GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

ArticulationPoints

 

Calling Sequence

Parameters

Description

Examples

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:

P5PathGraph5

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

(1)

ArticulationPointsP5

2,3,4

(2)

numelemsConnectedComponentsP5

1

(3)

GDeleteVertexP5,3

G:=Graph 2: an undirected unweighted graph with 4 vertices and 2 edge(s)

(4)

numelemsConnectedComponentsG

2

(5)

C5CycleGraph5

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

(6)

ArticulationPointsC5

(7)

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