地方政府公務人員四等-電子工程類科計算機概要107 年第 19 題單選題
下圖的關節點（articulation points）為何？
A正確答案
關節點（割點）為移除後會使圖不連通的頂點，本題為 2 與 3。
載入中…
完整詳解
Pro · 無限重點 關節點（割點）為移除後會使圖不連通的頂點，本題為 2 與 3。
1. 圖中邊：0-1, 0-2, 1-3, 2-3, 2-6, 3-4, 3-5, 4-5。
2. 逐一檢查每個頂點移除後是否仍連通：
- 移除 0：1-3-2 仍連通 → 非割點。
- 移除 1：0-2、3 等仍連通 → 非割點。
- 移除 2：6 與其餘節點失去唯一通路（6 只連 2）→ 是割點。
- 移除 3：4、5 仍透過 4-5 互通，但無法連到 0,1,2,6 → 是割點。
- 移除 4、5：因 3-4-5 三角形，移除任一仍連通 → 非割點。
- 移除 6：6 為葉節點 → 非割點。
3. 故關節點為 {2, 3}，選 (A)。
逐選項分析
關節點判定要點
| 概念 | 重點 |
|---|
| 定義 | 移除該頂點及其相連邊後，連通分量數增加的頂點 |
| DFS 判定 | 非根節點 u 為割點 ⇔ 存在子節點 v 使 low[v] ≥ disc[u] |
| 根節點 | DFS 樹中若有 ≥2 個子節點則為割點 |
| 葉節點 | 度數為 1 不可能是割點 |
| 環中節點 | 位於環上且無外掛橋者通常非割點 |
容易把葉節點 6 也當成關節點（誤選 B），但葉節點移除後其餘圖仍連通；也要注意 3-4-5 形成三角形，因此 4、5 並非割點。 
