Practice Flashcards
What is a minimum spanning tree (MST)?
Track your progress — Sign up free to save your progress and get smart review reminders based on spaced repetition.
All Flashcards in Topic 3.16
Below are all 16 flashcards for this topic. Sign up free to track your progress and get personalized review schedules.
3.16.18 cards
What is a minimum spanning tree (MST)?
The set of edges connecting every vertex with the least total weight and no cycle. On n vertices it has exactly n − 1 edges.
How many edges does a spanning tree on n vertices have?
Exactly n − 1, and it contains no cycle.
State Kruskal's algorithm.
Sort all edges from cheapest to dearest; add them one at a time, skipping any edge that would create a cycle, until all vertices are connected.
State Prim's algorithm.
Start at any vertex; repeatedly add the cheapest edge that joins a new (un-included) vertex to the tree, until all vertices are included.
Do Prim's and Kruskal's give the same answer?
They always give the same total weight (and the same tree when all edge weights are distinct).
What does Dijkstra's algorithm find?
The shortest path (least total weight) from a start vertex to a target vertex — not the whole connecting tree.
In Dijkstra's, how is a vertex's label updated?
new label = min(old label, permanent value of current vertex + edge to this vertex). The smallest temporary label becomes permanent next.
MST vs Dijkstra — when do you use each?
MST (Prim/Kruskal): connect ALL vertices cheaply. Dijkstra: shortest route between TWO specific vertices.
3.16.28 cards
What does the Chinese postman (route inspection) problem find?
The shortest CLOSED walk that uses every EDGE at least once and returns to the start.
When can the postman traverse every edge exactly once?
When every vertex has even degree (an Eulerian circuit exists); then the answer is just the sum of all edges.
Route-inspection method with odd vertices?
Pair the odd-degree vertices so the total of the shortest paths between the pairs is least; add that to the sum of all edges.
CPP length formula?
Sum of all edges + minimum pairing of the odd-degree vertices' shortest paths.
What does the travelling salesman problem (TSP) find?
The shortest CLOSED route visiting every VERTEX exactly once and returning to the start (a Hamiltonian cycle).
How do you get an upper bound for the TSP?
Nearest-neighbour algorithm: from the start, always go to the nearest unvisited vertex, then return to start. Its length is an upper bound.
How do you get a lower bound for the TSP (deleted-vertex method)?
Delete a vertex; find the MST of the rest; add the two cheapest edges from the deleted vertex back.
Edge problem or vertex problem?
Route inspection covers every EDGE; travelling salesman visits every VERTEX. Pick by what must be covered.
Topic 3.16 study notes
Full notes & explanations for Route algorithms (HL only)
Math AI exam skills
Paper structures, command terms & tips
Want smart review reminders?
Sign up free to track your progress. Our spaced repetition algorithm will tell you exactly which cards to review and when.
Start Free