GraphTheory[ArticulationPoints] - Maple Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory[ArticulationPoints]

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

withGraphTheory:

P5:=PathGraph5

P5:=Graph 1: an undirected unweighted graph with 5 vertices and 4 edge(s)

(1)

ArticulationPointsP5

2,3,4

(2)

numelemsConnectedComponentsP5

1

(3)

G:=DeleteVertexP5,3:

numelemsConnectedComponentsG

2

(4)

C5:=CycleGraph5

C5:=Graph 3: an undirected unweighted graph with 5 vertices and 5 edge(s)

(5)

ArticulationPointsC5

(6)

See Also

BiconnectedComponents, IsBiconnected, IsConnected, VertexConnectivity


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam