一、定義
割點(diǎn)：如果在圖G中刪去一個(gè)結(jié)點(diǎn)u后，圖G的連通分枝數(shù)增加，即W(G-u)>W(G)，則稱結(jié)點(diǎn)u為G的割點(diǎn)，又稱關(guān)節(jié)點(diǎn)。
橋：如果在圖G中刪去一條邊e后，圖G的連通分支數(shù)增加，即W(G-e)>W(G)，則稱邊u為G的橋，又稱割邊或關(guān)節(jié)邊。
雙連通分支：G中不含割點(diǎn)的極大連通子圖稱為G的雙連通分支，又稱為G的塊。
二、DFS
描述：在對(duì)于任選一個(gè)圖中結(jié)點(diǎn)為根的DFS搜索樹(shù)中建立一個(gè)LAB數(shù)組與LOW數(shù)組，LAB數(shù)組存儲(chǔ)個(gè)結(jié)點(diǎn)的編號(hào)，LOW數(shù)組存儲(chǔ)各點(diǎn)及其子樹(shù)的各結(jié)點(diǎn)能到達(dá)的最小編號(hào)結(jié)點(diǎn)的編號(hào)。
1 //lab為一個(gè)全局變量，初始為1， LAB各項(xiàng)初始為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)是樹(shù)邊，則對(duì)v做深度優(yōu)先搜索，并且LOW[u] = min{LOW[u], LOW[v]}，如果(u, v)是反向邊，則LOW[u] = min{LOW[u], LAB[v]}。三、割點(diǎn)
描述：當(dāng)一個(gè)結(jié)點(diǎn)u是割點(diǎn)時(shí)必滿足以下兩個(gè)條件之一：
1）u為根且至少有兩棵子樹(shù)；
2）u不為根且存在一個(gè)u在深搜樹(shù)中的子女v使得LOW[v] ≥ LAB[u]。
示例：POJ 1523 解題報(bào)告。
四、橋 描述：一條邊e=(u, v)是橋，當(dāng)且僅當(dāng)e為樹(shù)枝邊且LOW[v] > LAB[u]。
示例：POJ 3352 解題報(bào)告。
posted on 2009-07-05 16:18
Icyflame 閱讀(2646)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
圖論