Subject: 326: Clarification on the Book
From: James Nicholas Deibel (jdeibel@cs.washington.edu)
Date: Wed May 22 2002 - 14:41:32 PDT
At the bottom of page 420, the book says "a simple cycle is also a simple
path." This sounds wrong since the idea of a simple path is one that
never repeats a vertex. By the book's defintion of a simple path (which
allows that the first and the last vertices in a simple path can be the
same) this statement makes sense.
Their definition of a simple path in the book is a tad off standard in my
opinion. Most books that I have seen will claim that a path is simple if
all vertices encountered in the path are distinct. This would not allow
the first and last vertices to be the same. Also, note that this is not
the same as saying a path where are all the edges are distinct.
I would then define a cycle {v0, v1, v2, ... , vn, v0} to be simple if
there exists a simple path from v0 to vn and there exists an edge from vn
to v0.
For the homework, use the book's defintion of simple paths and simple
cycles if you need it. I wanted to point out this difference to hopefully
curb any confusion. Unfortunately, graph theory is one of those areas of
mathematics that is not fully set in its formal definitions. You would be
amazed at how many different definitions there are just for G* where G is
a graph.
nick deibel
jdeibel@cs.washington.edu
-- assume nothing is mundane. life is automatically more perplexing.
This archive was generated by hypermail 2b25 : Wed May 22 2002 - 14:41:45 PDT