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

GraphTheory

 IsStronglyConnected
 test if graph is strongly connected
 StronglyConnectedComponents
 compute strongly connected components of graph

 Calling Sequence IsStronglyConnected(G) StronglyConnectedComponents(G, sortoption)

Parameters

 G - graph sortoption - (optional) equation of the form sorted=true or false

Description

 • IsStronglyConnected('G') returns true if the input graph G is a strongly connected graph and returns false otherwise.
 • StronglyConnectedComponents(G) command computes the maximal subgraphs of G which are strongly connected.  It returns them as a list of lists of vertices where the number of lists indicates the number of strongly connected components.
 • By default the result is sorted by size of the subgraph. The optional parameter sorted=false can be used to preserve the order as computed by the algorithm.

Definition

 • A graph G is strongly connected if for each vertex u in G there is a path to every other vertex in G. Note that a graph with fewer than two vertice is trivially strongly connected.
 • If G is an undirected graph, then being strongly connected is equivalent to being connected.
 • An example of a strongly connected graph is the directed cycle graph.

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{IsStronglyConnected}\left(T\right)$
 ${\mathrm{false}}$ (3)
 > $\mathrm{ConnectedComponents}\left(T\right)$
 $\left[\left[{1}{,}{2}{,}{3}\right]\right]$ (4)
 > $\mathrm{StronglyConnectedComponents}\left(T\right)$
 $\left[\left[{1}\right]{,}\left[{2}{,}{3}\right]\right]$ (5)
 > $\mathrm{IsStronglyConnected}\left(\mathrm{Digraph}\left(\mathrm{Trail}\left(1,2,3,4,5\right)\right)\right)$
 ${\mathrm{false}}$ (6)
 > $\mathrm{IsStronglyConnected}\left(\mathrm{Digraph}\left(\mathrm{Trail}\left(1,2,3,4,5,1\right)\right)\right)$
 ${\mathrm{true}}$ (7)
 > $G≔\mathrm{Digraph}\left(\left\{\left[1,2\right],\left[2,3\right],\left[3,4\right]\right\}\right)$
 ${G}{≔}{\mathrm{Graph 2: a directed graph with 4 vertices and 3 arc\left(s\right)}}$ (8)
 > $\mathrm{StronglyConnectedComponents}\left(G\right)$
 $\left[\left[{4}\right]{,}\left[{3}\right]{,}\left[{2}\right]{,}\left[{1}\right]\right]$ (9)
 > $\mathrm{AddArc}\left(G,\left[4,3\right]\right)$
 ${\mathrm{Graph 2: a directed graph with 4 vertices and 4 arc\left(s\right)}}$ (10)
 > $\mathrm{StronglyConnectedComponents}\left(G\right)$
 $\left[\left[{2}\right]{,}\left[{1}\right]{,}\left[{3}{,}{4}\right]\right]$ (11)
 > $\mathrm{DrawGraph}\left(G\right)$
 > $\mathrm{AddArc}\left(G,\left[4,2\right]\right)$
 ${\mathrm{Graph 2: a directed graph with 4 vertices and 5 arc\left(s\right)}}$ (12)
 > $\mathrm{StronglyConnectedComponents}\left(G\right)$
 $\left[\left[{1}\right]{,}\left[{2}{,}{3}{,}{4}\right]\right]$ (13)