construct transitive closure
TransitiveClosure( G )
TransitiveClosure( G, opts )
(optional) weighted=true or weighted=false
weighted=true, false, or FAIL
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 FAIL, meaning the graph is weighted if and only if the input graph is weighted.
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.
Construct the transitive closure graph of a simple directed graph and visualize the two graphs.
G ≔ Graph⁡6,1,2,2,3,2,4,4,5
G≔Graph 1: a directed graph with 6 vertices and 4 arc(s)
H ≔ TransitiveClosure⁡G
H≔Graph 2: a directed graph with 6 vertices and 8 arc(s)
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.
TCW ≔ TransitiveClosure⁡G,weighted=true
TCW≔Graph 3: a directed weighted graph with 6 vertices and 8 arc(s)
The GraphTheory[TransitiveClosure] command was introduced in Maple 2016.
For more information on Maple 2016 changes, see Updates in Maple 2016.
Download Help Document