The Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.






Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.