Graph Theory and Network Algorithm 1 图的连通性

发表于 2020-11-22 更新于 2022-04-08 分类于 UCAS ， Courses 阅读次数：

图论与网络算法 (070105M04003H)，图的连通性。

图的连通性

概念

割点：$v\in V(G):w(G-v)>w(G)$。
割边：$e\in E(G):w(G-e)>w(G)$。
点割集：$V'\in V(G):w(G-V')>w(G)$；
- k-点割集；极小点割集；最小点割集；
割点是1-点割集；
完全图没有点割集。
连通度：$\kappa(G)=\min\{|V'|:V'是连通图G的点割集\}$；
- $\upsilon$阶完全图的连通度为$\upsilon-1$，不连通图的连通度为$0$；
- 若$\kappa (G)\ge k$，称$G$为k-连通的。
边割集：$[S,\bar{S}]:S\subset V(G),\bar{S}\subset V(G)-S$；
- k-边割集；极小边割集；最小边割集；
- $[S,\bar{S}]$表示一端在$S$一端在$\bar{S}$中的所有边的集合；
一条割边是$1$-边割集；
- $G-E'$不连通$\nRightarrow E'$是边割集。
边连通度：$\kappa'(G)=\min\{|E'|:E'是连通图G的边割集\}$；
- $\upsilon$阶完全图的边连通度为$\upsilon-1$，不连通图的边连通度为$0$；
- 若$\kappa' (G)\ge k$，称$G$为k-边连通的。

块（block）：无割点的连通图。
图$G$的一个块：$H$是块，且是$G$中具有此性质的极大子图。
- 若$\upsilon\ge3$，则块$\Longleftrightarrow$2-连通图；
- $K_2$是块，却是1-连通图。

定理

Theorem 2.1.1

对连通图$G$，$v$是$G$割点$\Longleftrightarrow G-v$不连通；

Theorem 2.1.2

对简单图$G$，$v$是$G$割点$\Longrightarrow E(G)$可划分为非空子集$E_1$和$E_2$，$s.t.\ V(G[E_1])\cap V(G[E_2])={v}$。

Theorem 2.1.3

对树$T$，$v$是$T$割点$\Longleftrightarrow d(v)>1$。

$\Longrightarrow$ 反证。

$\Longleftarrow$ 运用树中任意两顶点间路的唯一性（树的等价定义2）。

每个非平凡无环连通图至少有两个顶点不是割点。

设$T$是$G$的生成树，
则$T$至少有两个叶子（非平凡树至少含有两个一度顶点），这两个顶点不是割点。

Theorem 2.1.4

设$v$是连通图$G$的一个顶点，则下列命题等价：

$v$是$G$的割点；
$\exists u,w\in V(G):u,w\ne v,\ v$在每条$(u,w)$路上；
$\exists V(G)-{v}$的一个划分$U,W,\ s.t.\ \forall u\in U,\forall w\in W: v$在每条$(u,w)$路上。

$1\Longrightarrow3$ 将$G-v$的两个连通分支令为$U,W$；

$2\Longrightarrow3\Longrightarrow1$。

Theorem 2.1.5

$e$是$G$割边$\Longleftrightarrow e$不在$G$的任何圈中。

考虑其逆否命题。

Theorem 2.1.6

一个连通图是树$\Longleftrightarrow$它的每条边都是割边。

连通图$G$是树$\Longleftrightarrow$$G$无圈$\Longleftrightarrow$$\forall e$不在圈上$\Longleftrightarrow \forall e$是$G$割边。

Theorem 2.1.7

设$e$是连通图$G$的一条边，则下列命题等价：

$e$是$G$的割边；
$e$不在$G$的任何圈上；
$\exists u,v\in V(G):e$在每条$(u,v)$路上；
$\exists V(G)-{v}$的一个划分$U,W,\ s.t.\ \forall u\in U,\forall w\in W: e$在每条$(u,w)$路上。

