L13 Undirected Graph

Posted on 2021-08-23 Edited on 2025-06-17 In Computer Science Views: 40

Outline:

UAG的DFS树
UAG的DFS框架
UAG的DFS应用
- 容错连通
  - 寻找割点
  - 寻找桥

Ref:

算法设计与分析(Algorithm design and analysis) by 黄宇

UAG的DFS树

UAG的遍历的主要差别就在于剔除二次遍历

TE：当发现一个白色节点并递归地进行遍历时，就将其连接的边标记为TE。遍历过程中的TE组成遍历树，这与DAG是类似的。对于原本无向的边，遍历过程为它做了定向( orientation ), 即遍历推进的方向。
BE：当遍历节点 $u$ 并发现一条边指向灰色节点 $v$ 时, 此时有两种本质不同的情况:

若 $v u$ 是TE, 则这是一次二次遍历,因而标识并剔除这一类型的遍历.

若 $v$ 是 $u$ 的某个不是父节点的祖先节点, 则将 $u v$ 标记为BE
DE: 当遍历节点 $u$ 时, 发现一条边指向节点 $v$ 时, 且 $v$ 是 $u$ 在遍历树中的后继节点, 此时边 $u v$ 为DE, 但这次遍历必然是二次遍历,应该被剔除. 这是因为根据DE的定义, 此时 $v$ 不能是白色( 否则 $u v$ 是TE ), 不能是灰色(可能是二次遍历的BE ), 因而只能是黑色, 即 $v$ 已经结束了遍历, 它结束遍历前必然已经完成了边 $v u$ 的遍历, 且根据 $u$ , $v$ 间的祖先后继关系, 边 $v u$ 首次被遍历时标记为BE(可能是二次遍历的BE).
CE: 不存在. 因为当遍历节点 $u$ 时,发现一条边指向节点 $v$ . 根据CE的定义, $u$ , $v$ 间没有祖先后继关系,所以与上面分析类似, 节点 $v$ 只能是黑色, 它已经完成了遍历. 所以点 $v$ 在结束遍历前必然已经访问过边 $v u$ . 当从 $v$ 出发遍历 $v u$ 时, $u$ 尚未被遍历, 为白色. 所以 $v u$ 为TE, 这和 $u$ , $v$ 间没有祖先后继关系相矛盾.

UAG的DFS框架

对于TE的处理于DAG一致, 此外还要处理BE的情况. 根据对BE的讨论,我们必须去除指向父结点的BE. 为此, 我们记录了每个节点的父节点.

算法框架直接将上述两种情况外的其他情况忽略, 因为其他情况都是二次遍历, 不需要处理. 一个邻居节点只可能有3种情况:

白色: 即TE
灰色:
- 灰色且不是父结点: 需要额外处理
- 灰色且是父结点: 二次遍历
黑色:
- DE: 二次遍历
- CE: 二次遍历

DFS_UG(v, parent):


v.color := GRAY;
<Preorder processing of node v>;
foreach neighbour w of v do
	if w.color = WHITE then
		<Exploratory processing of TE vw>;
		DFS_UG(w,v);
		<Backtrack processing for TE vw>;
	else
		if w.color = GRAY and w != parent then
			<Check BE vw>;
<Postorder processing of node v>;
v.color := BLack;

UAG的DFS应用

容错连通

定义4.7 对于连通的无向图 $G$ , 如果其中任意去掉 $k - 1$ 个点, 图 $G$ 仍然连通, 则称图 $G$ 是 $k$ -点连通的. 类似的, 如果图中任意去掉 $k - 1$ 条边, 图 $G$ 仍然连通, 则称图 $G$ 是 $k$ -边连通的.

已知,当 $k = 1$ 时, $k$ -连通就退化为传统的无环连通. 另外, 我们更关注 $k = 2$ 的特殊情况, 即去掉某个点或某条边后,剩下的图不再连通. 由此引入割点( articulation point )和桥( bridge )的概念.

定义4.8 对于连通的无向图 $G$ , 称节点 $v$ 为割点, 如果去掉点 $v$ 后, 图 $G$ 不再连通; 称边 $u v$ 为桥, 如果去掉边 $u v$ 后, 图 $G$ 不再连通.

寻找割点

Brute Force: 遍历每个顶点, 检查剩下的图是否连通, 代价为 $O (n (m + n))$ , 这一方法源于割点的定义. 为了将代价改进到线性时间, 需要将割点的定义做等价变换.以支持更高效的找割点的算法.

割点的定义依赖一个全局的性质( 整个图是否连通 ), 这一性质难以高效地进行检测. 为此我们首先将割点的定义等价地变化为一个局部的性质, 利用部分节点之间的关系来完成割点的检测.

引理4.7 ( 割点基于路径的定义 ) 节点 $v$ 为割点, 当且仅当存在节点对 $w$ 和 $x$ 满足节点 $v$ 出现在 $w$ 到 $x$ 的每一条路径上.

证明略.
引理4.8 ( 割点基于DFS的定义 ) 假设在一次DFS中, 节点 $v$ 不是遍历树的根节点. 则节点 $v$ 为割点, 当且仅当在遍历树中, 存在节点 $v$ 的某棵子树, 没有任何BE指向 $v$ 的祖先节点.

证明:

