algorithms
algorithms copied to clipboard
jeffgerickson
[Oops.] A single edge is not a cycle
Please verify that the error is present in the most recent revision before reporting.
Chapter number or note title: 5
Page number: 191
Error description: The definition of cycle allows a single edge uv to be a cycle with the walk u,v,u. The book states:
- A walk in an undirected graph G is a sequence of vertices, where each adjacent pair of vertices are adjacent in G
- A walk is closed if it starts and ends at the same vertex; a cycle is a closed walk that enters and leaves each vertex at most once
By these definitions, the walks uvu or just u would be a cycle.
Suggested fix (if any): Not sure what's cleanest. I know that CLRS defines a "simple cycle" as a closed walk with distinct edges and vertices (except the endpoint). Alternatively, you could say a cycle is a closed walk with at least 4 vertices.
There are no pairs in u, so perhaps the walk definition doesnt apply to that one.
The walk definition should still apply, as "each adjacent pair of vertices are adjacent in G" is vacuously true when there are no pairs.
A single vertex is just a zero-length walk. This convention is used other places in the book, for example, in the definition of connected on the same page. We'd certainly say that a vertex is reachable from itself, and that a single vertex is a connected graph.