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
.