Q4E Here's a proposal for how to fin... [FREE SOLUTION]

91影视

Algorithms

Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani

Computer Science

1st Edition 路 333 pages

ISBN: 9780073523408

Chapter 4: Q4E (page 132)

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 t o v$ . The length of the cycle $level [v] - level [w + 1]$ is 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.

Short Answer

Expert verified

The given strategy fails when the shortest cycle consists of more than the one back edge.

Step by step solution

Define graphs

A graph consists of nodes and edges. These nodes are also known as vertices. In undirected graphs, the nodes are connected by bidirectional edges. On the other hand, a directed graph is one in which all of the edges point in some particular direction.

Determine a counter example where the given strategy fails

The node's level is equal to its distance of the node from the root node. If there are more than one back edges in the shortest cycle, the given strategy to find the shortest cycle in an undirected graph fails. Consider the following graph:

The above diagram illustrates an undirected graph. In this undirected graph, the shortest cycle would be $1 鈫� 4 鈫� 5 鈫� 1$ . But the given algorithm would detect $1 鈫� 2 鈫� 3 鈫� 4 鈫� 1$ .