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

Parameters

Description

Examples

References

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

withGraphTheory:

GGraphTrail1,2,3,4,2,Trail4,5,6,7,5

GGraph 1: an undirected unweighted graph with 7 vertices and 8 edge(s)

(1)

DrawGraphG

IsBiconnectedG

false

(2)

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

BlocksG

5,6,7,4,5,2,3,4,1,2

(3)

ArticulationPointsG

2,4,5

(4)

seqIsBiconnectedInducedSubgraphG,B,B=BlocksG

true,true,true,true

(5)

References

  

Hopcroft and Tarjan, "Efficient algorithms for graph manipulation," CACM. Vol. 16:372-378, 1973.

See Also

ArticulationPoints

IsConnected

IsTwoEdgeConnected

Trail