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:

Wolfram Research (2014), TransitiveClosureGraph, Wolfram Language function, https://reference.wolfram.com/language/ref/TransitiveClosureGraph.html (updated 2015).

Text

Wolfram Research (2014), TransitiveClosureGraph, Wolfram Language function, https://reference.wolfram.com/language/ref/TransitiveClosureGraph.html (updated 2015).

CMS

Wolfram Language. 2014. "TransitiveClosureGraph." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/TransitiveClosureGraph.html.

APA

Wolfram Language. (2014). TransitiveClosureGraph. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/TransitiveClosureGraph.html

BibTeX

@misc{reference.wolfram_2022_transitiveclosuregraph, author="Wolfram Research", title="{TransitiveClosureGraph}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/TransitiveClosureGraph.html}", note=[Accessed: 31-May-2023 ]}

BibLaTeX

@online{reference.wolfram_2022_transitiveclosuregraph, organization={Wolfram Research}, title={TransitiveClosureGraph}, year={2015}, url={https://reference.wolfram.com/language/ref/TransitiveClosureGraph.html}, note=[Accessed: 31-May-2023 ]}