割点、割边、双连通分支

一、割点、割边、双连通分支概念

挂接点(Articulation point)就是割点（Cut Vertex）
桥(Bridge)就是割边（Cut Edge）

割点：v为割点，则去掉v后，图的连通分支增加。
割边：v为割边，则去掉v后，图的连通分支增加。
割点形式化的定义：a是割点当且仅当存在两个点u,v使得u到v的每条路径都会经过a。（去掉a后，u到v没有路径）
边双连通分支：在连通分支中去掉一条边，连通分支仍连通。
点双连通分支：在连通分支中去掉一个点，连通分支仍连通。
我们这里说的是点双连通分支，因为由定义“任何两条边都在一个公共简单回路，且在一个双连通分支中没有割点，因此是点双连通分支。”。

割点应用场景：
给定一个计算机网络，如果有一个计算机v坏掉了，那么是否任何两个计算机都能够仍然连通？
遇到上述问题，是否能够转化成图论问题呢？
其实这个问题就是看坏掉的计算机是否是割点，如果是割点，则一定存在两个计算机u、v，u和v不连通。

双连通图定义：不存在割点。
双连通分支定义：他是极大双连通子图，就是如果G是双连通分支，则不存在G'，G是G‘的子图，且G’也是双连通分支。

二、一些命题的证明

命题：两个双连通分支之间最多有一个公共点。

证明：假设双连通分支C1、C2，且有两个公共点v1、v2，因为双连通分支划分非桥边，所以v1与v2之间至少有两条边，因此假设v1与v2有两条边，如下图：

首先声明，e1、e2可能是个路径，即由多条边组成，但是我们假设e1与e2为边。
e1在C1中，因此e1与C1中任何一条边都在一个简单回路中，同理，e2与C2中任何一条边都在一个简单回路，因为e1与e2在一个回路，所以e1与C2中任何一条边都在一个简单回路，e2与C1中任何一条边都在一个简单回路，所以C1与C2合并。

命题：两个双连通分支之间的一个公共点是割点。

证明：如果公共点不是割点，则将A点去除后，C1与C2仍然连通，因此必然存在u与v使得(u,v)属于E，因此当A存在时，u到A存在路径，A到v存在路径，u和v之间存在一条边，因此(u,v)与C1中任何一条边都在一个简单回路，(u,v)与C2中任何一条边都在一个简单回路，所以C1与C2合并。

命题：割点一定属于至少两个双连通分支。

证明：如果割点属于一个双连通分支，根据双连通分支定义，去掉任何一个点都不会让图不连通，与割点的定义矛盾。

命题：在一个双连通分支中至少要删除两个点才能够使图G不连通。

证明：双连通分支定义。Trivial。

Equivalence relation：边e1和e2是等价关系的当且仅当e1=e2或e1与e2在一个回路中。
Equivalence Class：一个等价类中的两条边都是等价关系。

命题：对于根顶点u，u为割点当且仅当u有至少两个儿子。

首先说明一点，无向图只有树边和反向边。
=>
已知Gn的根是割点，如果Gn中该根s只有一个子女节点t，则去除了根节点后，其子女节点t仍然连接着分支，这与根s为割点条件不符，因此根至少两个子女。
<=
如果Gn中根有至少两个子女，因为无向图只存在树边、反向边，没有交叉边，因此当根去除后，分支之间不能连接，因此根为割点。

命题：对于非根顶点u，u为割点当且仅当u只要存在一个子顶点s，s的后裔（注意是后裔，不是真后裔）没有指向u的真祖先的反向边。

=>
已知Gn中某个非根节点v是割点，如果任何v的子顶点s，s或s的后裔指向v的真祖先的反向边，我们考虑一个分支，假设反向边为(a,b),其中a为v的子顶点，b为v的真祖先，当v删除后，因为v的真祖先连通，v的子顶点之间连通，如果存在{a,b}的边，则v的真祖先和v的子顶点也连通，与条件矛盾。

<=
如果存在一个子顶点s，不存在s或s的后裔指向v的真祖先的反向边，则v的真祖先区域和v的子顶点区域不连通，因此v为割点。

命题：对于非根顶点u为割点，当且仅当存在相邻子顶点，使得 low[v]>=d[u].

证明：
=>
因为u为割点，因此u有一个子顶点v，不存在v或v的真后裔顶点指向u的真祖先的反向边。
因为 low[v] = min { d[v], d[w]}，其中对于v的后裔u，(u,w)为反向边。
因为d[w]>=d[u],所以low[v]>=d[u].

<=
因为low[v]>=d[u]，所以 low[v] = min { d[v], d[w]}>=d[u]，因为d[v]>=d[u],所以d[w]>=d[u],所以w为u的后裔。
所以不存在v，v或v的子顶点存在指向u的真祖先的反向边，因此u为割点。

命题：(u,v)是桥，当且仅当low[v]>d[u].

证明：
=>
已知(u,v)是桥，则此边不在任何简单回路中，不失一般性，先访问u,再访问v，则low[v]=min { d[v], d[w]}, d[w]>d[u],所以low[v]>d[u].
<=
已知low[v]>d[u]，所以d[w]>d[u],所以不存在v或v的子顶点，(v,w)为反向边，且w是u的后裔，所以(u,v)不属于简单回路，所以是桥。

命题：双连通分支的任意两条边位于同一个简单回路等价于双连通分支中没有割点。

证明：
如果存在割点u，设与u相邻的点为v1,v2,....vn，则因为u去掉后，应该使得v1...vn中的至少其中一个顶点和u不连通，假设此点为vi,但是根据双连通分支的定义，(u,vi)位于简单回路，因此根据定义u和vi应该仍然连通，所以矛盾。

三、求割点、割边、双连通分支实现

[java]
Find articulation points , cut edge and biconnected components
       time = 0
       STACK := Λ
       forall vertices v do color[v] = WHITE;
       SEARCHB(1)

    SEARCHB(v)
       color[v] := GRAY
       time = time + 1
       d[v] := time
1:     LOW[v] := d[v]
       for each w 属于 Adj[v]
          if (v,w) is not yet on the stack (parent[v]!=w)
             then put (v,w) on STACK
          if color[w] = WHITE then
             FATHER[w] := v
             SEARCHB(w)
         if LOW[w] > d[v] (v,w) is cut edge. //cut edge
             if LOW[w] ≥ d[v]
                v is an articulation point
                and the next biconnected component is       //biconnected components
                the set of edges popped from STACK up to and including (v,w)
2:           LOW[v] := min{ LOW[v], LOW[w] }
          else if w ≠ FATHER[v]
3:           LOW[v] := min{ LOW[v], d[w] }

补充：综合编程 , 其他综合 ,