$1\Longleftrightarrow2$（Theorem 2.1.5）；

$1\Longrightarrow4\Longrightarrow3\Longrightarrow1$。

与Theorem 2.1.4的叙述和证明类比。

Theorem 2.2.1

$\kappa(G)\le \kappa'(G)\le \delta(G).$

左：对$\kappa'(G)$做数学归纳法，当$\kappa'(G)=k+1$，设$(k+1)$-边割集$E_1$，$\forall e\in E_1$，考虑$G-e$，其最小边割集为$E_1-e$ ；

右：考虑$v:d(v)=\delta$，删去与其相邻的所有边。

Theorem 2.2.2

$\kappa(G)\le\lfloor\frac{2\epsilon}{\upsilon}\rfloor.$

由Theorem 1.1.1（度边关系）和Theorem 2.2.1得证；

（边）连通度$\le\delta\le$平均度。

Theorem 2.2.3

简单图$G$，$k\in\mathbb{N},\delta(G)\ge\frac{v+k-2}{2}\Longrightarrow G$是k-连通的。

反证，假设$\exists S:|S|<k,G-S$不连通，则至少由一个连通分支$G'$含有不超过$\frac{v-|S|}{2}$个顶点，分析$\forall v\in G'$的顶点度$\le \frac{v-|S|}{2}+|S|-1$（度的来源只可能是$G'$和$S$中的点），与$\delta$矛盾。

简单图$G$，$\delta(G)\ge\frac{v-1}{2}\Longrightarrow G$是连通图。

Theorem 2.2.3中令$k=1$。

Theorem 2.2.4

简单图$G:diam\ G=2\Longrightarrow\kappa'(G)=\delta(G)$。

图的直径：$diam\ G=\max\limits_{v\in V(G)}e(u)=\max\limits_{uv\in E(G)}d(u,v)$；

非空简单图$G:\forall u,v:uv\notin E(G),d(u)+d(v)\ge\upsilon-1\Longrightarrow\kappa'(G)=\delta(G)$。
简单图$G:\delta(G)\ge\frac{\upsilon-1}{2}\Longrightarrow\kappa'(G)=\delta(G)$。

以上是使边连通度$\kappa'$达到上界$\delta$的三个条件。

Theorem2.3.1 (Whitney, 1932)

$\upsilon\ge3$的图$G$是2-连通图（块）$\Longleftrightarrow G$中任两顶点共圈。

$\Longleftarrow$ 即证$\forall w\in V(H):w$不是割点，对$\forall u,v\in G-w$，证其在$G-w$有路相连。

$\Longrightarrow$ 对距离$d(u,v)$做归纳法。当$d(u,v)=1$时，$\kappa'\ge\kappa\ge2$（Theorem 2.2.1），故$G$是2-边连通的，即$G$没有割边，故$G-uv$仍然连通$\dots$当$d(u,v)=k$时，考虑长为$k$的路$u\dots wv$，则$d(u,w)=k-1\dots$

$\upsilon\ge3$的图$G$是2-连通图（块）$\Longleftrightarrow G$中任二顶点被至少两条内部无公共顶点的路所连。

考虑取此二顶点所在圈的两半作为路。

$\upsilon\ge3$的图$G$是2-连通图（块）$\Longleftrightarrow G$任二边都位于同一圈上。

在两边中加入一个顶点构成一个新图后使用Whitney定理。

Theorem 2.3.2

连通图$G:\upsilon\ge3$，下列命题等价：

$G$是2-连通的（块）；
$G$的任二顶点共圈；
$G$的任一顶点与任一边共圈；
$G$的任二边共圈；
$\forall u,v\in V(G),\forall e\in E(G),\exists(u,v)$路含有边$e$；
$\forall u,v,w\in V(G), \exists(u,v)$路含有顶点$w$；
$\forall u,v,w\in V(G),\exists(u,v)$路不含有顶点$w$。

$1\Longleftrightarrow2$ Whitney定理；

