TransitiveReductionGraph
gives a transitive reduction of the graph g.
TransitiveReductionGraph[{vw,…}]
uses rules vw to specify the graph g.
Details and Options

- TransitiveReductionGraph is also known as minimum equivalent graph.
- The transitive reduction h of a graph g is a graph that has the same transitive closure as g, with a minimal number of edges.
- TransitiveReductionGraph takes the same options as Graph.
- TransitiveReductionGraph works with undirected graphs, directed graphs, and multigraphs.
Examples
open allclose allScope (5)
TransitiveReductionGraph works with undirected graphs:
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:
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:
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