23. Minimum Spanning Tree a) Draw a weighted undirected graph with exactly 3 nod

Question

23. Minimum Spanning Tree

a) Draw a weighted undirected graph with exactly 3 nodes that has exactly 0 minimum spanning trees.

b) Draw a weighted undirected graph with exactly 3 nodes that has exactly 1 minimum spanning tree.

c) Draw a weighted undirected graph with exactly 3 nodes that has exactly 2 minimum spanning trees.

d) Draw a weighted undirected graph with exactly 3 nodes that has exactly 3 minimum spanning trees.

e) Can a weighted undirected graph with 3 nodes have more than 3 minimum spanning trees? Why or why not?

Explanation / Answer

Question:--- a) Draw a weighted undirected graph with exactly 3 nodes that has exactly 0 minimum spanning trees.

Answer:----- Any unconnected, weighted , undirected graph

Question:---b) Draw a weighted undirected graph with exactly 3 nodes that has exactly 1 minimum spanning tree.

Answer:---- Solution needs to have either 2 or 3 non self-edges and if it has 3 non self-edges then no two can have the same weight.

Question:---c) Draw a weighted undirected graph with exactly 3 nodes that has exactly 2 minimum spanning trees.

Answer:----Graph needs 2 non self-edge ,with exactly 2 having the same weight and the third edge having a lower weight.

Question:---d) Draw a weighted undirected graph with exactly 3 nodes that has exactly 3 minimum spanning trees.

Answer:----- Graph needs 3 non-self-edges , all with the same weight.

Question:---e) Can a weighted undirected graph with 3 nodes have more than 3 minimum spanning trees? Why or why not?

Answer:--- A 3-node graph can only have 3 spanning tree because it takes two edges ( number of nodes - 1) to create a spanning tree.If Node are A,B and C then only possible spanning tree are,

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.