$1\Longrightarrow3,4$ 在边上加入一个顶点构成一个新图后使用Whitney定理；

$3\Longrightarrow5$ 考虑$e$的两端不与$u,v$重合的情况，$e$分别与$u,v$共圈，总能取出这样的路；

$5\Longrightarrow6$ 易证；

$6\Longrightarrow7$ $\exists(u,w)$路含有$v$，故$(u,v)$路不含$w$；

$7\Longrightarrow1$ $w$不是割点。

由6可知$\forall u,v,w\in V(G):\exists(u,v)$路含有$w$，$\exists(v,w)$路含有$u$，$\exists(w,u)$路含有$v$，但不能推出$u,v,w$共圈，反例如下图：

Theorem 2.3.3

连通图$G:\upsilon\ge 3$，点$v$是$G$的割点$\Longleftrightarrow v$属于$G$的两个不同的块。

算法

求图的块的算法

- 思想：
- 复杂度：$O(\upsilon\cdot\epsilon^2)$

练习

证明：若$G$是连通简单图，但不是完全图，则$G$中$\exists u,v,w:uv,vw\in E(G),uw\notin E(G)$。

在$G$的最小点割集中任取一点$v$
（由完全图不存在点割集想到），在$G-v$的两个连通分支各取一点$u,w$满足条件。

证明：当$k\ge2$时，k-正则二部图没有割边。

证其每条边都在某个圈中。

证明：$\forall v\in G:\kappa(G-e)\ge \kappa(G)-1$。

证明过程比较复杂，可以设最小点割集为$V$，对$e$的来源分类讨论（注意不连通、完全图等特殊情况）

设$H\subseteq G$。举例说明有可能$\kappa(G)>\kappa(G)$。

考虑两个高阶完全图中各去一个顶点相连。

对不是块的连通图，至少有两个块，它们每个恰含有$G$的一个割点。

将块和割点作为顶点构造块-割点图$H$，
证其为树，由非平凡树至少由两个叶子得证；
取割点间最短路中最长的一条$P=v_1...v_2$，
可以取到含有$v_1/v_2$但不含$P$的块；

对$\upsilon$做数学归纳法。

连通图$G$所有的块为$B_1,B_2,...,B_k$，证明$G$恰有$\sum\limits_{i=1}^k \upsilon(B_i)-k+1$个顶点。

将$G$看成从一个块开始，逐次通过在公共割点处添加块形成，
即从$\upsilon(B_1)$开始依次添加块，在添加第$i$个块时，点数增加$\upsilon(B_i)-1$；

对块数做数学归纳法。

连通图$G:\upsilon(G)\ge3$，在$G$中距离为$2$的顶点对间全部添加新边，所得图记为$G'$，证明$G'$是2-连通的。

证$\forall u,v\in G:u,v$共圈，分$d(u,v)=1$，$d(u,v)\ge2$为偶数，$d(u,v)\ge3$为奇数三类情况，考虑$u,v$间最短路；

反证，假设由割点$v$，其必与$G-v$的两个连通分支有旧边相连，考虑与$v$相邻且在不同连通分支的两点，这两点相邻，矛盾。

k-连通图$G$，$v_1,v_2,...v_k$为其$k$个不同顶点。给$G$添加一个新顶点$w$，并将$w$与上述$k$个顶点都连上边，记此图为$G'$,求证$\kappa(G')=k$。

即证$\kappa(G')\ge k$，$\forall v_1,v_2,...v_{k-1}\in G'$，按此顶点集合中是否含有$w$讨论，可推出其不是点割集。

总结

证割点个数时可以考虑原图的生成树。
考虑逆否命题。
对不连通的$\upsilon$阶图，其至少存在一个连通分支含有不超过$\frac{\upsilon}{2}$个顶点。
证一个图是k-（边）连通的，即证其没有大小为$k-1$的点（边）割集。
已知非完全图，考虑取其最小点割集。