4.7 - Others

Articulation Point, Biconnected Graph, Biconnected Component

Articulation Point

在connected undirected graph中，若將某vertex及其連接的邊刪除後會造成剩下的subgraph變成unconnected，此種vertex稱為articulation point。

如何求出articulation points?

1. 求出各點的DFS number order

2. 畫出DFS spaning tree，並標示出back edge

3. 算出low值

   $low(x)=\min\{DFN(x),\ DFN(y)\}$，y為包含x的後代子孫經過最多一條back edge所到達的頂點編號。

4. 判斷articulation point法則

   1. 若root有2個子點，則root是articulation point

   2. 針對其他點x，若low(x的子點)≥DFN(x)，則x是articulation point

e.g.

1. 

   (不一定是此順序)

2. 
3. 0, 4, 8, 9 $\Rightarrow$無子點，不是articulation point

   3$\Rightarrow$Root有兩個子點

   low(0)=2

   low(1)=0

   low(2)=0

   low(3)=0

   low(4)=0

   low(5)=5

   low(6)=5

   low(7)=5

   low(8)=9

   low(9)=8

articulation point: {1, 3, 5, 7}

Biconnected Graph

沒有任何articulation points的connected undirected graph稱為biconnected graph。

e.g.

Biconnected Component

Undirected graph $G$, $G'$ is a biconnected component of $G$ if $G'$ satisfies:

1. $G'$ is biconnected subgraph

2. There is no connected subgraph of $G$ included $G'$

e.g.

biconnected components: