World's most popular travel blog for travel bloggers.

Articulation vertex in complementary graph

, , No Comments
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.

Asked By : Karudi
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 :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback