Section 10.5:Discrete Mathematics and Its Applications, Extra Examples

Discrete Mathematics and Its Applications, Extra Examples
Section 10.5




p.740, icon at Example 3
#2. Suppose the vertices of Kn are numbered 1, 2, . . ., n (in clockwise order) and each edge is assigned a
weight equal to the sum of the labels on the endpoints of the edge. Find a spanning tree of minimum weight
for this graph and find the weight of this spanning tree.
Solution:
The spanning tree of minimum cost has edges {1, 2}, {1, 3}, . . ., {1, n}. Using either Kruskal’s Algorithm or
Prim’s Algorithm, the first edges added are {1, 2} and {1, 3}. At the next stage, edges {2, 3} and {1, 4}
have the smallest weight, but adding edge {2, 3} would create a circuit. Therefore edges {1, 2}, {1, 3}, and
{1, 4} are inserted into the spanning tree. In general, if edges {1, 2}, {1, 3}, . . ., {1, k} have been selected, the
next edge inserted must be {1, k + 1} (of weight k + 2). (Any other edge {i, j} with weight ≤ k + 2 would
have 1 < i ≤ k and 1 < j ≤ k and would create a circuit when combined with {1, i} and {1, j}.) Thus, the
spanning tree of minimum weight consists of {1, 2}, {1, 3}, . . . , {1, n}. Its total weight is
(1 + 2) + (1 + 3) + · · · + (1+n) = (n − 2) + n(n + 1)
2
=
(n + 4)(n − 1)
2
.