TransitiveReduction - Maple Help

GraphTheory

 TransitiveReduction
 construct transitive reduction

 Calling Sequence TransitiveReduction( G )

Parameters

 G - a graph

Description

 • The TransitiveReduction( G ) command constructs the graph which is the transitive reduction of the graph G with respect to the edge relation.
 • The transitive reduction of an graph G is a undirected graph which has the same vertex set and transitive closure as G, but with a minimal number of edges.

Examples

Construct the transitive reduction graph of a simple directed graph and visualize the two graphs.

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $G≔\mathrm{Graph}\left(4,\left\{\left[1,2\right],\left[1,4\right],\left[2,3\right],\left[3,4\right]\right\}\right)$
 ${G}{≔}{\mathrm{Graph 1: a directed unweighted graph with 4 vertices and 4 arc\left(s\right)}}$ (1)
 > $H≔\mathrm{TransitiveReduction}\left(G\right)$
 ${H}{≔}{\mathrm{Graph 2: a directed unweighted graph with 4 vertices and 3 arc\left(s\right)}}$ (2)
 > $\mathrm{DrawGraph}\left(\left[G,H\right],\mathrm{style}=\mathrm{circle}\right)$

 > 

Compatibility

 • The GraphTheory[TransitiveReduction] command was introduced in Maple 2019.