The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+10 votes
559 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 (68.9k points)
edited by | 559 views

2 Answers

+13 votes
Best answer

a) edges with weight: 2,3,4,7,9



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

c) yes

d) yes

Edit:- Combining both answers into 1.

answered by Boss (8.5k points)
selected by
Although question is simple but it will be good if you can add some explanation for other options for justification.
+6 votes

Minimum spanning tree:

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

Related questions



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

32,692 questions
39,293 answers
110,104 comments
36,700 users