Minimum spanning trees

Minimum spanning trees Flashcards

Spec 2.1 · Edexcel International A Level Maths: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

12 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

See all 12 cards
What is a spanning tree?
A tree that includes every vertex of the network, using some of its arcs.
How many arcs does a spanning tree of nn vertices have?
n−1n-1.
What is the minimum spanning tree (minimum connector)?
The spanning tree with the smallest total weight.
State the steps of Kruskal's algorithm.
Sort arcs by increasing weight, then add each arc unless it forms a cycle, until n−1n-1 arcs are chosen.
When do you reject an arc in Kruskal's algorithm?
When its two ends are already connected, so adding it would form a cycle.
State the steps of Prim's algorithm.
Start at any vertex, then repeatedly add the smallest arc joining the tree to a new vertex.
What is the main difference between Prim's and Kruskal's algorithms?
Prim's grows one connected tree from a start vertex; Kruskal's picks the smallest arcs anywhere, joining separate pieces.
Which algorithm needs no cycle check?
Prim's, because it only ever adds a new vertex.
How do you start Prim's algorithm on a matrix?
Label the starting vertex's column 1 and delete its row.
Why is a distance matrix symmetrical?
The arc XYXY has the same weight as YXYX, so each arc appears twice.
A matrix has 14 non-blank entries. How many arcs?
77, since each arc is entered twice.
Can a network have more than one MST?
Yes, if arcs have equal weights, but every MST has the same total weight.

Flashcards