ArticulationPoints - Maple Help

# Online Help

###### All Products    Maple    MapleSim

GraphTheory

 ArticulationPoints
 compute list of articulation points

 Calling Sequence ArticulationPoints(G)

Parameters

 G - undirected graph

Description

 • A vertex v in a graph G is an articulation point of G if removing it and its incident edges increases the number of connected components of G.
 • ArticulationPoints(G) returns a list of the vertices of G which are articulation points.
 • The articulation points of a graph can be computed when traversing the graph using depth-first-search in linear time in the size of the graph.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{P5}≔\mathrm{PathGraph}\left(5\right)$
 ${\mathrm{P5}}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 5 vertices and 4 edge\left(s\right)}}$ (1)
 > $\mathrm{ArticulationPoints}\left(\mathrm{P5}\right)$
 $\left[{2}{,}{3}{,}{4}\right]$ (2)
 > $\mathrm{numelems}\left(\mathrm{ConnectedComponents}\left(\mathrm{P5}\right)\right)$
 ${1}$ (3)
 > $G≔\mathrm{DeleteVertex}\left(\mathrm{P5},3\right)$
 ${G}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 4 vertices and 2 edge\left(s\right)}}$ (4)
 > $\mathrm{numelems}\left(\mathrm{ConnectedComponents}\left(G\right)\right)$
 ${2}$ (5)
 > $\mathrm{C5}≔\mathrm{CycleGraph}\left(5\right)$
 ${\mathrm{C5}}{≔}{\mathrm{Graph 3: an undirected unweighted graph with 5 vertices and 5 edge\left(s\right)}}$ (6)
 > $\mathrm{ArticulationPoints}\left(\mathrm{C5}\right)$
 $\left[\right]$ (7)

 See Also