GraphTheory - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/IsStronglyConnected

GraphTheory

 IsStronglyConnected
 StronglyConnectedComponents

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

Parameters

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

Description

 • A graph G is strongly connected if for each vertex u in G there is a path to every other vertex in G.  Note: a graph with one vertex is 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.
 • The IsStronglyConnected('G') function returns true if the input graph is a strongly connected graph. It returns false otherwise.
 • The StronglyConnectedComponents 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.

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 unweighted 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 unweighted 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 unweighted 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 unweighted 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)