无向图的连通性与割点割边

无向图的连通性

1) 无向连通图：若无向图\(G\)上的任意两顶点间都有路径可达，则称\(G\)为无向连通图；

2) 割边(桥)：若删去连通无向图\(G\)的边\(e\)，则\(G\)不再连通，就称\(e\)是\(G\)的一个桥；

3) 割点：若删去连通无向图\(G\)的顶点\(u\)和以\(u\)为端点的边，则\(G\)不再连通，就称\(u\)是\(G\)的一个割点；

4) 无向的点双连通图：若从无向连通图\(G\)删去任意一个顶点剩下的部分还是无向连通图，即若\(G\)上不存在割点，则称\(G\)是一个无向的点双连通图；

5) 无向的边双连通图：若从无向连通图\(G\)删去任意一个变剩下的部分还是无向连通图，即若\(G\)上不存在割边，则称\(G\)是一个无向的边双连通图；

6) 子图：给定有向/无向图\(G’=(V’,E’), G=(V,E)\)，若\(V’\subseteq V, E’\subseteq E\)，则\(G’\)是\(G\)的子图；

7) 无向连通子图：若\(G’\)是无向图\(G\)的子图且\(G’\)是无向连通图，则称\(G’\)是\(G\)的无向连通子图；

8) 极小无向连通子图(无向图的生成树)：若\(G’=(V’,E’)\)是\(G\)的无向连通子图，若在\(V’\)(或\(E’\))仅删去一个元素后得到的图就不再是无向连通子图。则称\(G’\)是\(G\)的一个极小无向连通子图，又称为生成树。这里的“生成”是指生成树可以在DFS/BFS的过程中“生成”，而“树”是指如果指定了生成树上的任意一个顶点作为“树根”，那么生成树就可以转化成普通的树数据结构；

9) 极大无向连通子图(无向图的连通分量)：若\(G’=(V’,E’)\)是\(G\)的无向连通子图，若在\(V’\)(或\(E’\))无法加入其他\(V\)(或\(E\))的元素，或是加入其他元素后的图不再是无向连通子图。则称\(G’\)是\(G\)的一个极大无向连通子图，又称\(G’\)是\(G\)的一个连通分量。无向连通图仅有一个连通分量(即其自身)；

10) 无向图的点双联通分量：极大的点双连通的子图；

11) 无向图的边双联通分量：极大的边双连通的子图；

上述定义刻画了无向图连通性的概念，下面研究割点与割边的性质，以及求割点与割点的算法。

Tarjan算法

割边与割点这两个概念是比较直观的，可看做无向连通图衔接其他部分的“中枢”。容易找到求全部割点和割边的朴素算法：“把所有点或边删一次，在剩下的图的任意顶点DFS，如果DFS不能到达剩下的图的全部顶点，那就说明发现了其中一个割点或割边”。该算法的代价明显是二次函数形式。

为更好的研究Tarjan算法，这里列出几个关于无向图的性质或对无向图的约定：

a) 约定用邻接表存储和表示无向图，且规定邻接表(计为\(adj\))记录无向边\((u,v)\)的方法是“既把\(v\)加入\(adj[u]\)又把\(u\)加入\(adj[v]\)”；

b) 无向图若连通，其DFS森林仅有1个DFS生成树；

c) 无向图的边只能分为树边和反向边(见之前讨论DFS边分类性质的文章)；

Tarjan定义了两个描述完整DFS过程的量：

1) \(dfn[n]\)：顶点\(n\)的子DFS开始的时间戳(序号);

2) \(low[n]\)：顶点\(n\)为根的子DFS树所有节点自身的\(dfn\)或沿1条“不在总DFS树”的边可达的最小\(dfn\);

Tarjan给出了基于上述这两个量的判定割点与割边的定理：

1) 边\((x,y)\)是割边 <=> DFS树中\(x\)是\(y\)的父亲且\(dfn[x] < low[y]\);

证明：首先明确“\((x,y)\)是割边 => \((x,y)\)是任何生成树的边”，若存在割边\((u,v)\)但某次DFS中\((u,v)\)不在DFS生成树上，那么由于这个DFS生成树可作为原图的无向连通子图，故去掉\((u,v)\)后的图还是连通的，与\((u,v)\)是割边矛盾。

