edited by
4,456 views
29 votes
29 votes

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?
edited by

3 Answers

Best answer
28 votes
28 votes
  1. Edges with weights: $2,3,4,7,9$

$\text{Minimum Spanning Tree}$
  1. Number of distinct minimum spanning tree: $2 (2^{\text{nd}}$ with a different edge of weight $4)$
  2. Yes
  3. Yes 
edited by
9 votes
9 votes

Minimum spanning tree:

2 votes
2 votes

The number of vertices in the graph is 6. So the number of edges in the MST will be 5.

A) {(n1,n2,2),(n1,n6,3),(n2,n4,4),(n3,n4,7),(n4,n5,9)} and {(n1,n2,2),(n1,n6,3),(n3,n4,7),(n4,n5,9),(n4,n6,4)}

B) Number of distinct minimum spanning trees is 2.

C) Yes. It’s 2.

D) Yes. It’s 9.

-------------------------------------------------------------------------------------------------------------------------------------------------------------------

Assumption:

C)Is the minimum among the edge weights of a minimum spanning tree unique over all possible minimum spanning trees of the graph?

If we consider the gate question to be correct: options C and  D will be False. Because of duplicate edge weights.

Related questions

52 votes
52 votes
6 answers
3
Kathleen asked Sep 14, 2014
13,973 views
How many undirected graphs (not necessarily connected) can be constructed out of a given set $V=\{v_1, v_2, \dots v_n\}$ of $n$ vertices?$\frac{n(n-1)} {2}$$2^n$$n!$$2^\f...
7 votes
7 votes
3 answers
4
go_editor asked Feb 8, 2018
1,987 views
Consider a relation examinee (regno, name, score), where regno is the primary key to score is a real number.Write an SQL query to list the regno of examinees who have a s...