Question

Suppose T is a minimal spanning tree found by Prim’s algorithm in a connected graph
G.

(i) Show that either T contains the n-1 smallest edges, or the n-1 smallest edges form a subgraph which contains a cycle.

(ii) Show that if an edge (a, b) is not in T and if P is the unique path in T from a to
b, then for each edge e in P the weight of e is less than the weight of the edge (a, b).

Answer 1

i)The MST i.e T is built gradually by adding edges one at a time. At first the spanning tree consists only of a single vertex, which is choosen randomly. Then the edge having minimum weight outgoing from this vertex is selected and added to the spanning tree. After that the spanning tree already consists of two vertices. Now select and add the edge with the minimum weight that has one end in an already selected vertex (i.e. a vertex that is already part of the spanning tree), and the other end in an unselected vertex. And so on, i.e. every time we select and add the edge with minimal weight that connects one selected vertex with one unselected vertex. The process is repeated until the spanning tree contains all vertices (or equivalently until we have n−1edges).

In the end the constructed spanning tree will be minimal. If the graph was originally not connected, then there doesn't exist a spanning tree, so the number of selected edges will be less than n−1.

EXAMPLE- WE CAN SEE THAT THERE ARE TOTAL OF 9 VERTICES IN GRAPH AND (9-1) I.E 8 EDGES IN MINIMUM SPANNING TREE

.

ii)Prim’s algorithm is a Greedy algorithm. For any cycle in the graph, if the weight of an edge E of cycle is larger than the individual weights of all other edges of cycle, then this edge cannot belong to a Minimum Spanning tree.

From the above example we can say that if if an edge (A, B) is not in MST (as and if P is the unique path in MST from A to B, then for each edge e in MST the weight of e is less than the weight of the edge (A, B).

EXAMPLE-