Mathematics for Computer Science

11.11. References 469

(vii)cCs

(d)Prove that one of the quantities from part (c) strictly decreases at each transi-
tion. Conclude that for every starting state, the machine will reach a final state.

Problem 11.65.
Prove that a graph is a tree iff it has a unique path between every two vertices.

Problem 11.66.
LetGbe a weighted graph and suppose there is a unique edgee 2 E.G/with
smallest weight, that is,w.e/ < w.f /for all edgesf 2 E.G/feg. Prove that
any minimum weight spanning tree (MST) ofGmust includee.

Problem 11.67.
LetGbe a 4  4 grid with vertical and horizontal edges between neighboring
vertices. Formally,

V.G/DŒ0;3ç^2 WWDf.k;j/j 0 k;j 3 g:

Lettinghi;jbe the horizontal edgeh.i;j/—.iC1;j/iandvj;ibe the vertical edge
h.j;i/—.j;iC1/ifori 2 Œ0;2ç;j 2 Œ0;3ç, the weights of these edges are

w.hi;j/WWD

4iCj

100

;

w.vj;i/WWD 1 C

iC4j

100

:

(A picture ofGwould help; you might like to draw one.)
(a)Construct a minimum weight spanning tree (MST) forGby initially selecting
the minimum weight edge, and then successively selecting the minimum weight
edge that does not create a cycle with the previously selected edges. Stop when the
selected edges form a spanning tree ofG. (This is Kruskal’s MST algorithm.)

(b)Grow an MST forGstarting with the tree consisting of the single vertex.1;2/
and successively adding the minimum weight edge with exactly one endpoint in the
tree. Stop when the tree spansG. (This is Prim’s MST algorithm.)

(c)Grow an MST forGby treating the vertices.0;0/;.0;3/;.2;3/as 1-vertex
trees and then successively adding, for each tree in parallel, the minimum weight