The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
751 views

Consider a weighted undirected graph with vertex set $V = \{ n1, n2, n3, n4, n5, n6 \} $ and edge set $E = \{(n1,n2,2), (n1,n3,8), (n1,n6,3), (n2,n4,4), (n2,n5,12), (n3,n4,7), (n4,n5,9), (n4,n6,4)\}$. The third value in each tuple represents the weight of the edge specified in the tuple.

  1. List the edges of a minimum spanning tree of the graph.
  2. How many distinct minimum spanning trees does this graph have?
  3. Is the minimum among the edge weights of a minimum spanning tree unique over all possible minimum spanning trees of a graph?
  4. Is the maximum among the edge weights of a minimum spanning tree unique over all possible minimum spanning tree of a graph?
asked in Algorithms by Veteran (59.5k points)
edited by | 751 views

2 Answers

+16 votes
Best answer

a) edges with weight: $\text{2,3,4,7,9}$



b) no of distinct minimum spanning tree: $2$ (2nd with the different edge of weight $4$)

c) yes

d) yes

Edit:- Combining both answers into $1$.

answered by Loyal (8.2k points)
edited by
+1
Although question is simple but it will be good if you can add some explanation for other options for justification.
+7 votes

Minimum spanning tree:

answered by Loyal (8.2k points)
0
Please add this image in your first answer. It will make answer more elegant.


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,684 questions
46,748 answers
140,513 comments
58,300 users