Past exam question: 2066 Jestha (Back), Q10(b)
Open in the Padhaiko appQuestion
Write short notes on: b) Transitive Closure Graph
Solution
Transitive Closure of a Directed Graph: Given a directed graph , its transitive closure is a directed graph (often represented as an reachability matrix ) such that there is a directed edge (i.e., ) if and only if there exists a directed path of length from vertex to vertex in .
- Computation: Computed in time using Warshall's algorithm: .
- Applications: Dependency resolution, reachability queries in networks, and cycle detection ().
Answer:
The transitive closure connects whenever is reachable from via one or more directed edges in , computed in time by Warshall's algorithm.