Solve the minimal-spanning tree problem defined below:
A)total cost = 13
B)total cost = 15
C)total cost = 17
D)total cost = 11

Question

Solve the minimal-spanning tree problem defined below: 
A)total cost = 13 
B)total cost = 15 
C)total cost = 17 
D)total cost = 11

Quizplus · Accepted Answer

By calculating the weight of each edge, we can construct the weighted graph as follows.

2     3
A ------ B ----- C
|\______|_____/_|
|       1     1  
|       |     |
D ------ E --- F

The three edges with the smallest weights are AE (1), AB (2), and BE (3). If we choose any one of them, we will have a spanning tree. However, we choose the edge with the smallest weight first: AE. This creates a tree with two vertices, A and E.

1
A ----- E 
We then add the edge with the smallest weight that connects either A or E with a vertex that is not in the tree. The only such edge is AB (weight 2), so we add it:

1
A ----- E 
 \       |
  2      B
   \     |
    \    | 3
      \  |
        C 
We now have a tree that spans four vertices. The only edge that connects a vertex not in the tree to one that is in the tree is CF (weight 4), so we add it:

1
A ----- E 
 \       |
  2      B
   \     |
    \ 4  | 3
      \ |
        C 
We now have a tree that spans all six vertices. The total weight of the tree is the sum of the weights of all the edges, which is 1 + 2 + 4 + 3 + 1 + 4 = 15.

Solve the Minimal-Spanning Tree Problem Defined Below