PDF《仙人掌图分析：》

仙人掌图分析: 为了对仙人掌图有一个感性认识,我们先看下面三个图.

其中 a)和c)都不是仙人掌图,因为 a)不是强连通的、c)中的红弧同时属于两个圈 1?2?3?4?1 和1?2?4?1. b)就是一个仙人掌.直观的说,仙人掌图就是一个一个的圈直接"粘"在一起的图,圈 之间没有公共边. 于是我们很容易得到这样的一个算法:每次找一个圈,如果圈中不相邻的点之间有边, 那么该图就不是仙人掌;

否则把圈缩成点,然后把圈、点、边的关系进行适当的调整,继续 缩圈. 权且不说具体该如何调整圈、点、边的关系,光是缩点这一项就要大费周章.该算法的 思维和编程复杂度将非常高. 本文要介绍的另一个种算法是 DFS.对该图进行 DFS 遍历,建立 DFS 树. 譬如下图: 如果一个图是仙人掌的话,它的 DFS 生成树有什么特点呢?分析 DFS 树的一般方法是 从逆向边和横向边入手. 首先考虑它的横向边. a)非强连通 b)仙人掌图 c)红色的弧同时 属于两个圈

1 2

3 4

1 2

3 4

5 6

7 1

2 4

5 3

7 6 a)图b)DFS 树 上面 a)图中的红边是横向边. 蓝点是红点的祖先, 称从蓝点遍历到红点的这条路为红点 的"祖先路径" ,记作 P.因为仙人掌图强连通,所以必须存在一条从红点到蓝点的路. 如果这条路不和 P 相交,则如 b)图所示;

如果这条路和 P 相交,则如 c)图所示.不论 是b)图还是 c)图,蓝色的点和边都同时隶属两个圈.也就是说,只要存在横向边,这棵 DFS 树的原图就肯定不是仙人掌图. 所以: 性质

1 仙人掌图的 DFS 树没有横向边. 下面我们进一步考虑逆向边. 对于每个节点 v,定义两个函数: 1. DFS(v)表示 v 在DFS 树中是第几个被遍历到的点. 2. Low(v)表示通过从 v 以及 v 的所有后代直接指出去的边, 可以访问到的 DFS 值最小 的点的 DFS 值. 通过下图读者可以对 DFS 和Low 的定义获得一个更感性的认识. …… …… …… a)横向边 b)不相交 c)相交

1 2

4 3

6 5 1(1,1) 2(2,1) 4(3,1) 3(4,4) 5(5,4) 6(6,4) a)原图 b)DFS 树 括号中第一个数是 DFS 值, 第二个是 LOW 值DFS 函数的求解可以通过设立一个计数器,在深度优先遍历的时候每碰到一个新的点 就累加

1 来实现. Low 函数的计算如下: Low(v)=min{DFS(v), Low(u)} (其中 u 是v的儿子) 下面考虑某一个点 v.如果它存在一个儿子 u 满足 Low(u)>DFS(v),那么这个 DFS 树的 原图肯定不是仙人掌. 如上图所示,因为 Low(u)>DFS(v),所以 u 以及 u 的后代都被限制在红色的线圈范围之 内,没有指出去的逆向边.这样就成了桥.我们知道在一个强连通图中是不可能有桥 的,所以: 性质

2 Low(u)