Intuition behind the algorithm of finding articulation bridges:
So the other night ,while I posting in my blog about articulation point,I heard these two little pal chatting again about something related to graph theory.being a eager learner of graph theory,I tried to pick words from their conversation .They were having it about articulation bridge:
-So,now I have come across about a new topic:articulation bridge.Did you know about it?
:A bit,but never went through it carefully.
-Surprised,its so much similar with the articulation point thing you taught me.
:Great!Then it should be a cakewalk for you to understand the inner things. Btw,now it’s your turn to define articulation bridge
-Easy,its the edges whose removal causes the number of connected components to increase.
:So I guess,there is a similarly naive algorithm for it too?
-Of course,go through each edge;remove it;find if the graph is still connected or not;if so,not a bridge,if not so,its a bridge.Return the edge again in the graph,repeat.
:I can sense a quadratic complexity here.
-Yah,O(E(V+E))
:So is there any smart algo for it?
-Yes.And guess what?It needs the idea of low(u) too,the thing u taught me earlier in articulation point!!
:Great!!how??
-Simple.First run a dfs and get a dfs tree.There will be some edges lost.Will there be any articulation bridge in it?
:I don’t think so.Had there been any bridge that is not in dfs tree,the tree would have lost its connectivity.As there is no other way to reach fro one part to another.
-Yes.So just run a dfs first and you only look after the tree edges for finding the bridge.
:Wao!Damn easy!!
-Not yet the job is done.Think now how can you use low(u) now?
:Ok,let me think.Ummm.......ok,if the removal of an edge(v,u) divides the graph into two components,there should be no back edge from the connected component containing u to the connected component containing v.
-Interpret it using low(u) B-)
:Wait,let me define -
from the connected component containing u-->subtree rooted at u
The oldest ancestor from subtree(u) =low(u)
No back edge from subtree(u) o the connected component containing v.
== Even if there is a back edge,its younger than v
==>low(u)>dfs(v)
Is this?
-You are a maverick B-)
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন