GATE CSE 1999 | Question: 1.15

Question

The number of articulation points of the following graph is

• A. $0$
• B. $1$
• C. $2$
• D. $3$

Comments

$Cut $ $Vertex$ = $Articulation$ $ point$ = Removal of vertex creates more components of graph .

Answer 1

ARTICULATION POINT: are those points whose removal from the graph makes the graph disconnected.

Here if we remove the vertex no. $2$ then we get disconnected graph.

similarly, if we remove the vertex no. $3$ then we get disconnected graph.

similarly, if we remove the vertex no. $5$ then we get disconnected graph.

So, (D) choice. 

Comments

This is same as VERTEX CUT / SEPRATING SET

---

yes same

---

@paraskk @shashankrustagi no cut vertex(Articulation Point) and vertex cut are not same !

Cut vertex are vertex whose removal increase the number of components while Vertex cut is a set of vertex whose removal either increase number of componets or single isolated vertex is left .

for ex consider a graph    A------B  here cut vertex do not exist as removal of either of vertex do not increase the number of components , while vertex cut exist because removing wny one of the vertex an isolated vertex is left i.e {A} , {B} 2 vertex cut

Answer 2

Answer: D

The articulation points are 2,3,5.

Answer 3

Answer: (D)

Explanation: An articulation point is a vertex whose removal makes the graph disconnected.
There are three articulation points in the given graph, they are vertices- 2, 3, and 5
If any one of the above nodes is removed from the graph then the graph becomes disconnected.
 

Comments

Nice one

Answer 4

An articulation point(A.P)is a vertex removal of which disconnects the graph

 

So we will have to choose each vertex and check if its an A.P or not

 

4,6 and 7→ These are pendant vertices with degree 1.Removal of these vertices can never make the graph disconnected .These are like the leaf nodes in a rooted tree

 

2,3 and 5 → Nodes of degree 3.Removal of each of them will deleted the 3 edges associated with them which will make the garph disconnected

 

Removal of vertex 1 will not make it disconnected which can be clearly seen

 

Correct answer is option D

Answer 5

Articulation points means the cut vertex. Hence there are 3 cut vertex {2,3,5}