next up previous
Next: 3 Implementation on a Up: Minimum-Cost Spanning Tree as Previous: 1 Introduction

2 Minimum-cost spanning tree

In this section we define the minimum-cost spanning tree problem and a related path-finding problem. We give a recurrence for solving the path-finding problem via dynamic programming. We then prove that the solution to the path-finding problem contains the solution to the minimum-cost spanning tree problem.

Given an n-node connectedgif undirected graph tex2html_wrap_inline842 , where V is the set tex2html_wrap_inline846 , and where each edge tex2html_wrap_inline856 in E has cost tex2html_wrap_inline852 , the minimum-cost spanning tree problem is to find a subgraph that connects the vertices in V such that the sum of the costs of the edges in the subgraph is minimum. We assume that the edge costs are unique. (If not, lexicographical information can be added to make them unique.) For convenience, we also assume that if tex2html_wrap_inline856 is not in E then it has cost tex2html_wrap_inline860 .

The path-finding problem is to compute the cost tex2html_wrap_inline898 for each tex2html_wrap_inline864 of the shortest (lowest-cost) path from i to j that passes through vertices only in the set tex2html_wrap_inline870 , where the cost of a path is defined to be the highest cost of any edge on the path. For any i and j, the shortest path from i to j with no intermediate vertex higher than k either passes through k or does not. In the first case, the cost of the shortest path from i to j is either the cost of the shortest path from i to k or the cost of the shortest path from k to j, whichever is higher. In the second case, we have tex2html_wrap_inline896 . Thus, tex2html_wrap_inline898 can be computed by the recurrence


The following theorem shows that the unique minimum-cost spanning tree can be recovered from the costs of the shortest paths.


Proof: The proof has two parts. We first show that if tex2html_wrap_inline856 is a tree edge then tex2html_wrap_inline932 . We then show that if tex2html_wrap_inline932 then the edge tex2html_wrap_inline856 is in the tree. First, assume that tex2html_wrap_inline856 is a tree edge, but that tex2html_wrap_inline916 . Consider the cut of the graph that tex2html_wrap_inline856 crosses, but no other tree edge crosses. Since tex2html_wrap_inline916 , there must be some path from i to j whose highest-cost edge has cost tex2html_wrap_inline926 . Hence, every edge on this path has cost less than tex2html_wrap_inline938 . This path must cross the cut at least once. Replacing the edge tex2html_wrap_inline856 by any edge on the path that crosses the cut reduces the cost of the tree, a contradiction. Conversely, assume that tex2html_wrap_inline932 , but that tex2html_wrap_inline856 is not a tree edge. Adding the edge tex2html_wrap_inline856 to the tree forms a cycle whose highest-cost edge costs more than than tex2html_wrap_inline938 . Replacing this edge by tex2html_wrap_inline856 yields a tree with smaller cost, a contradiction. width 4pt height 8pt depth 1.5pt

next up previous
Next: 3 Implementation on a Up: Minimum-Cost Spanning Tree as Previous: 1 Introduction

Bruce Maggs
Sun Jul 21 23:35:52 EDT 1996