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

+13 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?

+16 votes

Best answer

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,684 questions

46,748 answers

140,513 comments

58,300 users