> For the complete documentation index, see [llms.txt](https://garychang.gitbook.io/data-structure/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://garychang.gitbook.io/data-structure/4-graph/4.7-others.md).
# 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:
