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.
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 tree that includes every vertex of the network, using some of its arcs.
- How many arcs does a spanning tree of vertices have?
- .
- What is the minimum spanning tree (minimum connector)?
- The spanning tree with the smallest total weight.
- State the steps of Kruskal's algorithm.
- Sort arcs by increasing weight, then add each arc unless it forms a cycle, until arcs are chosen.
- When do you reject an arc in Kruskal's algorithm?
- When its two ends are already connected, so adding it would form a cycle.
- State the steps of Prim's algorithm.
- Start at any vertex, then repeatedly add the smallest arc joining the tree to a new vertex.
- What is the main difference between Prim's and Kruskal's algorithms?
- Prim's grows one connected tree from a start vertex; Kruskal's picks the smallest arcs anywhere, joining separate pieces.
- Which algorithm needs no cycle check?
- Prim's, because it only ever adds a new vertex.
- How do you start Prim's algorithm on a matrix?
- Label the starting vertex's column 1 and delete its row.
- Why is a distance matrix symmetrical?
- The arc has the same weight as , so each arc appears twice.
- A matrix has 14 non-blank entries. How many arcs?
- , since each arc is entered twice.
- Can a network have more than one MST?
- Yes, if arcs have equal weights, but every MST has the same total weight.