GraphTheory - Maple Programming Help

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

GraphTheory

 IsConnected
 ConnectedComponents

 Calling Sequence IsConnected(G) ConnectedComponents(G)

Parameters

 G - graph

Description

 • 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).
 • 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.

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