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

Parameters

Options

Description

Examples

Compatibility

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.

withGraphTheory:

GGraph6,1,2,2,3,2,4,4,5

GGraph 1: a directed unweighted graph with 6 vertices and 4 arc(s)

(1)

HTransitiveClosureG

HGraph 2: a directed unweighted graph with 6 vertices and 8 arc(s)

(2)

DrawGraphG,H,style=circle

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.

TCWTransitiveClosureG,weighted=true

TCWGraph 3: a directed weighted graph with 6 vertices and 8 arc(s)

(3)

DrawGraphTCW,showweights,style=circle

Compatibility

• 

The GraphTheory[TransitiveClosure] command was introduced in Maple 2016.

• 

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

See Also

GraphTheory

GraphTheory[AllPairsDistance]

GraphTheory[ReverseGraph]

GraphTheory[TransitiveReduction]