《Discrete Mathematics II教学-华南理工》7.4 Spanning trees.pptVIP

Section 7.4 Spanning Trees Spanning tree d a b c e (a) (b) Definition 1: Let G be a simple graph. A spanning tree of G is a subgraph of G that is a tree containing every vertex of G. d a b c e G A spanning tree of G d a b c e Spanning tree Theorem 1: A simple graph is connected iff it has spanning tree. Proof: First, suppose that a simple graph G has a spanning tree T. T contains every vertex of G.Furthermore, there is a path in T between any two of its vertices. Since T is a subgraph of G, there is a path in G between any two of its vertices. Hence, G is connected. Next suppose that G is connected. If G is not a tree, it must contain a simple circuit. Remove an edge from one of these simple circuits. The resulting subgraph has one fewer edge but still contains all the vertices of G and is connected. If this subgraph is not a tree, it has a simple circuit; so as before, remove an edge that is in a simple circuit. Repeat this process until no simple circuits remain. The process terminates when no simple circuits remain. A tree is produced since the graph stays connected as edges are removed.This tree is a spanning tree since it contain every vertices of G. Theorem Depth-first search (backtracking 回溯) Breadth-first search Algorithms for constructing spanning trees A procedure for constructing a spanning tree by adding edges that form a path until this is not possible , and then moving back up the path until a vertex is found where a new path can be formed. Depth-first search (backtracking） a d i j c e f h k b g f g h k j i d e c b a G A Depth-First Search of G. Example A procedure for constructing a spanning tree that successively adds all edges incident to the last set of edges added, unless a simple circuit is formed. Breadth-first search a d i j c e f h k b