Condensation - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

# Online Help

###### All Products    Maple    MapleSim

GraphTheory

 Condensation
 condense graph to its strongly connected components

 Calling Sequence Condensation(G)

Parameters

 G - graph

Description

 • Condensation(G) returns the condensation of G.
 • The vertices of the resulting graph are integers corresponding to the index of the strongly connected component returned by StronglyConnectedComponents.

Definition

 • The condensation of a graph G is a graph C whose vertices correspond to the strongly connected components of G. An edge exists in C from u to v if there exists an edge from a to b in G for a a vertex in the strongly connected component corresponding to u, and b a vertex in the strongly connected component corresponding to v.
 • Note if G is undirected, the condensation has no edges. This operation is therefore generally most interesting for directed graphs.

Examples

The graph below is connected but not strongly connected since vertex 1 is not reachable from vertices 2 or 3.

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $T≔\mathrm{Digraph}\left(\left[1,2,3\right],\left\{\left[1,2\right],\left[1,3\right],\left[2,3\right],\left[3,2\right]\right\}\right)$
 ${T}{≔}{\mathrm{Graph 1: a directed graph with 3 vertices and 4 arc\left(s\right)}}$ (1)
 > $\mathrm{DrawGraph}\left(T\right)$
 > $\mathrm{IsConnected}\left(T\right)$
 ${\mathrm{true}}$ (2)
 > $\mathrm{Condensation}\left(T\right)$
 ${\mathrm{Graph 2: a directed graph with 2 vertices and 1 arc\left(s\right)}}$ (3)
 > $G≔\mathrm{Digraph}\left(\left\{\left[1,2\right],\left[2,3\right],\left[3,4\right]\right\}\right)$
 ${G}{≔}{\mathrm{Graph 3: a directed graph with 4 vertices and 3 arc\left(s\right)}}$ (4)
 > $\mathrm{Condensation}\left(G\right)$
 ${\mathrm{Graph 4: a directed graph with 4 vertices and 3 arc\left(s\right)}}$ (5)

Compatibility

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

 See Also