World's most popular travel blog for travel bloggers.

Articulation vertex in complementary graph

, ,
Problem Detail:

I need to implement an algoritm, but I can't understand the theory behind it.

How can I prove that if v is an articulation vertex in a graph G , that it will not be an articulation vertex in G' complimentary graph ?

I know that an articulation vertex , is one which when removed disconects the G . And that the complementary graph , is one with two distinct vertices adjacent if and only if they are not adjacent in G.But I can't figure out how to connect this statements with my problem.

Answered By : hengxin

Hint: An equivalent characteristic of "an articulation vertex $v$" is as follows:

$v$ is an articulation vertex in $G$ $\iff$ there exists two vertices $x,y$ such that $v$ is on all the paths between $x,y$.

So it suffices to check all the pairs $x,y$ in $G'$ to see whether there exists some path between them which does not pass $v$.

More hints:

Consider two cases:

1. In $G$, $v$ is on all the paths of $x,y$. Then is $e = (x,y) \in G'$?
2. In $G$, $v$ is not on all the paths of $x,y$. Where are $x$ and $y$ if $v$ is removed in $G$? Then,

2.1 What if $(x,y) \notin G$?
2.2 What if $(x,y) \in G$? Can you find a path $x \leadsto y$ in $G'$ which does not pass $v$?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37349

3200 people like this

Post a Comment

Let us know your responses and feedback