Spanning Trees and Route Problems flashcards
12 practice cards drawn from the Spanning Trees and Route Problems lessons. Tap a card to turn it over. Every answer is checked against the lesson it came from.
Read the Spanning Trees and Route Problems lessons in full →
Which edge does Kruskal add last?
B to E
from “Kruskal’s Algorithm for a Spanning Tree”
How many edges does the minimum spanning tree of these five towns have?
4
from “Kruskal’s Algorithm for a Spanning Tree”
Prim starts at A. Which edge does it take first?
A to C
from “Prim’s Algorithm and the Matrix Method”
Prim starts at A. Which town joins the tree next?
C
from “Prim’s Algorithm and the Matrix Method”
What is the length of the shortest closed route using every street?
30
from “The Chinese Postman Problem”
Which vertices of this network have odd degree?
B and C
from “The Chinese Postman Problem”
What does the cycle A-B-C-D-A cost?
24
from “The Traveling Salesman Problem”
How many different cycles visit all 5 towns?
12
from “The Traveling Salesman Problem”
A nearest-neighbor tour costs 22. What does that tell you?
the best tour costs 22 or less
from “The Nearest-Neighbor Upper Bound”
The tour starts at B. Which town comes next?
A
from “The Nearest-Neighbor Upper Bound”
Vertex B is deleted. What is the weight of the minimum spanning tree of the rest?
14
from “The Deleted-Vertex Lower Bound”
What do the two cheapest roads at C come to?
6
from “The Deleted-Vertex Lower Bound”