Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

5.6: Optimal Spanning Trees

( \newcommand{\kernel}{\mathrm{null}\,}\)

In some applications, a graph G is augmented by associating a weight or cost with each edge; such a graph is called a weighted graph. For example, if a graph represents a network of roads, the weight of an edge might be the length of the road between its two endpoints, or the amount of time required to travel from one endpoint to the other, or the cost to bury cable along the road from one end to the other. In such cases, instead of being interested in just any spanning tree, we may be interested in a least cost spanning tree, that is, a spanning tree such that the sum of the costs of the edges of the tree is as small as possible. For example, this would be the least expensive way to connect a set of towns by a communication network, burying the cable in such a way as to minimize the total cost of laying the cable.

This problem is one that can be solved by a greedy algorithm. Roughly speaking, a greedy algorithm is one that makes choices that are optimal in the short run. Typically this strategy does not result in an optimal solution in the long run, but in this case this approach works.

Definition 5.6.1: Weighted Graph

A weighted graph is a graph G together with a cost function c:E(G)R>0. If H is a subgraph of G, the cost of H is c(H)=eE(H)c(e).

Algorithm 5.6.1: The Jarník Algorithm

Given a weighted connected graph G, we construct a minimum cost spanning tree T as follows. Choose any vertex v0 in G and include it in T. If vertices S={v0,v1,,vk} have been chosen, choose an edge with one endpoint in S and one endpoint not in S and with smallest weight among all such edges. Let vk+1 be the endpoint of this edge not in S, and add it and the associated edge to T. Continue until all vertices of G are in T.

This algorithm was discovered by Vojtěch Jarník in 1930, and rediscovered independently by Robert C. Prim in 1957 and Edsger Dijkstra in 1959. It is often called Prim's Algorithm.

The algorithm proceeds by constructing a sequence of trees T1,T2,,Tn1, with Tn1 a spanning tree for G. At each step, the algorithm adds an edge that will make c(Ti+1) as small as possible among all trees that consist of Ti plus one edge. This is the best choice in the short run, but it is not obvious that in the long run, that is, by the time Tn1 is constructed, that this will turn out to have been the best choice.

Theorem 5.6.1

The Jarník Algorithm produces a minimum cost spanning tree.

Proof

Suppose G is connected on n vertices. Let T be the spanning tree produced by the algorithm, and Tm a minimum cost spanning tree. We prove that c(T)=c(Tm).

Let e1,e2,,en1 be the edges of T in the order in which they were added to T; one endpoint of ei is vi, the other is in {v0,,vi1}. We form a sequence of trees Tm=T0,T1,,Tn1=T such that for each i, c(Ti)=c(Ti+1), and we conclude that c(Tm)=c(T).

If e1 is in T0, let T1=T0. Otherwise, add edge e1 to T0. This creates a cycle containing e1 and another edge incident at v0, say f1. Remove f1 to form T1. Since the algorithm added edge e1, c(e1)c(f1). If c(e1)<c(f1), then c(T1)<c(T0)=c(Tm), a contradiction, so c(e1)=c(f1) and c(T1)=c(T0).

Suppose we have constructed tree Ti. If ei+1 is in Ti, let Ti+1=Ti. Otherwise, add edge ei+1 to Ti. This creates a cycle, one of whose edges, call it fi+1, is not in e1,e2,,ei and has exactly one endpoint in {v0,,vi}. Remove fi+1 to create Ti+1. Since the algorithm added ei+1, c(ei+1)c(fi+1). If c(ei+1)<c(fi+1), then c(Ti+1)<c(Ti)=c(Tm), a contradiction, so c(ei+1)=c(fi+1) and c(Ti+1)=c(Ti).


This page titled 5.6: Optimal Spanning Trees is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by David Guichard via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?