Kosaraju算法的证明

首先提出图的转置的概念。所谓转置就是将一个图上所有的有向边反向。简单来说就是本是x->y的一条边,现在变为y->x这样一条边。

另外强连通性质具有传递性,如果(i,j),(j,k)属于同一强连通分量,那么(i,k)属于同一强连通分量。因为如果满足题设,那么存在路径i->j->k和k->j->i。所以传递性得证。所以其实我们要求点i所属的极大强连通分量,只需要把所有和i可以互达的点求出来就可以了。

该算法的流程如下:

1、 利用深度优先搜索遍历原图,并按出栈的先后顺序把点放进一个线性表里。这里可以每次取任意一个点出发DFS,如果还有点未被DFS到,那么继续任选未被遍历到的点出发DFS。

2、 将整个图转置。

3、 按照线性表中的出栈顺序,从后往前依次作为起点DFS。每次DFS到的就是一个强连通分量。

初看这个算法很神奇,但是其实是不难证明的。

命题1:该算法求出的都是强连通分量

假设在后来转置后的图中从x dfs到了 y处,说明存在路径x->y。因为这是在转置图中,所以说明原图中存在路径y->x

然后另外一个信息就是x的序号在y之后。这有两种可能:

1、以y为根先DFS出了一棵搜索树(可以认为是整个搜索树的一棵子树),但是这棵子树里不包含x,并且此时x还未被dfs到。(利用反证法,如果这棵子树里包含了x,那么x的序号会在y之前)

2、y是x扩展出来的搜索树中的一个结点。

综合两个条件,综合两个条件取交。那么上面两种可能中的第一种不成立。因为存在路径y->x,所以如果x未被dfs到,一定会被y为根的搜索树包含的。于是只剩下第二种可能,那么第二种情况表明存在路径x->y。所以x,y可以互相到达。至此证明了该算法求出的都是强连通分量。命题1得证。

命题2:所有的极大强连通分量都会被该算法求到。

命题2等价于:不存在两个点(i,j),他们互相可达,但是没有被放进同一个强连通分量中。易知若(i,j)可以互相到达,那么肯定其中一个点在另外一个点扩展出去的搜索树中(注意DFS的性质,走完一个分叉再走另外一个分叉)。

由于轮换对称,不妨设j在i扩展出去的搜索树中,那么显然j比i先出栈。假如命题2不成立,那么必须是有一棵以A为根(而且这个A必须比i后出栈)的搜索树,它包含了j但不包含i。由命题1可知,(A,j)可互达。那么由于(i,j)可互达,在这颗搜索树中,肯定能有j扩展到i,所以这样的一棵搜索树是不存在的。因此反证得命题2成立。

该算法比Tarjan算法慢一点,但是有一个好处:该算法依次求出的强连通分量已经是拓扑序的。

下面给出这一性质的证明:

对于两个不同的强连通分量A,B,设A中出栈顺序最晚的点为a,B中出栈顺序最晚的点为b。不妨设a出栈顺序在b之前,那么有两种可能。

1、存在路径b->a。由于两点不属于同一强连通分量,所以不存在路径a->b。这种情况下Kosaraju算法会先把B强连通分量拿出来,所以是满足拓扑序的。

2、不存在路径b->a。那么这种情况下必然也不存在路径a->b,否则a出栈之时,b必然已经出栈了。所以,先拿出B强连通分量是符合拓扑序的。

所以,该性质得证。

【写图论教程时无聊证了一下。。。各位无视】

加入对话

5条评论

  1. 回复overture_wy:= =您可能没理解我神马意思,确实是把强连通块分好了。但是这些“强连通块之间”有些题目需要再拓扑排序对吧?比如说求2-SAT的题目。然后这个Kosaraju算法它把强连通块Count出来的顺序就已经是拓扑序了。Tarjan算法依次数出来的强连通块我感觉是逆拓扑序的,但是木有证明。

留下评论

您的电子邮箱地址不会被公开。