一、定義
割點：如果在圖G中刪去一個結點u后，圖G的連通分枝數增加，即W(G-u)>W(G)，則稱結點u為G的割點，又稱關節點。
橋：如果在圖G中刪去一條邊e后，圖G的連通分支數增加，即W(G-e)>W(G)，則稱邊u為G的橋，又稱割邊或關節邊。
雙連通分支：G中不含割點的極大連通子圖稱為G的雙連通分支，又稱為G的塊。
二、DFS
描述：在對于任選一個圖中結點為根的DFS搜索樹中建立一個LAB數組與LOW數組，LAB數組存儲個結點的編號，LOW數組存儲各點及其子樹的各結點能到達的最小編號結點的編號。
1 //lab為一個全局變量，初始為1， LAB各項初始為0
2 DFS(u)
3 LAB[u] = LOW[u] = lab++
4 for each (u, v) in E(G)
5 if LAB[v] is 0
6 DFS(v)
7 LOW[u] = min{LOW[u], LOW[v]}
8 else if v isnot parent of u
9 LOW[u] = min{LOW[u], LAB[v]}
第5行中，如果(u, v)是樹邊，則對v做深度優先搜索，并且LOW[u] = min{LOW[u], LOW[v]}，如果(u, v)是反向邊，則LOW[u] = min{LOW[u], LAB[v]}。三、割點
描述：當一個結點u是割點時必滿足以下兩個條件之一：
1）u為根且至少有兩棵子樹；
2）u不為根且存在一個u在深搜樹中的子女v使得LOW[v] ≥ LAB[u]。
示例：POJ 1523 解題報告。
四、橋 描述：一條邊e=(u, v)是橋，當且僅當e為樹枝邊且LOW[v] > LAB[u]。
示例：POJ 3352 解題報告。
posted on 2009-07-05 16:18
Icyflame 閱讀(2627)
評論(1) 編輯 收藏 引用 所屬分類:
圖論