Online Help

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 undirected graph G is an undirected graph which has the same vertex set and transitive closure as G, but with a minimal number of edges.

Similarly, the transitive reduction of a directed graph G is a directed graph which has the same vertex set and transitive closure as G, but with a minimal number of arcs.

$\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\; graph\; with\; 4\; vertices\; and\; 4\; arcs}$

$H≔\mathrm{TransitiveReduction}\left(G\right)$

$H≔\mathrm{Graph\; 2:\; a\; directed\; graph\; with\; 4\; vertices\; and\; 3\; arcs}$

$\mathrm{DrawGraph}\left(\left[G\,H\right]\,\mathrm{style}=\mathrm{circle}\right)$

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

For more information on Maple 2019 changes, see Updates in Maple 2019 .