DFS and depth tree

user_17294992 0
Viewed 42

I need to decide whether the following statement is true or false. If true, explain why, if false give a counterexample.

Let T be the depth-tree resulting from running the DFS algorithm on a graph G and a source vertex s. G is an undirected graph with a cycle of exactly 3 vertices. So T necessarily does not contain all the shortest paths from s to the other vertices in G.

I think it's true but I don't know how to prove it or to explain why

tree depth-first-search graph data-structures
1 Answers

This is a little tricky, because the graph G may contain other cycles. There are many ways that the 3-cycle might be embedded in the tree, and it may be that none of the edges in the cycle are in the tree at all, so it's difficult to make a proof by dividing all the possible embeddings into a few cases.

I think the easiest way to prove this is:

  • If T is a DFS tree for G rooted at s, then every edge in G is either in T, or it connects a node to an ancestor in T.
  • Note that the vertices adjacent to any edge are at different heights. For edges in the tree, they differ by 1. For other edges they differ by at least 1.
  • The sum of height changes around a cycle must be 0, since it starts and ends at the same vertex.
  • It cannot be that all the height differences in the 3-cycle are of magnitude 1, because then their sum would be an odd number -- not 0.
  • At least one edge in the 3-cycle must therefore have a height difference > 1. This edge will be a short-cut to its lower vertex, since all paths in the tree can change height by at most one per step.
user_54835260
Related