- Asked 2/14
- 2068 Bhadra · 6 marks
Transitive closure of 4-vertex graph (Warshall)
Short answer
Using Warshall's algorithm, the transitive closure adds edges: a→a, a→c, a→d; b→a, b→c, b→d; c→a, c→c, c→d; d→a, d→c, d→d. No vertex reaches b.
Let G = (V, E) with V = {a, b, c, d} and E = {(a,d), (b,a), (b,c), (c,a), (c,d), (d,c)} be a directed graph. Find the transitive closure of G using Warshall's algorithm, showing each iterations.
Warshall's algorithm: for k = a, b, c, d in turn, set P[i][j] = P[i][j] OR (P[i][k] AND P[k][j]). That is, if i reaches k and k reaches j, then i reaches j.
Vertices in order a, b, c, d. Edges: a→d, b→a, b→c, c→a, c→d, d→c.
P₀ (adjacency matrix)
| a | b | c | d | |
|---|---|---|---|---|
| a | 0 | 0 | 0 | 1 |
| b | 1 | 0 | 1 | 0 |
| c | 1 | 0 | 0 | 1 |
| d | 0 | 0 | 1 | 0 |
Iteration k = a (vertices with an edge into a: b, c; a's row has d): b→d added; c→d already present.
| a | b | c | d | |
|---|---|---|---|---|
| a | 0 | 0 | 0 | 1 |
| b | 1 | 0 | 1 | 1 |
| c | 1 | 0 | 0 | 1 |
| d | 0 | 0 | 1 | 0 |
Iteration k = b (no edge enters b): no change.
Iteration k = c (into c: b, d; c's row has a, d): b already has a, d; d gains a and d.
| a | b | c | d | |
|---|---|---|---|---|
| a | 0 | 0 | 0 | 1 |
| b | 1 | 0 | 1 | 1 |
| c | 1 | 0 | 0 | 1 |
| d | 1 | 0 | 1 | 1 |
Iteration k = d (into d: a, b, c, d; d's row has a, c, d): every row gains a, c, d.
Transitive closure P₄
| a | b | c | d | |
|---|---|---|---|---|
| a | 1 | 0 | 1 | 1 |
| b | 1 | 0 | 1 | 1 |
| c | 1 | 0 | 1 | 1 |
| d | 1 | 0 | 1 | 1 |
Answer: closure edges are a→a, a→c, a→d; b→a, b→c, b→d; c→a, c→c, c→d; d→a, d→c, d→d. No vertex reaches b, because b has no incoming edge.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Transitive closure of 5-vertex graph (Warshall) · Data Structure and Algorithm, chapter 10 · asked 2×