Question:
What are the articulation points in the above graph?
उपरोक्त ग्राफ में आर्टिकुलेशन बिंदु (articulation points) कौन से हैं?
Options:
- 1, 2 and 3
- 2, 3 and 4
- 3, 4 and 5
- 2, 3 and 5
- 1, 2 और 3
- 2, 3 और 4
- 3, 4 और 5
- 2, 3 और 5
Correct Answer: d)
Explanation:
An **articulation point** (cut vertex) is a vertex whose removal increases the number of connected components in the graph:
– Removing vertex **2** disconnects subgraph \(\{1, 3, 4, 9, 10\}\) from subgraph \(\{5, 6, 7, 8\}\).
– Removing vertex **3** disconnects nodes 9 and 10 from the main graph.
– Removing vertex **5** disconnects node 6 from the graph.
– Vertices 1 and 4 belong to the 4-cycle \(1-2-3-4-1\); removing either leaves an alternative path through the other.
Thus, the articulation points are **2, 3, and 5**.
ग्राफ में **आर्टिकुलेशन पॉइंट (कट वर्टेक्स)** वह शीर्ष होता है जिसे हटाने पर ग्राफ दो या अधिक भागों (disconnected components) में विभाजित हो जाता है:
– शीर्ष **2** को हटाने पर बायाँ भाग और दायाँ भाग अलग हो जाते हैं।
– शीर्ष **3** को हटाने पर नोड्स 9 और 10 अलग हो जाते हैं।
– शीर्ष **5** को हटाने पर नोड 6 अलग हो जाता है।
शीर्ष 1 और 4 चक्र \(1-2-3-4-1\) का हिस्सा हैं, इसलिए उन्हें हटाने पर ग्राफ डिस्कनेक्ट नहीं होता।
अतः सही उत्तर **2, 3 और 5** है।