11.5 Minimum Spanning Trees

Question 1

minimum spanning tree

Answer 1

A minimum spanning tree in a connected weighted graph is a spanning tree that has the smallest
possible sum of weights of its edges.

Question 2

minimum spanning tree

Answer 2

A minimum spanning tree in a connected weighted graph is a spanning tree that has the smallest
possible sum of weights of its edges.

Question 3

Prim’s Algorithm

Answer 3

An algorithm for finding a minimum spanning tree.
• Begin by choosing any edge with smallest weight, putting it into the spanning tree.
• Successively add to the tree edges of minimum weight that are incident to a vertex already
in the tree, never forming a simple circuit with those edges already in the tree.
• Stop when n − 1 edges have been added.

Question 4

Kruskal’s Algorithm

Answer 4

An algorithm for finding a minimum spanning tree.
• Begin by choosing an edge in the graph with minimum weight.
• Successively add edges with minimum weight that do not form a simple circuit with those
edges already chosen.
• Stop after n − 1 edges have been selected.