test if graph is strongly connected
compute strongly connected components of graph
(optional) equation of the form sorted=true or false
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.
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.
The graph below is connected but not strongly connected since vertex 1 is not reachable from vertices 2 or 3.
T ≔ Digraph⁡1,2,3,1,2,1,3,2,3,3,2
T≔Graph 1: a directed graph with 3 vertices and 4 arc(s)
G ≔ Digraph⁡1,2,2,3,3,4
G≔Graph 2: a directed graph with 4 vertices and 3 arc(s)
Graph 2: a directed graph with 4 vertices and 4 arc(s)
Graph 2: a directed graph with 4 vertices and 5 arc(s)
Download Help Document