Minimal Spanning Tree Problem
A tree can be defined as an acyclic, undirected and connected graph. A spanning tree is a subgraph of G, that is, undirected and connected graph, is a tree and consists of all the vertices of G. A minimum spanning tree is a spanning tree but has weights or lengths related with edges and the total weight is at the minimum.
Prim's Algorithm
Sample Assignment
Assume that it is desired to set up a cable communication network that connects major cities, which is revealed in the figure. Find out how the cities are linked such that the total cable mileage is reduced.
Answer
C = {LA} C' = {SE, DE, DA, EH, NY, DC}
C = {LA, SE} C' = {DE, DA, EH, NY, DC}
C = {LA, SE, DE} C' = {DA, EH, NY, DC}
C = {LA, SE, DE, DA} C' = {EH, NY, DC}
C = {LA, SE, DE, DA, EH} C' = {NY, DC}
C = {LA, SE, DE, DA, EH, NY} C' = {DC}
C = {LA, SE, DE, DA, EH, NY, DC} C' = { }
The resulting network is
Therefore the total cable mileage is 1100 + 1300 + 780 + 900 + 800 + 200 = 5080
18,76,764
Questions Asked
21,311
Experts
9,67,568
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!