TransitiveReductionGraph

TransitiveReductionGraph[g]

gives a transitive reduction of the graph g.

TransitiveReductionGraph[{vw,…}]

uses rules vw to specify the graph g.

Details and Options

Examples

open allclose all

Basic Examples  (1)

The transitive reduction of a graph:

Highlight the graph:

Scope  (5)

TransitiveReductionGraph works with undirected graphs:

Directed graphs:

Multigraphs:

Use rules to specify the graph:

TransitiveReductionGraph works with large graphs:

Applications  (2)

Build an interstate highway system linking all African countries. From a network joining geographic centers of bordering countries, minimize the number of highways and preserve reachability relation:

Minimize the number of highways:

Highlight the interstate highway system:

Build the genealogy tree of a family from its age relation graph:

The genealogy tree:

Properties & Relations  (3)

The transitive reduction of a graph g has the same transitive closure as the graph g:

The transitive reduction of g:

The transitive closure of g and h:

TransitiveReductionGraph[g] has the same vertices as g:

The transitive reduction of an undirected graph is a tree:

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

Text

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

CMS

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

APA

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

BibTeX

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

BibLaTeX

@online{reference.wolfram_2022_transitivereductiongraph, organization={Wolfram Research}, title={TransitiveReductionGraph}, year={2015}, url={https://reference.wolfram.com/language/ref/TransitiveReductionGraph.html}, note=[Accessed: 01-April-2023 ]}