Define spanning tree. For the un-directed graph given below write the sequence of edges visited of during the execution of Prime’s algorithm to construct a minimum cost spanning tree_

Spanning tree: A sub graph T of a un-directed graph G = {V, E} is a spanning tree of G if it is a tree and contains every vertex of G.

Example:

Now,

Step-1: We will first select a minimum distance edge from given graph.

Step-2: The next minimum distance edge is a-d. This edge is adjacent previously vertex a.

Step-3: The next minimum distance edge is d-f which is already adjacent previously edge a-b.

Step-4: The next select edge is f-c which is with minimum distance and it is adjacent to already selected edge d-f.

Step-5: The next select edge is c-e which is adjacent to already selected edge f-c.

Step-6: The next select edge is c-h.

Step-7: The next select edge is h-g.

Step-8: The next select edge is g-i. Which is with minimum distance. Since all the vertices are visited and we get a connected tree as minimum spanning tree.

 The minimum cost of spanning tree is 45.

The applications of spanning tree:

(i) Consider an application where n stations are to be linked using a communication network.

(ii) The laying of communication links between any two stations involves a cost.

(iii) The problem is to obtain a network of communication links which while preserving the connectivity between stations does it with minimum cost.

(iv) It preserves the connectedness of the graph yields minimums cost.