Minimum spanning trees 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 vertices have?
- Outline Kruskal's algorithm.
- Sort edges in increasing weight; accept each unless it forms a cycle; stop at 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.