in DS retagged by
9,239 views
15 votes
15 votes

An $articulation$ $point$ in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.

Let $T$ be a $\text{DFS}$ tree obtained by doing $\text{DFS}$ in a connected undirected graph $G$.

Which of the following options is/are correct?

  1. Root of $T$ can never be an articulation point in $G$.
  2. Root of $T$ is an articulation point in $G$ if and only if it has $2$ or more children.
  3. A leaf of $T$ can be an articulation point in $G$.
  4. If $u$ is an articulation point in $G$ such that $x$ is an ancestor of $u$ in $T$ and $y$ is a descendent of $u$ in $T$, then all paths from $x$ to $y$ in $G$ must pass through $u$.
in DS retagged by
by
9.2k views

14 Comments

B & D?
1
1
yes
0
0
In option B, even if the root has 2 children it is still possible that both the children are connected to each other(Cycle). The how is B true in that case? Im asking since the option says “if and only if” which should imply that both should be true or both should be false(both meaning root being an articulation point and root having 2 children). However we can have a root with 2 or more children but still not be an articulation point. Please clarify this doubt of mine if possible.
1
1
Yes root will not be articulation point in that case, but it doesn’t matter as with 1 child it’ll never be.
0
0
@zxy123 are you implying that option B is right?
0
0
Yes it is correct according to me
0
0
edited by

@123sid Exactly, I eliminated option B based on the same reason as u mentioned. I don’t know how people are saying it is correct I still do not understand. If option B is correct then these two implication should be correct 

  1. Root of DFS ‘T’ being an articulation point → Root of T has more than 1 children (correct)
  2. Root of T has more than 1 children ---> Root of ‘T’ is an articulation point   (not necessary)

only implication 1 is correct not 2….

please, someone, explain why B is correct

 

1
1
Its not p-->q   it is p<-->q

They clearly mentioned if and only if which means iff also known as bi-implication
0
0
@KULDEEP+SINGH+2

Can you give a counter-example of G and T where pt.2 is wrong?
0
0
Sorry I misinterpreted the question…..now I understood B is correct and both implication from left to right and right to left follows correctly ….
0
0
@123sid,

Two or more children in a DFS tree will only be present when they are not interconnected. Because before exploring a sibling subtree, it explores the whole subtree first in the graph.
4
4
@avistein Yes brother you are right. I had misinterpreted the statement initially.
1
1

@123_sid

tree does not contain cycle and in ques. the graph mentioned is a tree.

0
0

2 Answers

29 votes
29 votes
Best answer

As per the option B it says root of T can be an articulation point in G if and only if it has 2 or more children, now here for simplicity I have taken simple case where root will have 2 children and I will tell you for the generalized case later. Also as its double implication lets see it as separately

Case 1: If root is articulation point then root will have 2 or more children

If a vertex is articulation point then its removal disconnects the graph into $2$ or more components means there must exist at least $2$ vertices for which each and every path in between them will pass through articulation point and removal of articulation point will destroy all the paths in between them and thereby disconnecting the graph into components, otherwise that vertex can not be an articulation point because even if we remove that vertex still every pair of vertices has some other path and hence graph wont get disconnected.

Now when we start DFS Traversal from vertex $V$ (articulation point) we may visit either the vertex from $G_1$ or $G_2$ first, lets say we visited vertex of $G_2$ first now during the DFS traversal which becomes child of $V$ now we can never visit any vertex in $G_1$ unless and until we do not use vertex $V$ because every path will go through vertex $V$ only, and by the nature of DFS no vertex during the traversal of sub-graph $G_2$ can visit the vertex $V$ again as it will be having Gray color/ not yet finished (refer DFS algorithm from CLRS for better understanding) and because of this property all the vertices in $G_2$ will be exhausted and we will be back to the vertex $V$ but vertex $V$ still has path to the unvisited vertices of sub-graph $G_1$ and hence the first vertex which will be visited in $G_1$ will become the new child of $V$ thereby making $2$ children for the root vertex $V$ which is the articulation point.

Case 2: If root vertex has 2 or more children then it is articulation point

Lets say in an undirected graph if root has $2$ children then it is true that there is no path between the vertices in left sub-tree and right sub-tree of vertex $V$ (w.r.t DFS traversal tree) because if there had been any path between the left and right sub-tree the in that case if we start with right child then before reaching to the root all the vertices in left sub-tree would have been visited and root had only single child but it is contradiction as root has $2$ children and hence there can be no path between the left and right sub-tree of vertex $V,$ thereby making it the ONLY vertex through which vertices in left and right sub-tree are connected

Hence above two cases proves the option B is correct and A is incorrect

For the generalized case visualize star graph with many vertices where center is articulation point, now you got the intuition and apply this on any graph!

Lets understand option C.

Option C says that leaf of tree $T$ can be an articulation point, its FALSE because if some vertex is leaf of tree $T$ then all the vertices to which it connects are already been visited which indicates that even without using this leaf vertex there exists path between all of its neighbors and hence it can not be an articulation point. 

Hence option C is incorrect

Now option D

Option D talks about ancestors and decedents $X$ and $Y$ and says that if $X$ is ancestor of $U$ in $T$ and $Y$ is decedent then all the paths between $X$ and $Y$ must pass through $U$ but we have counter for this as shown below.

Hence option D is incorrect

edited by

4 Comments

3
3

A better arrangement to visualize $U$ as an articulation point, but $X$ (ancestor of $U$) and $Y$ (descendant of $U$) being connected through a “back-edge” have an alternate path which is not through $U$.

Thus option D is False.

0
0

@Abhrajyoti00 good example !!

1
1
6 votes
6 votes

Only B is Correct

  1. If we think of A as 3 node tree where root have two children , Here root will be articulation point. Hence A is False.
  1. if the Root have only 1 child it can never disconnect a Tree on removal.Hence B is Correct.
     
  2. Also, a leaf when removed from a tree can never disconnect a graph. Hence C is False. 
     
  3. As Observed and pointed by @deba1998 and @PandurangaVittal Option D is incorrect
edited by

4 Comments

i understand that every single mark matters now...but please just think there is no chance that ancestors and descendants change based on the node u start..once the tree has been formed than we decide the ancestors and descendants in the tree..there is a very popular coding question related to this asking the descendants and ancestors of a node it doesnt matter man where u start from...
0
0
yes bro i know the situation is same for you also and so you  are trying to prove yoyr logic correct irrespective of  the above examples, so let it be finally the ans will be b only
0
0
no problem bro..lets wait for the final answer key
0
0
Answer:

Related questions