3.2.2. The Spanning Tree

A spanning tree of a graph G is a spanning subgraph of G that is a tree.

Theorem 3.8. Every connected graph contains a spanning tree.

Proof. By construction. We choose an arbitrary vertex . Let

,

where M is the largest integer for which VM is not empty. If and is an path then . It is clear that , if , and for any , there exists at least one , which adjacent to y in G. (), and these edges form together a spanning tree in G.

 

Figure 3.3. Construction of a spanning tree.

Corollary 3.9. If the graph G is , then the size of its spanning tree is .

Corollary 3.10. For any forest with order n and k components, the size of the forest is .

A well-known problem in optimization theory asks for a relatively easy way of finding a spanning subgraph with a special property: Given a graph and a positive valued cost function f defined on the edges, , find a connected spanning subgraph of G for which

is minimal. Such a spanning subgraph T is called as an economical spanning subgraph.

It is very easy to find a „real life" problem which results in finding an economical spanning tree: Certain villages in an area are to be joined to a water supply situated in one of the villages. The system of pipes contains those pipelines which are connecting the water towers of two villages. For any two villages we know how much it would cost to build a pipeline connecting them, provided such a pipeline can be built at all. How can we find an economical system of pipes?

Since the system has to be economical, T is a minimal connected spanning subgraph, which is a spanning tree of G.

We can construct four different algorithms, each of them results in an economical spanning tree.

Algorithm 1. (Kruskal, 1956): We choose one of the cheapest edges of G, that is an edge e for which is minimal. Each subsequent edge will be chosen from among the cheapest remaining edges of G with the only restriction that we must not select all edges of any cycle.

Algorithm 2. (Prim): Pick a vertex of G and select one of the least costly edges incident with , say . Then choose one of the least costly edges of the form , where , and . Having found vertices and an edge , for each vertex with , select one of the least costly edges of form , say where and . The process terminates after we have selected edges.

Algorithm 3. (Boruvka): This method is applicable only if no two edges have the same cost. We start to choose the cheapest edge in each vertex simultaneously. At the end of this stage we get a spanning forest with components . Now, for each we will choose a cheapest edge from those of ones where and only . We continue this procedure until the edges have been chosen form a connected graph.

Algorithm 4. : This method based on the fact that it is foolish to use a costly edge unless it is needed to ensure the connectedness of the subgraph. So, let us delete one by one those costliest edges whose deletion does not disconnect the graph.

Considering the above algorithms we can see that in each step we make the local best decision: either we choose the cheapest edge from the non-considered edges, or we deleted the most expensive edge.

That algorithm which makes a local best solution in each step we call greedy algorithm.

We call a system of sets as a matroid if it has the following characteristics:

  • .
  • If and then .
  • If and then there exists an such that .

It is known that in a matroid system any greedy algorithm results in an optimal solution. Here we omit the proof but we encourage the reader to prove this statement. Therefore, to prove the correctness of the above four algorithms it is enough to prove that the set of spanning trees creates a matroid. (Here we omit the proof but we encourage the reader to prove this statement.)

 

Figure 3.4. A graph G and its economical spanning tree computed by the Kruskal algorithm

Theorem 3.11. Let T be a nontrivial tree with maximum degree , and let be the number of vertices of degree i for . Then

Proof. Suppose that T has order n and size m. Then

and

Therefore

If we solve this equation for n1 then we get the desired result.

The degree matrix is the matrix with and for  .