GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

IsStronglyConnected

  

StronglyConnectedComponents

 

Calling Sequence

Parameters

Description

Examples

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.

withGraphTheory:

TDigraph1,2,3,1,2,1,3,2,3,3,2

TGraph 1: a directed unweighted graph with 3 vertices and 4 arc(s)

(1)

DrawGraphT

IsConnectedT

true

(2)

IsStronglyConnectedT

false

(3)

ConnectedComponentsT

1,2,3

(4)

StronglyConnectedComponentsT

1,2,3

(5)

IsStronglyConnectedDigraphTrail1,2,3,4,5

false

(6)

IsStronglyConnectedDigraphTrail1,2,3,4,5,1

true

(7)

GDigraph1,2,2,3,3,4

GGraph 2: a directed unweighted graph with 4 vertices and 3 arc(s)

(8)

StronglyConnectedComponentsG

4,3,2,1

(9)

AddArcG,4,3

Graph 2: a directed unweighted graph with 4 vertices and 4 arc(s)

(10)

StronglyConnectedComponentsG

2,1,3,4

(11)

DrawGraphG

AddArcG,4,2

Graph 2: a directed unweighted graph with 4 vertices and 5 arc(s)

(12)

StronglyConnectedComponentsG

1,2,3,4

(13)

See Also

ConnectedComponents

Digraph

IsConnected

Trail