必要性: 易证若节点 $v$ 的某棵子树,没有任何BE指向 $v$ 的祖先节点, 则删掉 $v$ 后, 该子树将于图的其他部分断连, 所以 $v$ 是割点.

充分性: 假设节点 $v$ 为割点, 则根据引理4.7, 存在不同于 $v$ 的两个节点 $x$ 和 $y$ 满足 $v$ 出现在 $x$ 到 $y$ 的每一条路径上. 首先我们发现节点 $x$ 和 $y$ 中至少有一个是节点 $v$ 在遍历树中的后继节点( 可通过反证法证明. ). 所以必有某个点在遍历树中的后继节点, 而 $v$ 必然不是叶节点. 同样可用反证法证明, 若 $v$ 的任意子树均有BE指向 $v$ 的祖先节点, 此时无论 $x$ 和 $y$ 哪一个是 $v$ 的后继节点( 或者都是 ), 均可构造一条从 $x$ 到 $y$ 的不经过 $v$ 的路径, 这和 $v$ 出现在 $x$ 到 $y$ 的每一条路径上相矛盾.

证毕.
根据引理4.8, 可以用算法操作来发现割点: 为每个节点维护一个变量back来判定它是否为割点:
- 当 $v$ 首次被发现时: $v . b a c k = v . d i s c o v e r T i m e$
- 遍历过程中遇到一条从节点 $v$ 指向节点 $w$ 的BE: $v . b a c k = m i n {v . b a c k, w . d i s c o v e r T i m e}$
- 遍历节点 $w$ 结束, 从 $w$ 回退到 $v$ 时: $v . b a c k = m i n {v . b a c k, w . b a c k}$
注意, $v . b a c k$ 初始值为 $v . d i s c o v e r T i m e$ , 且 $v . b a c k$ 的值只会减少. 其减少有两种情况:
- 遍历过程遇到一条BE, 记为边 $v w$ . 处理完BE并回退时, $v . b a c k$ 被减少为 $w . d i s c o v e r T i m e$ . 由于BE指向的节点 $w$ 是祖先节点, 所以 $w . d i s c o v e r T i m e$ 更小,这一更新使得 $v . b a c k$ 的值减少.
- 处理完TE $v w$ 回退时, 如果节点 $w$ 的back值有更新( 只可能减少 ), 这一更新随着回退被传递到回退的节点.

当从TE $v w$ 回退时, 如果 $w . b a c k \geq v . d i s c o v e r T i m e$ , 则节点 $v$ 是割点.

定理4.5 ARTICULATION-POINT-DFS算法是正确的.

证明:

根据引理4.8, 要证明算法正确性, 只需证明当从TE $v w$ 回退时, 如果 $w . b a c k \geq v . d i s c o v e r T i m e$ , 则以 $w$ 为根的某棵子树没有任何BE指向 $v$ 的祖先节点. 根据back值的更新方法, 如果以 $w$ 为根的某棵子树存在BE指向 $v$ 的祖先, 则 $v$ 的祖先的 $d i s c o v e r T i m e$ 会被赋值给 $w$ 为根的子树中某个节点的back值, 且随着遍历的回退过程, 这一 $d i s c o v e r T i m e$ 会以back遍历的方式传递给 $w . b a c k$ . 由于祖先节点具有更小的 $d i s c o v e r T i m e$ , 所以如果这样的一条BE存在, 则 $w . b a c k$ 一定小于 $v . d i s c o v e r T i m e$ , 反之则说明这样的BE不存在.

ARTICULATION-POINT-DFS(v):

v.color := GRAY;
time := time + 1;
v.discoverTime := time;
v.back := discoverTime;
foreach neighbour w of v do
    if w.color = WHITE then
        w.back	:=  ARTICULATION-POINT-DFS(w);
		if w.back >= v.discoverTime then
            Output v as an articulation point;
		v.back = {v.back, w.back};
	else
        if vw is BE then
            v.back = min{ v.back, w.discoverTime };
return back;

寻找桥

基于UAG的DFS中,只会出现TE和BE, 对于BE, 删去它后图依然是连通的( 易证 ), 因此只需关注TE.

引理4.9 ( 桥基于DFS的定义 ) 给定遍历树中的TE $u v$ ( $u$ 是 $v$ 的父结点 ), $u v$ 是桥当且仅当在以 $v$ 为根的所有遍历树的子树中, 没有BE指向 $v$ 的祖先节点( 不包括 $v$ , 包括 $u$ ).
$v . b a c k$ 维护方式为:
- 当 $v$ 首次被发现时: $v . b a c k = v . d i s c o v e r T i m e$
- 当遍历BE $v w$ 时, $v . b a c k = m i n {v . b a c k, w . b a c k}$
- 当遍历节点 $w$ 结束, 回退到 $v$ 时, $v . b a c k = m i n v . b a c k, w . b a c k$
定理4.6 BRIDGE-DFS算法是正确的.

证明略

BRIDGE-DFS(u):

v.color := GRAY;
time := time + 1;
v.discoverTime := time;
v.back := discoverTime;
foreach neighbour w of v do
    if w.color = WHITE then
    	v.back := min{ u.back, v.back };
    	if v.back > u.discoverTime then
    		Output uv as a bridge;
	else
		if uv is BE then
			u.back := min{u.back, v.discoverTime};