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.

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.

$\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(s)}$

$\mathrm{DrawGraph}\left(T\right)$

$\mathrm{IsConnected}\left(T\right)$

$\mathrm{true}$

$\mathrm{Condensation}\left(T\right)$

$\mathrm{Graph\; 2:\; a\; directed\; graph\; with\; 2\; vertices\; and\; 1\; arc(s)}$

$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(s)}$

$\mathrm{Condensation}\left(G\right)$

$\mathrm{Graph\; 4:\; a\; directed\; graph\; with\; 4\; vertices\; and\; 3\; arc(s)}$

The GraphTheory[Condensation] command was introduced in Maple 2024.

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