Dark Mode

9,394 views

17 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?

- Root of $T$ can never be an articulation point in $G$.
- Root of $T$ is an articulation point in $G$ if and only if it has $2$ or more children.
- A leaf of $T$ can be an articulation point in $G$.
- 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$.

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*

Much better solution by @Sachin Mittal 1 Sir : https://youtu.be/3xubsm7-VPY?list=PLIPZ2_p3RNHjUCHdJp-_soSSmhgmO4i0T&t=889

3

1

6 votes

**Only B is Correct**

- If we think of A as 3 node tree where root have two children , Here root will be articulation point.
**Hence A is False.**

- if the Root have only 1 child it can never disconnect a Tree on removal.
**Hence B is Correct.**

- Also, a leaf when removed from a tree can never disconnect a graph.
**Hence C is False.**

- As Observed and pointed by @deba1998 and @PandurangaVittal Option D is incorrect

2

A simple counterexample against option D. In graph G, clearly u is an articulation point. Now one of the possible DFS trees is as given below. In that tree, x is an ancestor of u and y is a descendant of u. But still, not all paths between x and y go through u only in the original graph G. As we have a direct edge between x and y too. Therefore, only option B is correct.

6

edited
Feb 21, 2021
by pritishc

@PandurangaVitthal you sure $x$ is an ancestor of $u$? Because it looks like both $x$ and $y$ are leaf nodes and $u$ is their ancestor, not descendant…

Also, according to https://softwareengineering.stackexchange.com/questions/297283/does-a-tree-node-have-an-ancestor, it depends on which node you select as root. Ancestor/descendant relationship seems to be defined only in rooted trees. If you select $u$ as root, then $x$ and $y$ are descendants.

Okay, if we select $x$ as root, what you say may be possible. My only doubt is now whether $y$ counts as ancestor or descendant of $u$.

1

Well, yes X is an ancestor of U and Y is a descendant of U. We can have a DFS traversal that starts from X. Thus, making X as the root node, now it discovers U which makes U descendant of X, or vice versa, i.e., X is the ancestor of U. After discovering U, we discover Y which makes Y descendant of U. And then, we just discover W and Z in any order. So, yes X will be an ancestor of U and Y is a descendant of U but still, not all paths in between X and Y go through U only in G. Therefore, Option D is not correct.

1

reshown
Jan 17, 2022
by HitechGa

In the exam while solving the question, the below first picture came to my mind.

We start the DFS from the blue node and traverse along the orange line and I felt that option D is correct, simply from the instance of the graph which I had chosen there (within 3 mins of time)

But the situation would have been appropriate if I had chosen the graph (in black) as shown below,

Here again we start from the node indicated with the blue arrow. And the diagram is self explanatory, but unfortunately, this case did not come to my mind, at that situation in pressure.

So please suggest me resources about these graph theory concepts, so that any such questions can be solved by me. I want to build intuition of the same. (Naveen Garg sir, of IIT Delhi, developes some intution and CLRS as well, but more depth is required I guess as far as intuition is concerned).

please help me.

1

@HitechGa clearly you and I already know the concepts. And we were able to select the other options correctly, right? We were able to discern everything about articulation points, correctly judge the leaf node option as wrong, etc.

This is the thing with GATE. In that time pressure you have to be able to try out a variety of different test cases, atleast two to three. That is where we failed and others succeeded (by luck or otherwise). Of course it isn’t easy, but what can we do at this point. If you are taking GATE again next year, take more quality tests, dozens more of them and train yourself under pressure. That is the only way.

I got the other graph theory problem (diameter) wrong too, and that one especially hurt, because my test example was correct right until the end, where I misread the computed adj matrix. So I know how to solve...I just failed under pressure.

If this had been a question from PYQ GOBook, we would have easily solved it because we’re not under that time pressure and not facing a hostile barrage of questions.

This is the thing with GATE. In that time pressure you have to be able to try out a variety of different test cases, atleast two to three. That is where we failed and others succeeded (by luck or otherwise). Of course it isn’t easy, but what can we do at this point. If you are taking GATE again next year, take more quality tests, dozens more of them and train yourself under pressure. That is the only way.

I got the other graph theory problem (diameter) wrong too, and that one especially hurt, because my test example was correct right until the end, where I misread the computed adj matrix. So I know how to solve...I just failed under pressure.

If this had been a question from PYQ GOBook, we would have easily solved it because we’re not under that time pressure and not facing a hostile barrage of questions.

3

i believe option D is correct..beacuse it is mentioned in the question that the graph is undirected

so here it does’nt matter from where u start..x and y will be the ancestors of u in the above graph so it does’nt hold here...u can look for ancestors and descendants of a node in a undirected tree in geeks

according to you if i start with node u than x and y will be descendants..your assumptions are right if the tree was directed but it is clearly mentioned that it is undirected

0

0

first of all..it is clearly mentioned that the graph is undirected..and @deba1998

as u said that we can start with any node here u r contradicting yourself..i invite you to start dfs from the node u than both x and y will be its descendants please have a look

0

0

0

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