...
Data-Structures
October 8, 2023
Computer-Organization
October 8, 2023
Data-Structures
October 8, 2023
Computer-Organization
October 8, 2023

Data-Structures

Question 32
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 DFS tree obtained by doing 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. 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.
  3. A leaf of T can be an articulation point in G.
  4. Root of T is an articulation point in G if and only if it has 2 or more children
A
4
Question 32 Explanation: 
Statement-1: FALSE: Root of T can never be an articulation point in G.
Statement-2:
Example-1:
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.





Here 2 and 6 are articulation points.
If you consider node-1 ancestor and node-3 descendent, then without passing through from node -2, there exists a path from one node to another node.
Path from node-1 to node-3
If you consider node-5 ancestor and node-4 descendent, then without passing through from node-6, there exists a path from one node to another node.
Path from node-4 to node-5
The given statement is not TRUE for all cases. So, the given statement is FALSE.

Statement-3: FALSE: Leafs of a DFS-tree are never articulation points.

Statement-4: TRUE: The root of a DFS-tree is an articulation point if and only if it has at least two children.



Node 2 is an AP because any node from the first subtree (1, 2) is connected to any node from the second subtree (4, 5, 6, 7, 8) by a path that includes node 2. If node 2 is removed, the 2 subtrees are disconnected.

Correct Answer: A
Question 32 Explanation: 
Statement-1: FALSE: Root of T can never be an articulation point in G.
Statement-2:
Example-1:
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.





Here 2 and 6 are articulation points.
If you consider node-1 ancestor and node-3 descendent, then without passing through from node -2, there exists a path from one node to another node.
Path from node-1 to node-3
If you consider node-5 ancestor and node-4 descendent, then without passing through from node-6, there exists a path from one node to another node.
Path from node-4 to node-5
The given statement is not TRUE for all cases. So, the given statement is FALSE.

Statement-3: FALSE: Leafs of a DFS-tree are never articulation points.

Statement-4: TRUE: The root of a DFS-tree is an articulation point if and only if it has at least two children.



Node 2 is an AP because any node from the first subtree (1, 2) is connected to any node from the second subtree (4, 5, 6, 7, 8) by a path that includes node 2. If node 2 is removed, the 2 subtrees are disconnected.

0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x
error: Alert: Content selection is disabled!!