GraphTheory - Maple Programming Help

# Online Help

###### All Products    Maple    MapleSim

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

GraphTheory

 IsBiconnected
 BiconnectedComponents
 Blocks

 Calling Sequence IsBiconnected(G) BiconnectedComponents(G) Blocks(G)

Parameters

 G - undirected unweighted graph

Description

 • A graph G is bi-connected or 2-connected if it is connected and removal of any vertex from G does not disconnect G.  A maximal bi-connected subgraph of G is called a bi-connected component or block of G.
 • The IsBiconnected command returns true if the input graph is bi-connected. It returns false otherwise.
 • The Blocks and BiconnectedComponents commands return a list the vertices of all blocks of the graph.  The InducedSubgraph command can be used to extract the blocks of the graph as separate subgraphs.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $G≔\mathrm{Graph}\left(\mathrm{Trail}\left(1,2,3,4,2\right),\mathrm{Trail}\left(4,5,6,7,5\right)\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 7 vertices and 8 edge\left(s\right)}}$ (1)
 > $\mathrm{DrawGraph}\left(G\right)$
 > $\mathrm{IsBiconnected}\left(G\right)$
 ${\mathrm{false}}$ (2)

The two triangles in G and the two edges {1,2} and {4,5} are the blocks in G.

 > $\mathrm{Blocks}\left(G\right)$
 $\left[\left[{5}{,}{6}{,}{7}\right]{,}\left[{4}{,}{5}\right]{,}\left[{2}{,}{3}{,}{4}\right]{,}\left[{1}{,}{2}\right]\right]$ (3)
 > $\mathrm{ArticulationPoints}\left(G\right)$
 $\left[{2}{,}{4}{,}{5}\right]$ (4)
 > $\mathrm{seq}\left(\mathrm{IsBiconnected}\left(\mathrm{InducedSubgraph}\left(G,B\right)\right),B=\mathrm{Blocks}\left(G\right)\right)$
 ${\mathrm{true}}{,}{\mathrm{true}}{,}{\mathrm{true}}{,}{\mathrm{true}}$ (5)

References

 Hopcroft and Tarjan, "Efficient algorithms for graph manipulation", CACM. Vol. 16:372-378, 1973. doi:10.1145/362248.362272
 "Biconnected component", Wikipedia. http://en.wikipedia.org/wiki/Biconnected_component

 See Also