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:

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