Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Minimum-Cost Spanning Trees

In this section we consider undirected graphs and their subgraphs. A subgraph  of a graph tex2html_wrap_inline70252 is any graph tex2html_wrap_inline71708 such that tex2html_wrap_inline71710 and tex2html_wrap_inline71712. In particular, we consider connected undirected graphs and their minimal subgraphs  . The minimal subgraph of a connected graph is called a spanning tree:

Definition (Spanning Tree)  Consider a connected, undirected graph tex2html_wrap_inline70252. A spanning tree  of G is a subgraph of G, say tex2html_wrap_inline71720, with the following properties:
  1. tex2html_wrap_inline71722.
  2. T is connected.
  3. T is acyclic.

Figure gif shows an undirected graph, tex2html_wrap_inline71728, together with three of its spanning trees. A spanning tree is called a tree because every acyclic undirected graph can be viewed as a general, unordered tree. Because the edges are undirected, any vertex may be chosen to serve as the root of the tree. For example, the spanning tree of tex2html_wrap_inline71728 given in Figure gif (c) can be viewed as the general, unordered tree

displaymath71702

   figure51849
Figure: An undirected graph and three spanning trees.

According to Definition gif, a spanning tree is connected. Therefore, as long as the tree contains more than one vertex, there can be no vertex with degree zero. Furthermore, the following theorem guarantees that there is always at least one vertex with degree one:

Theorem  Consider a connected, undirected graph tex2html_wrap_inline70252, where tex2html_wrap_inline71736. Let tex2html_wrap_inline71738 be a spanning tree of G. The spanning tree T contains at least one vertex of degree one.

extbfProof (By contradiction). Assume that there is no vertex in T of degree one. That is, all the vertices in T have degree two or greater. Then by following edges into and out of vertices we can construct a path that is cyclic. But a spanning tree is acyclic--a contradiction. Therefore, a spanning tree always contains at least one vertex of degree one.

According to Definition gif, the edge set of a spanning tree is a subset of the edges in the spanned graph. How many edges must a spanning tree have? The following theorem answers the question:

Theorem  Consider a connected, undirected graph tex2html_wrap_inline70252. Let tex2html_wrap_inline71738 be a spanning tree of G. The number of edges in the spanning tree is given by

displaymath71703

extbfProof (By induction). We can prove Theorem gif by induction on tex2html_wrap_inline70678, the number of vertices in the graph.

Base Case Consider a graph that contains only one node, i.e., tex2html_wrap_inline71756. Clearly, the spanning tree for such a graph contains no edges. Since tex2html_wrap_inline71758, the theorem is valid.

Inductive Hypothesis Assume that the number of edges in a spanning tree for a graph with tex2html_wrap_inline70678 has been shown to be tex2html_wrap_inline71762 for tex2html_wrap_inline71764.

Consider a graph tex2html_wrap_inline71766 with k+1 vertices and its spanning tree tex2html_wrap_inline71770. According to Theorem gif, tex2html_wrap_inline71772 contains at least one vertex of degree one. Let tex2html_wrap_inline71268 be one such vertex and tex2html_wrap_inline71776 be the one edge emanating from v in tex2html_wrap_inline63829.

Let tex2html_wrap_inline63813 be the graph of k nodes obtained by removing v and its emanating edge from the graph tex2html_wrap_inline63829. That is, tex2html_wrap_inline71790.

Since tex2html_wrap_inline63829 is connected, so too is tex2html_wrap_inline63813. Similarly, since tex2html_wrap_inline63829 is acyclic, so too is tex2html_wrap_inline63813. Therefore tex2html_wrap_inline63813 is a spanning tree with k vertices. By the inductive hypothesis tex2html_wrap_inline63813 has k-1 edges. Thus, tex2html_wrap_inline63829 as k edges.

Therefore, by induction on k, the spanning tree for a graph with tex2html_wrap_inline70678 vertices contains tex2html_wrap_inline71762 edges.




next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.