Intuition behind the algorithm of finding articulation point in a graph:
My two nephews ,Aarish and Zaheen,are two of the most intelligent lads I have ever seen.The things they talk about often surprises me due to their intelligence level.One day I heard them about talking about articulation points.Infact,it was like a gift,as I myself was preparing to learn about it;but could not understand the intuition behind it.So I decided to listen to their conversation.Here is the extract of it
***********************************
-Brother,what is an articulation point?
:Well,Articulation points in a graph are the points whose removal divides the graph in two or more connected components.
-Umm,easy to understand.Is there any algorithm to find those points?
:I know about such an algorithm.But you should ask yourself first.can you think about any approach?
-Ah,If we think naively,then its not that hard to find the articulation points using the basic graph algorithms we know.Here is a naive algorithm
for all vertices v belongs to G.V:
Remove v from G
See if G is connected using bfs/dfs
If G is not connected,v is an articulation point,otherwise no
Return the removed vertex in the graph
:Good one!!! :D
-Nah,I don’t like it :/ . This algorithm takes ,
O( loop iteration)*O(dfs/bfs)=O(V)*O(V+E)=O(V(V+E)) times.It is a quadratic time algorithm.too much for a dense graph.
:Well,We can upgrade it although to a linear time one,if we have some insight about the properties of articulation points.
-How ??
:To do so,let’s make our hand a little dirty,do a simple DFS a bit :)
(After a bit of time)
Ok,so your dfs is done.Now look at the graph carefully.What can you see now?
-Simple,a DFS tree -_-
:Good,so can you classify the nodes according to some criteria?
-Of course;Root,internal nodes and leaves.But why?
:Well,if you can classify the nodes,then it will be easy for you to apply conditions to define articulation points differently as per their classification
-Please explain a bit :3
:Well,you can determine if a root is an articulation point in a different way,determine if an internal node is an articulation point in another way and determine if a leaf is an articulation point in .........
-Wait,I have something to say!!
:Well,what?
-Can any leaf be an articulation point :/ ?
:Well,why?
-You see,if the removal of a leaf node disconnects the graph,then it means the graph can be divided into two components such that the leaf node acts as the connection between them,right?
:I agree.Then?
-Then ,it means that leaf has edges with both the connected components.One connected component has the root of the dfs tree,other one doesn’t.
:Ok
-Then while doing dfs,you could have visited to the “not-root-containing component” via that leaf from the “root-containing component”,right?
:Yes.
-So,if there is a connected component whom you can visit through a node during DFS,can that node be regarded as leaf?I don’t think so.
:You are goddamn right:LEAVES ARE NEVER ARTICULATION POINTS :D
-ah,relieved :)
:Ok,then now tell if you have anything to say about the root node?
-Umm,still nothing to say.Can you do this?
:Ok,assume that the root has one child.Can it be an articulation point?
-Don’t think so.Remove the root,you still get the DFS tree connected.So ,no.
:Ok,what if it has two children?
-Ah,well then.if I remove the root,there are two subtrees with no tree edge between them.So,there are disconnected components.
:So,you want to say that the root is...
-No no,still not;what if there is a cross edge between the subtrees?they will still be connected...
:Sure ;) ?
-Ah wait,how can there be cross edges?the graph is undirected :o
:So,the root is?
-AN ARTICULATION POINT IF IT HAS TWO ..WAIT ....MORE THAN TWO CHILDREN!!!
:BAZINGA!!Now you are talking lad :D
-Ok,then lets see how can we encounter the cases of internal nodes.
:Ok bro,In fact it will be the trickiest one.
-Indeed ,I can feel it.I am feeling blank a bit about it.Can you show some light?
:Ok,lets just think about it.Say ,we have just removed an internal node.What will happen now?
-Well,then the tree will be disconnected.Not sure about the graph though.
:Good,when the disconnected tree will result in disconnected graph too?
-Umm...if there is no bypass way between the root and any of the subtrees under the removed node?
:You mean,a backedge from a subtree under the removed node to one of the proper ancestors of the removed node.
-Yes,yes!!!But how can we detect them in linear time?
:Ok,what if we keep the track about a particular property of every nodes?and call it low(removed node) ?
-What property?
:The oldest ancestor that can be visited from the subtree rooted by that node?
-benefit?
:Lets think that the removed node is V.and there are two children of it:x,y.Assume that we have somehow counted low(x) and low(y).
-Ok,then?
:Then ,what do you think,how can this will help you to see if v is an AP or not?
-Well,I guess,I can check whether any of low(x) and low(y) is greater than or equal to the discovery time of v.
:Interesting,but why ;) ?
-If it happens,it will mean the oldest ancestor of either x or y through a back edge is still not the ancestor of v.It means there is no back edge or bypass from x(or y) to a proper ancestor of v!!!So obviously,if so happens,then v IS AN ARTICULATION POINT!!!
:Excellent brother,just excellent!!You really can read me well.....
-Well ,I ain’t convinced yet.You haven’t still said about how can we count low(v).Can we do so in linear time?
:That’s the tweak lad,think recursively ;)
-Recursively -_- ?
:Yes,lets think about v and its children again,what do you think,how can you count low(v) from low(x) and low(y)?
- Ah,I see.Low(v) means the oldest ancestor that can be visited from the subtree rooted by v.That visit can either start from a node situated in subtree rooted by x,or from a subtree rooted by y or from v itself?
:You are in form today.Then?
-The first two cases points to low(x) and low(y) respectively.But about the last case,well,I think,separate checkings of back edges need to be done.Oh and btw,in case of leaf nodes,it will be equal to their discovery time.
:I am proud of you brother.Infact,THIS IS THE RECURSIVE SOLUTION!!!
LOW(V)=MIN ( DISCOVERY TIME OF v,
MIN( LOW(X) FOR EVERY CHILDREN X OF V),
MIN( DISCOVERY TIME OF U FOR EVERY BACKEDGE(V,U)
)
-But still,can this recursive thing be done in linear time?
:Well,what about doing it simultaneously with the DFS ?in O(V+E) time?
-You are awesome :)
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন