Although question is simple but it will be good if you can add some explanation for other options for justification.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+11 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.

- List the edges of a minimum spanning tree of the graph.
- How many distinct minimum spanning trees does this graph have?
- Is the minimum among the edge weights of a minimum spanning tree unique over all possible minimum spanning trees of a graph?
- Is the maximum among the edge weights of a minimum spanning tree unique over all possible minimum spanning tree of a graph?

+13 votes

Best answer

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.9k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 949
- Others 1.3k
- Admissions 409
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,782 questions

41,758 answers

118,940 comments

41,401 users