Spanning trees and network optimisation

Spanning trees and network optimisation Flashcards

Spec DB1–DB2 · AQA 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.

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 connected network with no cycles that contains every node of the network.
How many arcs has a spanning tree on nn nodes?
n−1n-1
What is a minimum spanning tree?
A spanning tree of least total weight.
State Kruskal's algorithm.
Take arcs in ascending order of weight, rejecting any that form a cycle, until n−1n-1 arcs are chosen.
State Prim's algorithm.
Start at any node; repeatedly add the lightest arc joining a node in the tree to a node not in it.
When is an arc rejected in Kruskal's algorithm?
When its two nodes are already connected, so it would form a cycle.
What do node, arc and weight mean?
Node: a point. Arc: a line joining two nodes. Weight: the number on an arc (distance, cost or time).
Do Kruskal's and Prim's give the same total weight?
Yes: both give a minimum spanning tree.
Is a minimum spanning tree always unique?
No: equal weights can give different trees, but the total weight is the same.
How does Prim's algorithm work on a matrix?
Choose the smallest entry in the columns of tree nodes among rows of nodes not yet in the tree.
What should you do if an arc in the network is closed?
Remove it and re-apply the algorithm to the remaining arcs.
Does an MST give the shortest route between two nodes?
No: it minimises total weight of the whole tree, not distances between pairs.

Flashcards