GraphTheory - Maple Programming Help

# Online Help

###### All Products    Maple    MapleSim

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/TransitiveClosure

GraphTheory

 TransitiveClosure
 construct transitive closure

 Calling Sequence TransitiveClosure( G ) TransitiveClosure( G, opts )

Parameters

 G - a graph opts - (optional) weighted=true or weighted=false

Options

 • weighted=true or false
 Specifies whether the resulting graph should have edge weights corresponding to the weighted length of the shortest path in the input graph. The default is false, meaning the graph is unweighted.

Description

 • The TransitiveClosure( G ) command constructs the graph which is the transitive closure of the graph G with respect to the edge relation.
 • The transitive closure of an undirected graph G is a undirected graph with the same vertices as G in which there is an edge between distinct vertices u and v whenever there is a path between u and v in G.
 • Similarly, the transitive closure of a directed graph G is a directed graph with same vertices as G, in which there is an arc from vertex u to vertex v whenever there is a directed path from u to v in G.
 • The transitive closure of a connected undirected graph will always be the complete graph on the vertices of the input graph.

Examples

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

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

Construct the transitive closure graph with edge weights corresponding to the path lengths in the original graph. For example, because the shortest path in G from 1 to 5 has 3 steps (1→2→4→5), the arc in TCW has weight 3.

 > $\mathrm{TCW}≔\mathrm{TransitiveClosure}\left(G,\mathrm{weighted}=\mathrm{true}\right)$
 ${\mathrm{TCW}}{≔}{\mathrm{Graph 3: a directed weighted graph with 6 vertices and 8 arc\left(s\right)}}$ (3)
 > $\mathrm{DrawGraph}\left(\mathrm{TCW},\mathrm{showweights},\mathrm{style}=\mathrm{circle}\right)$
 > 

Compatibility

 • The GraphTheory[TransitiveClosure] command was introduced in Maple 2016.
 • For more information on Maple 2016 changes, see Updates in Maple 2016.

 See Also