Learn Tarjan the hard way

写在前面的前面

这是一篇不严格的搬砖文。为了不引起不必要的误解,本文中描述算法的具体记号与Tarjan原文保持一致。注意:本文中部分引理和原文证明方法略有区别。

约定与记号

\(G=(\vartheta,\varepsilon )\)为有向图

路径\(p:v\overset{*}{\Rightarrow}w\)是从\(v\)\(w\)的一条有向简单路径(这里简单路径指顶点序列中每个点都是不同的)

\(G\)通过dfs产生的生成树记为\(T\)

\((v,w)\)\(T\)上的一条边记为\(v\rightarrow w\)

\(T\)上有一条从\(v\)\(w\)的路径记为\(v\overset{*}{\rightarrow}w\)

\(T_{v}\)是以\(v\)为根的\(T\)包含\(v\)的所有子孙的子树(当然也包括\(v\)

本文中所有提到的点的标号都是对应点的dfs

About \(T\)

在理清\(G\)的生成树\(T\)的性质之前谈Tarjan求scc都是耍流氓。

显然边集\(\varepsilon\)中只有两种边,要么在\(T\)的边集内,要么不在,暂且不谈在\(T\)内的边,我们先谈不在\(T\)内的边。

在无向图的双连通分量中我们称之为返祖边,但是当背景转成了有向图,就似乎没有那么简单了。

这些边只会有以下几种(不妨设其为\((v,w)\)):

  1. \(w\)\(v\)的祖先
  2. \(w\)\(v\)的子孙
  3. \(w\)\(v\)的某个祖先的子孙,并且\(w<v\)

在以上几种情况中我们似乎唯独没有提到:\(w\)\(v\)的某个祖先的子孙,并且\(w>v\)的情况。

这当然是有原因的,这和dfs序的性质有关。因为如果这种情况出现了,生成树\(T\)一定不会是现在这种样子。\(v\)一定会强行沿着\((v,w)\)走到\(w\),于是\((v,w)\)将会成为\(T\)中的一条边(然而事实上没有)。

我们称上述的第一种边为frond

第三种边称为cross-link

第二种边因为它对图的连通性没有任何的贡献,我们选择残忍地抛弃之。

注意:对于上述的两种边,Tarjan给了它们一个杀马特即时感的记号\(-\rightarrow\),但是由于我无法在\(\LaTeX\)中找到这个记号,所以我们不妨给它换一个记号叫作,嗯……,譬如说\(\dashrightarrow\)

正题:Strong connectivity

\(G\)是强连通的:对于\(G\)内的任意点对\((u,w)\)都有\(u\overset {*}{\Rightarrow}w\)\(w\overset{*}{\Rightarrow}v\)

我们经常给强连通图一个记号叫作\(C\)

补充一下之前提到的记号:

  • 如果\(G\)是不弱连通(当然弱连通的时候也会出现这种情况)的,那么完全有可能整张图不会通过dfs生成一棵唯一的树,而是一棵生成树森林,我们称之为\(F\)
  • \(F\)和非树边(即\(\dashrightarrow\))构成一个jungle,这很形象

强连通分量在\(F\)中的直观映象

引理:若存在\(p:v\overset{*}{\Rightarrow} w\)\(v<w\)\(v\)\(w\)必然属于同一棵生成树\(T\)\(p\)必然经过\(v\)\(w\)的某一个公共祖先。

证明:按结论顺序证明

  • 假设\(v\)\(w\)不在一棵\(T\)内,那么不妨设\(v\)属于\(T_{1}\)\(w\)属于\(T_{2}\)。那么显然\(T_{1}\)的任意点都小于\(T_{2}\)的任意点,又因为\(v\overset{*}{\Rightarrow} w\),所以\(T_{2}\)事实上会在dfs中和\(T_{1}\)并到一起去。
  • 现在\(v\)\(w\)已经被证明在同一棵生成树中,同理\(p\)中的所有点都在该生成树中。下面Tarjan用了一种比较玄妙的方法证明后一个结论:
  • 他假设包含路径\(p\)上所有点的最小的子树为\(T_{u}\)(即为上图所画)。
  • 先假设有一个待选点集为\(\{T_{u_{1}},T_{u_{2}}\cdots T_{u_{t}}\}\)其中\(u\rightarrow u_{1},u\rightarrow u_{2}\cdots u\rightarrow u_{t}\)并且这个点集恰好覆盖了\(p-\{u\}\)中所有的点。
  • 如果我们能证明\(u\)\(p\)中相当于证明了第二个结论,于是我们把目标放在证明\(u\)\(p\)中上
    • \(v\overset{*}{\rightarrow}w\)那么这是显然的(\(p\)已经经过了它们的公共祖先\(v\)
    • 否则我们把问题放到刚才说的语境中去考虑。我们讨论它的逆否命题:如果\(u\)不在\(p\)
      • \(t=1\)\(T_{u}\)一定不是最小的,\(T_{u_{1}}\)才是最小的
      • \(t\ge 2\):因为我们有了\(u\)不在\(p\)中的先决条件,所以所有需要考虑的边仅存在在子树之内或者是子树之间。事实上如果选择了从一棵序号较大的子树通过cross-link跳到另一棵序号较小的子树上,就无法再跳回来(根据cross-link的性质)
        1. \(v\)\(w\)在同一棵子树内,嗯……,那要剩下的那些子树干什么?
        2. 如果\(v\)\(w\)不在同一棵子树内,那么悲惨的事情是\(v\)永远无法跳到\(w\)(因为\(v<w\)),也就是说这样的\(p\)不存在
      • 所以当\(v\)不是\(w\)的祖先时:不存在\(u\)不在\(p\)中的情况。也就是说,\(u\)\(p\)
    • 综上,\(u\)一定在\(p\)
  • 这样我们就证明了\(p\)必然经过\(v\)\(w\)的某一个公共祖先。

这样的证明似乎很冗长而且根本不优美,Tarjan怎么会写出这样的证明呢(其实是我写的QAQ)?

但是下面的一些结论就应该赏心悦目了。

引理:如果\(v\)\(w\)属于同一个强连通分量,则它们的最近公共祖先也一定属于这个强连通分量。

证明:Without loss of generality,不妨设\(v<w\)。因为\(v\overset{*}{\Rightarrow} w\),所以必然存在\(u\)\(u\overset{*}{\rightarrow}v\)\(u\overset{*}{\rightarrow}w\)使得\(v\overset{*}{\Rightarrow}u\overset{*}{\Rightarrow} w\)。又因为\(w\overset{*}{\rightarrow}v\),所以\(w\overset{*}{\rightarrow}u\)\(\therefore\)\(u\)\(v\)\(w\)属于同一个强连通分量。我们不妨设它们的最近公共祖先为\(u^{'}\),显然有\(u=u^{'}\)\(u\overset{*}{\rightarrow} u^{'}\),同理有\(u^{'}\)一定和\(v,w\)在同一个强连通分量里。

推论:某个强连通分量\(C\)在其搜索树中一定会构成一棵子树(注意:这里的子树并非在约定中说的子树,而是指,嗯……,连通的一大块东西)。我们称\(C\)在搜索树中的树根为该强连通分量的树根。

证明:这似乎很容易证明,通过上述引理可以很轻松地推出来。

这样我们就获得了对SCC的一些直观认识,比如构成它的点一定是在搜索树里集中出现,如果把这些点和关联它们的在\(T\)中的边抠出来,一定会获得一棵树。并且深度最小的那个点我们称之为相应SCC的树根。

Reference

Tarjan R. Depth-first search and linear graph algorithms[C]

Switching and Automata Theory, 1971. Symposium on. IEEE, 2008:114-121.