Share
Explore BrainMass

Undirected Graph, Spanning Tree, Joining Nodes and Ancestors

Let G be an undirected graph, and let T be the spanning tree genereted by a depth-first search of G. Prove that an edge of G that has no corresponding edge in T cannot join nodes in differect branches of the tree, but must necessarily join some node v to one of its ancestors in T.

Solution Preview

Proof:

When we use a depth-first search (DFS) to build a spanning tree T of G, each edge e of G is divided into two groups. If e is in T, it is ...

Solution Summary

Depth-First Search ( DFS ), Undirected Graph, Spanning Tree, Joining Nodes and Ancestors are investigated.

$2.19