Question

Consider the following weighted undirected graph. 

(a) Explain why edge (B, D) is safe. In other words, give a cut where the edge is the cheapest edge crossing the cut. 

(b) We would like to run the Kruskal's algorithm on this graph. List the edges appearing in the Minimum Spanning Tree (MST) in the order they are added to the MST. For simplicity, you can refer to each edge as its weight. 

(c) 1We would like to run the Prim's algorithm on this graph using A as initial vertex. List the edges appearing in the Minimum Spanning Tree (MST) in the order they are added to the MST. For simplicity, you can refer to each edge as its weight.

Answer 1

a)

The edge (B,D) is safe because it is a part of minimal spanning tree and its removal leads to making the a new edge in minimum spanning tree.that means the weight of edge used instead of edge(B,D) will be higher

b)

Order of adding :

The edges are listed based on the increasing order:

BE,AD,DG,BD,GE,AF,FG,AB,FD,EC,EH,CH,BC,GH

as per the algorithm there is n-1 edges in the minimum spanning tree,where n is the number of edges.

from the above list edges are considered in the increasing order of their weights.

if the edge is the edge with minimum weight and its including doesn't form any cycle then the edge is added to the list edges of minimum spanning tree.

BE,AD,DG,BD,AF,EC,EH

C)

Order of adding:

Edge starting from the vertex A is considered.edge with minimum weight starting from A is considered.the process is repeated without forming any cycles untill number of edges is n-1 where n is the number of vertices.

In this case edge AD is the minimum weighted edge.all the edges from both these vertex is considered in the next iteration.

AD,DG,BD,BE,AF,EC,EH

hope the answer is satisfactory

any doubts please comment

please give me a thumbs up

answer is updated.