Transitive Closure and Transitive ReductionWhat is the Transitive Closure of a Graph?The transitive closure of a directed graphG=(V,E) is a graph
H=(V,F) with edge (v,w) in F if and only if there
is a path from v to w in G .
Where can I use Transitive Closure?It is very easy to check if there is a path from a node Transitive ReductionBesides functions to compute the transitive closure of a graph, LEDA
also offers functions to compute the transitive reduction of a graph.
The transitive reduction of a directed graph Notice that transitive closure and transitive reduction are not exact reversals of each other. If I compute the transitive closure H of a graph G and then compute the transitive reduction G' of H, G' may be a subgraph of G. Example for transitive closure and transitive reduction Running TimeThe running time for transitive closure and transitive reduction is O(|V||E|). |
See also:GraphWin for visualizing graphs and graph algorithms Manual Entries: |