PadhaikoAll subjects

Past exam question: 2079 Ashwin (Back), Q12(a)

Data Structure and Algorithms · 2 marks

Open in the Padhaiko app

Topic: Graphs

Question

Explain the concept of transitive closure.

Solution

Formal Definition of Transitive Closure: Given a directed graph with vertices, the transitive closure of is a boolean relation represented as an matrix (often called the reachability matrix) where:

While the standard adjacency matrix indicates only direct edges (paths of length 1), the transitive closure reflects all reachability across any sequence of intermediate vertices:

where matrix multiplication and addition are computed using boolean () and () operations.

Key Properties and Real-World Applications:

Answer:

The transitive closure of a directed graph is an boolean reachability matrix where if there exists any directed path from vertex to vertex , and otherwise. It answers all-pairs reachability questions in lookup time.

All past exam questions for Data Structure and Algorithms