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 connected undirected graph , where V is the set , and where each edge in E has cost , 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 is not in E then it has cost .

The path-finding problem is to compute the cost for each of the shortest (lowest-cost) path from i to j that passes through vertices only in the set , 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 . Thus, 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 is a tree edge then . We then show that if then the edge is in the tree. First, assume that is a tree edge, but that . Consider the cut of the graph that crosses, but no other tree edge crosses. Since , there must be some path from i to j whose highest-cost edge has cost . Hence, every edge on this path has cost less than . This path must cross the cut at least once. Replacing the edge by any edge on the path that crosses the cut reduces the cost of the tree, a contradiction. Conversely, assume that , but that is not a tree edge. Adding the edge to the tree forms a cycle whose highest-cost edge costs more than than . Replacing this edge by yields a tree with smaller cost, a contradiction. width 4pt height 8pt depth 1.5pt

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

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