Q15

MCQMarks unknown

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.

(A)

List the edges of a minimum spanning tree of the graph.

(B)

How many distinct minimum spanning trees does this graph have?

(C)

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

(D)

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

Loading…