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

GraphTheory

 IsConnected
 test if graph is connected
 ConnectedComponents
 compute connected components of graph

 Calling Sequence IsConnected(G) ConnectedComponents(G)

Parameters

 G - graph

Description

 • IsConnected returns true if the input graph is a connected graph or false otherwise. If G is a directed graph then the directions of edges are ignored. Use the IsStronglyConnected command to test whether each pair of vertices is connected by a directed path.
 • ConnectedComponents returns the components of the graph as a list of lists of vertices.  Each sublist is a list of vertices for a connected component.

Definition

 • A graph G is connected if for each pair of vertices u and v in G there exists a path from u to v in G (if G is undirected), or in the underlying graph of G (if G is directed).

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$
 > $G≔\mathrm{CycleGraph}\left(4\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected graph with 4 vertices and 4 edge\left(s\right)}}$ (1)
 > $\mathrm{IsConnected}\left(G\right)$
 ${\mathrm{true}}$ (2)
 > $H≔\mathrm{GraphComplement}\left(G\right)$
 ${H}{≔}{\mathrm{Graph 2: an undirected graph with 4 vertices and 2 edge\left(s\right)}}$ (3)
 > $\mathrm{IsConnected}\left(H\right)$
 ${\mathrm{false}}$ (4)
 > $\mathrm{ConnectedComponents}\left(H\right)$
 $\left[\left[{1}{,}{3}\right]{,}\left[{2}{,}{4}\right]\right]$ (5)
 > $\mathrm{DrawGraph}\left(H\right)$
 > $G≔\mathrm{Graph}\left(\left[1,2,3,4,5,6\right],\left\{\left\{1,2\right\},\left\{2,3\right\},\left\{4,5\right\}\right\}\right)$
 ${G}{≔}{\mathrm{Graph 3: an undirected graph with 6 vertices and 3 edge\left(s\right)}}$ (6)
 > $\mathrm{IsConnected}\left(G\right)$
 ${\mathrm{false}}$ (7)
 > $\mathrm{ConnectedComponents}\left(G\right)$
 $\left[\left[{1}{,}{2}{,}{3}\right]{,}\left[{4}{,}{5}\right]{,}\left[{6}\right]\right]$ (8)
 > $G≔\mathrm{OctahedronGraph}\left(\right)$
 ${G}{≔}{\mathrm{Graph 4: an undirected graph with 6 vertices and 12 edge\left(s\right)}}$ (9)
 > $\mathrm{ConnectedComponents}\left(G\right)$
 $\left[\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}{,}{6}\right]\right]$ (10)
 > $H≔\mathrm{GraphComplement}\left(G\right)$
 ${H}{≔}{\mathrm{Graph 5: an undirected graph with 6 vertices and 3 edge\left(s\right)}}$ (11)
 > $\mathrm{IsConnected}\left(H\right)$
 ${\mathrm{false}}$ (12)
 > $\mathrm{ConnectedComponents}\left(H\right)$
 $\left[\left[{1}{,}{2}\right]{,}\left[{3}{,}{4}\right]{,}\left[{5}{,}{6}\right]\right]$ (13)
 > $\mathrm{DrawGraph}\left(G\right)$
 > $\mathrm{DrawGraph}\left(H\right)$