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