Consider a weighted undirected graph with vertex set V = {n1,n2,n3,n4,n5,n6}…

PYQ GATE 2001

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 overall 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 trees of a graph?

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…