Graph Theory

Question

Can someone solve this?

Also please attempt this question on Algorithms time complexity if interested :)

https://gateoverflow.in/210836/algorithms-time-complexity 

Comments

..

---

Biconnected components are ${\{1,2,4\}, \{3,9,10\}, \{6,7,8\}, \{15,17,16\}, \{20,21,22\}, \{18,23,24\}}$.

Note that they all are K₃. which do not contain any articulation point and bridges.

---

Seems correct. Can you have a look at abhishek's solution? What do you think?

Answer 1

Total biconnected component is 16

----> 1,2,4,7,8,9,10,12,13,14,16,17,21,22,23,24.

So answer is none of these. 

Comments

I don't have the answer :(
Though I got what you are saying. Even every single node is a subgraph. Nodes 3,5,6.... are articulation points. And if these are ignored, others satisfy the conditions to be a biconnected component.

---

yes .

---

@abhishekmehta4u but it is mentioned in the question that it should be "maximal".

---

I think it is the modified definition of biconnected graph. Here they have also include a condition that is it should not contain bridge.

Answer 2

I think answer should be 7.

Components will be {1,2,4},{6,7,8},{9,10},{12,13,14},{16,17},{20,21,22},{23,24}

After removing the articulation points {3,5,11,15,19,18}