Spanning trees and network optimisation 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 nodes?
- 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 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.