This

**preview**shows pages 1-3. to view the full**27 pages of the document.**1

Articulations

•Definition:

•A node vof a connected graph Gis an

articulation node (also called a cut vertex) if the

removal of vand all its incident edges causes Gto

become disconnected.

•Motivation for articulations:

•Articulations are important in communication

networks.

•In traffic flows they identify places that will stop

traffic between two areas of a city if they become

blocked.

Finding Articulations (1)

•Problem:

•Given any graph G= (V, E), find all the

articulation points.

•Possible strategy:

• For all vertices vin V:

Remove vand its incident edges.

Test connectivity using a DFS.

• Execution time: Θ(n(n + m)).

– Can we do better?

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

2

Finding Articulations (2)

•A DFS tree can be used to discover

articulation points in Θ(n+ m) time.

•We start with a program that computes a DFS

tree labeling the vertices with their discovery

times.

•We also compute a function called low[v]that can

be used to characterize each vertex as an

articulation or non-articulation point.

• The root of the DFS tree (the root has a d[ ] value of 1)

will be treated as a special case:

Finding Articulations (3)

•The root of the DFS tree is an articulation

point if and only if it has two children.

•Suppose the root has two or more children.

• Recall that the back edges never link the vertices in

two different subtrees.

• So, the subtrees are only linked through the root vertex

and if it is removed we will get two or more connected

components (i.e. the root is an articulation point).

•Suppose the root is an articulation point.

• This means that its removal would produce two or

more connected components each previously

connected to this root vertex.

• So, the root has two or more children.

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

3

Finding Articulations (4)

•Computation of low[v].

•We need another function defined on vertices:

•This quantity will be used in our articulation

finding algorithm:

low[v]= min{d[v], d[z]such that

(u, z) is a back edge for some descendent uof v}

•So, low[v]is the discovery time of the vertex

closest to the root and reachable from vby

following zero or more edges downward, and then

at most one back edge.

Finding Articulations (5)

•For non-root vertices we have a different test.

•Suppose vis a non-root vertex of the DFS tree T.

Then vis an articulation point of Gif and only if

there is a child wof vin Twith .

•Sufficiency: Assume such a child wexists.

• There is no descendent vertex

of vthat has a back edge going

“above” vertex v.

• Also, there is no cross link from

a descendent of vto any other subtree.

• So, when vis removed the subtree

with was its root will be disconnected

from the rest of the graph.

Root

v

w

Possible links

No links like this

[

]

[

]

d v low w

≤

###### You're Reading a Preview

Unlock to view full version