TransitiveClosureGraph

TransitiveClosureGraph[g]

gives the transitive closure of the graph g.

TransitiveClosureGraph[{vw,}]

uses rules vw to specify the graph g.

Details and Options

Examples

open allclose all

Basic Examples  (1)

The transitive closure of a graph:

Highlight the original graph within its transitive closure:

Scope  (5)

TransitiveClosureGraph works with undirected graphs:

Directed graphs:

Multigraphs:

Use rules to specify the graph:

TransitiveClosureGraph works with large graphs:

Options  (3)

Method  (3)

The method is automatically chosen depending on input:

"Warshall" and "Warren" methods can be used for dense graphs:

"Purdom" can be used for directed acyclic graphs:

Applications  (2)

Find species in the food chain that would be affected if beetles were extinct:

Give a divisibility tree and find all divisors for each number:

Properties & Relations  (6)

The transitive closure graph has the same vertices as the original graph:

An edge uv is in the closure graph if there is a path from u to v in the original graph:

There is a path from 1 to 6 in the given graph, by no direct edge:

There is a direct edge 16 in the transitive closure:

The transitive closure of a connected undirected graph is a complete graph:

Using transitive closure to find the reachability of each vertex in the graph:

TransitiveClosureGraph can be computed using GraphPower:

The transitive closure is the same for a graph and its transitive reduction:

Introduced in 2014
 (10.0)
 |
Updated in 2015
 (10.3)