Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Hopcroft & Ullman's book - incomplete definition of a cycle in
a graph?

Replies: 2   Last Post: Mar 10, 2016 5:43 AM

 Messages: [ Previous | Next ]
 Tommy Jensen Posts: 249 From: Daegu, Korea Registered: 12/6/09
Re: Hopcroft & Ullman's book - incomplete definition of a cycle in
a graph?

Posted: Mar 10, 2016 4:52 AM

On Thu, 10 Mar 2016 11:21:01 +0200, Jussi Piitulainen wrote:

>
> You are thinking of computer science kind of trees, with a root and
> directed connections away from the root, no going back.

That is a good point actually. When they think of a graph, they
may well have in mind what is usually called a digraph. in which each
edge has a definite direction. The term "graph" has come to be used
for the kinds of relations that are symmetric, that is, there are no
directions on the edges. If there is an edge from a to b, the same
edge is also an edge from b to a. If they do not assume this, then
their definition makes perfectly sense. There can be a cycle which
is a loop, from a to a, and another cycle which consists of an edge
from a to b and another different edge from b to a.
So in that case the answer to the original post is that the
case of a single vertex should be somehow excluded. There can be no
cycle of length zero. The shortest cycles are loops, they join a
vertex to itself and have length 1.

Date Subject Author
3/10/16 Tommy Jensen
3/10/16 LudovicoVan