一、定义
割点：如果在图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 阅读(2528)
评论(1) 编辑 收藏 引用 所属分类:
图论