Skip to main content

Spanning tree properties; Round Robin MST

Short answer

A spanning tree has V-1 edges and is connected and acyclic. Using Round Robin, the MST edges are a-d (2), c-d (4), d-e (4), b-e (5) with total cost 15.

Write two properties of spanning tree. Find MST of graph-1 using Round Robin Algorithm. [Figure: graph-1, undirected weighted graph on vertices a, b, c, d, e with edges a-b 9, a-d 2, b-d 6, a-c 5, c-d 4, d-e 4, b-e 5, c-e 5]

Two properties of a spanning tree

  1. A spanning tree of a connected graph with V vertices contains exactly V−1 edges and all V vertices.
  2. It is connected and acyclic: there is exactly one path between any two vertices, and adding any non-tree edge creates exactly one cycle.

(Also: removing any edge disconnects it; a graph can have many spanning trees.)

MST of graph-1 by Round Robin

Round Robin algorithm (Yao / Cheriton-Tarjan) builds an MST by merging trees. Start with every vertex as a separate tree placed in a queue. Repeat: remove the tree T at the front, find the minimum-weight edge leaving T, merge T with the tree at the other end of that edge (remove that tree from the queue), and add the merged tree to the rear. Stop when one tree remains.

Edges: a-b 9, a-d 2, b-d 6, a-c 5, c-d 4, d-e 4, b-e 5, c-e 5. Initial queue: [a] [b] [c] [d] [e].

StepTree takenCheapest edge leaving itMergeQueue after
1{a}a-d (2)with {d}[b] [c] [e] [a,d]
2{b}b-e (5)with {e}[c] [a,d] [b,e]
3{c}c-d (4)with {a,d}[b,e] [a,c,d]
4{b,e}d-e (4)with {a,c,d}[a,b,c,d,e]

One tree remains.

MST edges: a-d (2), c-d (4), b-e (5), d-e (4). Minimum cost = 2 + 4 + 5 + 4 = 15.

a --2-- d --4-- c
        |
        4
        |
        e --5-- b

The result equals the Kruskal result (15).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 10 questions →