關節點（articulation points）

在一個網路裡，有些節點默默地承重：把它們抽走，整個東西就裂成不相連的部分。無向圖的一個關節點（或割點）正是這樣的節點——一個頂點，移除它連同它的邊會增加連通分量的數目，把一塊曾經連通的區域斷成兩塊或更多。找出它們便告訴你網路在哪裡脆弱：一個單點故障，它的失去會切斷原本能彼此抵達的部分。

有一種快速方法能在一趟 DFS 中找出所有關節點，用的是與塔揚 SCC 法相同的 low-link 想法。跑 DFS，給每個頂點一個發現時間 disc(u)，並計算 low(u)：從 u 的 DFS 子樹出發、沿樹邊加上至多一條回邊所能抵達的最早發現時間。現在是測試。DFS 的根是關節點，恰當它在 DFS 樹中有兩個或更多子節點（移除它會切斷原本沒有別的方式相連的子樹）。一個非根頂點 u 是關節點，恰當它在 DFS 樹中有一個子節點 v 使 low(v) >= disc(u)：這表示 v 的整個子樹沒有任何回邊爬到 u 之上，所以 u 是那個子樹與其餘部分之間唯一的橋——移除 u，子樹就掉下來。理由是：一條爬到 u 之上的回邊會給子樹另一條逃逸路線，而 low(v) 恰好記下最高的這種逃逸；若連最好的逃逸都爬不到 u 之上，u 就是不可或缺的。

這跑在 O(n + m)，一趟走訪，它精準定位網路中每一個單點故障——對評估通訊、運輸與電網的可靠度，以及把圖拆成它穩固的雙連通部分至關重要。兩個誠實的告誡。根的規則特殊且容易忘：根是割點，恰當它有兩個或更多 DFS 樹子節點，而非依其 low 值判斷。還有，關節點談的是移除一個頂點；密切相關的橋概念談的是移除一條邊——兩者不同，雖然都出自同樣的 low-link 機制，而一張圖可以有割點卻沒有橋、或反之。