然后来看\(dfn[x]<low[y]\)的意义，首先可以确定的是在这次总DFS中，\(y\)子树的全部节点(包括\(y\))仅沿1条不在总DFS树上的边，只能到达\(x\)子树(不包括\(x\))中的某些节点。根据上述(c)无向图边只能是总DFS树的边或反向边，结合该结论可知\(y\)子树(包括\(y\))的全部节点仅沿1条不在总DFS树的边只能到达\(y\)子树(包括\(y\))本身。也就是说整个\(y\)子树(包括\(y\))的全部顶点如果不经过\((x,y)\)边无法到达图中的其他部分。

2) 点\(x\)是割点且\(x\)非总DFS树的根 <=> 总DFS树非根节点\(x\)有第一代孩子\(y\)且\(dfn[x] \leq low[y]\);

证明：不取等号时根据上述(1)有\((x,y)\)是割边，如果删掉\(x\)的话\(y\)子树的所有节点(包括\(y\))都无法到达图的其他部分(比如\(x\)的父亲)，但若\(x\)是根节点的话有可能删了\(x\)后刚好这个图就没有“其他部分”了，所以就先排除掉\(x\)是根节点的情况。取等号时的分析思路基本是也类似上述(1)，取等号时说明\(y\)子树(包括\(x\))最远只可到达\(x\)的反向边，同样的如果删\(x\)就无法到达\(x\)的父亲。对于”<=”方向的证明基本上无需额外分析，可以稍微看一下为什么\(x\)没有孩子就一定不是割点。首先确定\(x\)有至少一条反向边(连父亲的)且没有树边，那很显然去掉它不会改变剩余部分的连通性。

3) 点\(x\)是割点且\(x\)是总DFS树的根 <=> 总DFS树根节点\(x\)有1个以上的第一代孩子；

证明：设总DFS树根\(x\)有2个第一代孩子\(y_1,y_2\)，根据无向图DFS树的特性，\(y_1,y_2\)为根的DFS子树的每个节点都无横向边，也就是说不通过\(x\)的话\(y_1,y_2\)为根的DFS子树互相不可达。存在2个以上第一代孩子同理。如果\(x\)仅有1个第一代孩子\(y\)，那么整个以\(y\)为根的子树的反向边只能是到达子树本身和\(x\)，去掉\(x\)不会改变剩下部分的连通性。

然后先考虑如何实现“DFS+dfn+low”的算法，下面是其步骤：

1) 开始当前顶点(计为\(x\))的子DFS，染灰\(x\)并同时记录\(dfn[x]\)；

2) 对于所有非白色邻接顶点(计为\(g_1,g_2…g_n\))，记录\(low’ = min\{ dfn[x],dfn[g_1]…dfn[g_n]\}\)；

3) 求出所有白色邻接顶点(计为\(w_1,w_2…w_n\))，对每个执行子DFS；

4) 记录\(low[x] = min\{ low’, low[w_1]…low[w_n]\}\)；

5) 染黑\(x\)并结束当前顶点的DFS；

该步骤的正确性无需证明。可以发现该步骤只判断颜色是否为白色，而没有区分灰色和黑色，而是否为白色可以通过\(dfn\)区分，所以可以扔掉标准DFS中记录颜色的量。并且考虑到之后在判断割边割点时需要判断边是否为树边，所以这里额外引入一个量\(p[x]\)用于记录\(x\)在DFS树中的父亲。

另外要注意上述(a)约定用邻接表作无向图的物理结构。这样会导致一个小问题“设\(x\)是\(y\)的DFS树父节点，则在\(y\)的子DFS中会发现一个邻接顶点\(x\)，此时程序会把\((x,y)\)当成反向边处理，但\((x,y)\)实际上是树边”。这个问题较容易解决，只需要在子DFS发现邻接点时额外判断这个邻接点是否为父节点即可。

最后基于“DFS+dfn+low”算法求出的\(dfn,low,p\)，利用\(p\)遍历树边很容易完成割点割边判定。