articulation points in graph

application of graph theory in data structures

1. Lecture6:AnApplicationofDFS:
Articulationpoints
RecallDFSalgorithm:
DFS{G}{
foreachvinVdo//Initialize
visit[v]=false;
foreachvinVdo
if(visit[v]==false)RDFS(v);
}
RDFS(v){
visit[v]=true;
foreachwinAdj(v)do
if(visit[w]==false){
RDFS(w);
}
}
}
1

2. DFSExample
B
b
e
f
a
b
e
f
B
d
gc
a d
gc
GivenagraphG=(V;E),ittraversesallverticesof
Gand
constructsaforest(acollectionofrootedtrees),to-
getherwithasetofsourcevertices(theroots).
2

3. AdditionalInformation
discover[u]–thediscoverytime,acounterindi-
catingwhenvertexuisdiscovered.
pred[u]–thepredecessorofu,whichdiscovered
u.
DFS{G}{
foreachvinVdo//Initialize
visit[v]=false;
pred[v]=NULL;
time=0;
foreachvinVdo
if(visit[v]==false)RDFS(v);
}
RDFS(v){
visit[v]=true;
discover[v]=++time;
foreachwinAdj(v)do
if(visit[w]==false){
pred[w]=v;
RDFS(w);
}
}
}
3

4. ClassicationofEdges
Treeedges:whicharetheedgesfpred[v],vgwhere
DFScallsaremade.
Backedges:whicharetheedgesfu,vgwherevis
anancestorofuinthetree.
4

5. AnApplicationofDFS:Articulationpoints
Denition:LetG=(V;E)beaconnectedundi-
rectedgraph.Anarticulationpoint(orcutvertex)ofG
isavertexwhoseremovaldisconnectsG.
GivenaconnectedgraphG,howtondallarticulation
points?
5

6. Articulationpoints:Easysolution
Theeasiestsolutionistoremoveavertex(andits
correspondingedges)onebyonefromGandtest
whethertheresultinggraphisstillconnectedornot
(saybyDFS).TherunningtimeisO(V(V+E)).
6

7. Articulationpoints:Observations
1.TherootoftheDFStreeisanarticulationifithas
twoormorechildren.
2.AnyotherinternalvertexvintheDFStree,ifit
hasasubtreerootedatachildofvthatdoesNOT
haveanedgewhichclimbs'higher'thanv,thenv
isanarticulationpoint.
7

8. Articulationpoints:Howtoclimbup
Observethatforanundirectedgraph,itcanonlyhas
treeedgesorbackedges.Asubtreecanonlyclimb
totheupperpartofthetreebyabackedge,anda
vertexcanonlyclimbuptoitsancestor.
v
. . . .
k
w
1
w
2
w
8

9. Articulationpoints:Tackleobservation2
WemakeuseofthediscoverytimeintheDFStree
todene'low'and'high'.Observethatifwefollowa
pathfromanancestor(high)toadescendant(low),
thediscoverytimeisinincreasingorder.
Ifthereisasubtreerootedatachildrenofvwhich
doesnothaveabackedgeconnectingtoaSMALLER
discoverytimethandiscover[v],thenvisanarticula-
tionpoint.
Howdoweknowasubtreehasabackedgeclimbing
toanupperpartofthetree?
DeneLow[v]bethesmallestvalueofasubtreerooted
atvtowhichitcanclimbupbyabackedge.
Low[v]=minfdiscover[v];discover[w]:(u;w)
isabackedgeforsomedescendantuofvg
9

10. RDFS_Compute_Low(v) {
visit[v]=true;
Low[v]=discover[v] =++time;
foreachwinAdj(v)do
if(visit[w]==false){
pred[w]=v;
RDFS_Compute_Low(w);
//WhenRDFS_Compute_Low(w)returns,
//Low[w]storesthe
//lowestvalueitcanclimbup
//forasubtreerootedatw.
Low[v]=min(Low[v],Low[w]);
}elseif(w!=pred[v]){
//{v,w}isabackedge
Low[v]=min(Low[v],discover[w]);
}
}
10

11. Articulationpoints
Articulationpointsarenowdeterminedasfollows:
1.TherootoftheDFStreeisanarticulationpointif
ithastwoormorechildren.
2.AnyotherinternalvertexvintheDFStreeisan
articulationpointifvhasachildwsuchthatLow[w]
discover[v].
ArticulationPoints{
foreachvinVdo
if(pred[v]==NULL){//visaroot
if(|Adj(v)|>1)
articulation_point(v)=true;
}else{
foreachwinAdj(v)do{
if(Low[w]>=discover[v])
articulation_point(v)=true;
}
}
}
Runningtime=?
11