({{, (RefLink[TransitiveReductionGraph, paclet:ref/TransitiveReductionGraph])[g] 
gives a transitive reduction of the graph g.}, {, (RefLink[TransitiveReductionGraph, paclet:ref/TransitiveReductionGraph])[{v->w,…}]
uses rules v->w to specify the graph g. }})

OpenersNotesSection(Spacer1)Details and Options

(RefLink[TransitiveReductionGraph, paclet:ref/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.

(RefLink[TransitiveReductionGraph, paclet:ref/TransitiveReductionGraph]) takes the same options as (RefLink[Graph, paclet:ref/Graph]).

(RefLink[TransitiveReductionGraph, paclet:ref/TransitiveReductionGraph]) works with undirected graphs, directed graphs, and multigraphs.

OpenersPrimaryExamplesSection(Spacer1)Examples  (11)

OpenersExampleSection0(Spacer1)Basic Examples  (1)

The transitive reduction of a graph:

g=Graph[{1\[DirectedEdge]2,1\[DirectedEdge]3,1\[DirectedEdge]4,1\[DirectedEdge]5,3\[DirectedEdge]4,3\[DirectedEdge]5,2\[DirectedEdge]4,4\[DirectedEdge]5}];

TransitiveReductionGraph[g]

Highlight the graph:

HighlightGraph[g,%,GraphHighlightStyle->"Thick"]

OpenersExampleSection1(Spacer1)Scope  (5)

(RefLink[TransitiveReductionGraph, paclet:ref/TransitiveReductionGraph]) works with undirected graphs:

TransitiveReductionGraph[]

Directed graphs:

TransitiveReductionGraph[]

Multigraphs:

TransitiveReductionGraph[]

Use rules to specify the graph:

TransitiveReductionGraph[{1->2,1->5,2->3,3->4,4->5,3->6,4->6}]

(RefLink[TransitiveReductionGraph, paclet:ref/TransitiveReductionGraph]) works with large graphs:

g=GridGraph[{10,10,10,10},DirectedEdges->True];

Timing[TransitiveReductionGraph[g];]

OpenersExampleSection3(Spacer1)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:

g=;

Minimize the number of highways:

TransitiveReductionGraph[g]

Highlight the interstate highway system:

HighlightGraph[g,%]

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

g=;

The genealogy tree:

TransitiveReductionGraph[g,VertexShapeFunction->"Name",GraphLayout->{"LayeredEmbedding", "RootVertex"->"James"}]

OpenersExampleSection4(Spacer1)Properties & Relations  (3)

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

g=;

The transitive reduction of g:

h =TransitiveReductionGraph[g]

The transitive closure of g and h:

{TransitiveClosureGraph[g],TransitiveClosureGraph[h]}

SameQ @@ %

(RefLink[TransitiveReductionGraph, paclet:ref/TransitiveReductionGraph])[g] has the same vertices as g:

g=CycleGraph[4];

VertexList[TransitiveReductionGraph[g]]==VertexList[g]

The transitive reduction of an undirected graph is a tree:

TransitiveReductionGraph[]

TreeGraphQ[%]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[TransitiveClosureGraph, paclet:ref/TransitiveClosureGraph])  ▪  (RefLink[BooleanMinimize, paclet:ref/BooleanMinimize])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Graph Operations and Modifications, paclet:guide/GraphModifications])}})}})