Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Here is the proof that was given in my textbook (P.178 of "Introduction to Combinatorics"). I want to check if my reasoning behind the parts in bold are correct.

Let $T_i$ be the tree obtained by the algorithm with $i$ vertices, $V_i$ be the vertex set for $T_i$, $y_i$ be the edge added in going from $T_{i-1}$ to $T_i$, and$c(y)$ be the cost of edge $y$.

The object is to prove that $T_v$ obtained by Prim's Algorithm is a minimal spanning tree.

Suppose $T^1$ is a minimal spanning tree in $G$. Find the smallest $i$ such that $y_i$ is not an edge of $T^1$. Since $T^1$ is a spanning tree of $G$, (1)there is a path in $T^1$ joining the two end points of $y_i$. (2)As one travels along the path, one must encounter an edge $z$ joining a vertex in $V_{i-1}$ to one that is not in $V_{i-1}$. Now, at the iteration when $y_i$ was added to $T_{i-1}$, $z$ could also have been added, (3)and it would have been added instead of $y_i$ if its cost was less than that of $y_i$. So (4)$c(z) \ge c(y_i)$. Then (5)$T^2$ is connected, (6)has the same number of edges as $T^1$, (7)and the total cost of its edges is not larger than that of $T^1$, therefore (4)it is also a minimum spanning of $G$ and (8)it contains $y_i$ and all the edges added before it during the construction of $T_v$. Repeat this process until $T_v$ is achieved.

(1)By definition, a spanning tree is a connected graph that includes all the vertices in $G$. Therefore, there is a walk between any two vertices of $G$, and any walk contains a path.

(2)Suppose there was no such edges. Then all the endpoints of the edges in the path would be in $V_{i-1}$, and it would be impossible for the walk to finish at the other endpoint, which is a vertex not in $V_{i-1}$.

(3)Because Prim's algorithm chooses the edge with the smallest cost that increases the number of vertices by one.

(4)This is more a question; why is it not $c(z) = c(y_i)$? Is it possible that $c(z) \gt c(y)$ and $T^1$ is still a minimum spanning tree?

(5)Let the two endpoints of $y_i$ be $a, b$ and those of $z$ be $x,y$. So the walk from $a$ to $b$ via edge $z$ is $aAxyBb$, whee $A$ and $B$ are strings of vertices. After deleting $z$, one can still go from $x$ to $y$ by way of $xAabBy$ (with the order of $B$ reversed). All other edges are unchanged and $T^1$ was connected, so the $T^2$ is connected.

(6)Because we deleted one edge and added another.

(7)The only change in the cost was replacing $c(z)$ with $c(y_i)$, of which the latter was less than or equal to the former.

(8)Suppose there was an edge $y_k$ with $k \lt i$ such that it is not in $T^2$. Then it is not in $T^1$, because this edge was unchanged. This contradicts the $y_i$ being the edge with the smallest $i$ that is not an edge in $T^1$.

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.