Minimum spanning trees

Minimum spanning trees Flashcards

Spec 2.1 · Edexcel A-Level Further 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.

13 cards

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

See all 13 cards
What is a minimum spanning tree?
A spanning tree with the smallest possible total weight.
How many edges does a spanning tree of a network with nn vertices have?
n−1n-1
Outline Kruskal's algorithm.
Sort edges in increasing weight; accept each unless it forms a cycle; stop at n−1n-1 edges.
Why does Kruskal's algorithm reject an edge?
Its two ends are already connected, so it would form a cycle.
Outline Prim's algorithm.
Start at any vertex; repeatedly add the shortest edge joining the tree to a new vertex.
Can Prim's algorithm form a cycle?
No: it only ever adds an edge to a vertex not yet in the tree.
In matrix Prim's, what do you do with the start vertex's row?
Delete the row and number its column 1.
In matrix Prim's, what do you circle each time?
The smallest entry in the numbered columns, in a row not yet deleted.
What does a dash mean in a distance matrix?
There is no direct edge between those vertices.
What is special about the matrix of an undirected network?
It is symmetric about the leading diagonal.
Is the minimum spanning tree unique?
Yes if all the edge weights are different.
Does a minimum spanning tree give the shortest route between two vertices?
Not necessarily. It minimises total weight only.
If an edge in the tree is removed from the network, what do you do?
Re-find the tree: join the vertex by its cheapest remaining edge.

Flashcards