Class Notes (1,100,000)
CA (650,000)
UW (20,000)
CS (1,000)
CS341 (20)
Lecture

CS341 Lecture Notes - Biconnected Component, Two Trees Of Valinor, Computer Network


Department
Computer Science
Course Code
CS341
Professor
Forbes Burkowski

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
“abovevertex 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