Solution Found!
Heres a proposal for how to find the length of the shortest cycle in an undirected graph
Chapter 4, Problem 4.4(choose chapter or problem)
Here’s a proposal for how to find the length of the shortest cycle in an undirected graph with unit edge lengths. When a back edge, say (v, w), is encountered during a depth-first search, it forms a cycle with the tree edges from w to v. The length of the cycle is level[v] − level[w] + 1, where the level of a vertex is its distance in the DFS tree from the root vertex. This suggests the following algorithm:
Do a depth-first search, keeping track of the level of each vertex.
Each time a back edge is encountered, compute the cycle length and save it if it is smaller than the shortest one previously seen.
Show that this strategy does not always work by providing a counterexample as well as a brief (one or two sentence) explanation.
Questions & Answers
QUESTION:
Here’s a proposal for how to find the length of the shortest cycle in an undirected graph with unit edge lengths. When a back edge, say (v, w), is encountered during a depth-first search, it forms a cycle with the tree edges from w to v. The length of the cycle is level[v] − level[w] + 1, where the level of a vertex is its distance in the DFS tree from the root vertex. This suggests the following algorithm:
Do a depth-first search, keeping track of the level of each vertex.
Each time a back edge is encountered, compute the cycle length and save it if it is smaller than the shortest one previously seen.
Show that this strategy does not always work by providing a counterexample as well as a brief (one or two sentence) explanation.
ANSWER:Step 1 of 2
An edge in an undirected graph is bidirectional. That is if there is an edge between two nodes A and B, then there is a connection from A to B and also B to A.
The given algorithm is as follows:
• Execute DFS to keep the track of the level of each vertex.
• When the back edge is encountered, calculate the length of the cycle and save it if it is smaller than the previous shortest cycle.