图论导引 - 第三章第一节：连通性

章节概述

第三章（Paths and cycles）主要讲述了路径和循环相关的图论知识，包括四个部分：连通性、欧拉图、哈密顿图、一些相关算法应用。

连通性 Connectivity

通道 walk

给定一个图 $G$ ， $G$ 中的一条通道（或称为**“链”）是形如 $v_{0}v_{1}、v_{1}v_{2}、··· 、v_{m - 1}v_{m}$ 的有限边序列**，也可记为 $v_{0} \to v_{1} \to v_{2} \to \cdots \to v_{m}$ ，其中任意两条连续的边是相邻的或相同的。

一条通道确定了一个顶点序列 $v_{0},v_{1},···,v_{m}$ 。
我们称 $v_{0}$ 为通道的起始顶点（initial vertex）， $v_{m}$ 为通道的终止顶点（final vertex），并说这是一条从 $v_{0}$ 到 $v_{m}$ 的通道。
通道中的边数称为其长度（length）。

在这里插入图片描述

迹 trail 和路径 path

所有边都互不相同的通道是一条迹（trail）。
此外，如果所有顶点 $v_{0}, v_{1}, \cdots, v_{m}$ 都互不相同（除了 $v_{0}=v_{m}$ ），那么这条迹就是一条路径（path）。
- 如果 $v_{0}=v_{m}$ ，则路径或迹是封闭的（closed），并且包含至少一条边的封闭路径是一个圈（cycle）。
- 注意，任何环（loop）或一对多重边都是一个圈。

在这里插入图片描述

连通图

当且仅当每对顶点之间都存在一条路径时，图是连通的。

在这里插入图片描述

二部图 Bipartite Graph

当且仅当 $G$ 的每个圈(cycle)都具有偶数长度时， $G$ 是二分图。

定理5.1：如果 $G$ 是一个二分图，那么 $G$ 的每个圈都具有偶数长度。

证明：

因为 $G$ 是二分图，所以我们可以将其顶点集划分为两个不相交的集合 $A$ 和 $B$ ，使得 $G$ 的每条边都连接 $A$ 中的一个顶点和 $B$ 中的一个顶点。
设 $v_{0} \to v_{1} \to \cdots \to v_{m} \to v_{0}$ 是 $G$ 中的一个环，并且假设 $v_{0}$ 在 $A$ 中。那么 $v_{1}$ 在 $B$ 中， $v_{2}$ 在 $A$ 中，依此类推。由于 $v_{m}$ 必定在 $B$ 中，所以这个回路的长度肯定是偶数。

简单连通图的边数限制

一个具有 $n$ 个顶点的简单连通图，当没有回路时边数最少，为 $n - 1$ 条边；当该图是完全图时边数最多，为 $n (n - 1) /2$ 条边。

定理5.2：设 $G$ 是一个具有 $n$ 个顶点的简单图。如果 $G$ 有 $k$ 个连通分量，那么 $G$ 的边数 $m$ 满足 $\leq m \leq (n - k)(n - k + 1)/2$ 。

证明：

证下界：
- 假设每个连通分量 $C_i$ 中有 $n_i$ 个顶点，图 $G$ 的总顶点数为 $n=\sum_{i=1}^{k} n_{i}$
- 一个连通分量中， $n_i$ 个顶点至少有 $n_i-1$ 条边连接
- $k$ 个连通分量，至少有 $\sum_{i=1}^{k} (n_{i}-1)$ 条边，计算 $\sum_{i=1}^{k} (n_{i}-1)=\sum_{i=1}^{k} n_{i}-k=n-k$
- 对于 $k$ 个连通分量，至少有 $n - k$ 条边，得证。
证上界：
- 为了证明上限，假设 $G$ 的每个连通分量都是完全图，这样才有可能达到最多的边数。
- 假设有两个连通分量 $C_{i}$ 和 $C_{j}$ ，分别有 $n_{i}$ 个和 $n_{j}$ 个顶点，其中 $n_{i}\geq n_{j}>1$ 。如果我们用具有 $n_{i}+1$ 个顶点和 $n_{j}-1$ 个顶点的完全图分别替换 $C_{i}$ 和 $C_{j}$ ，那么顶点总数保持不变，而边的数量变化为
  $\{\frac{(n_{i}+1)n_{i}-n_{i}(n_{i}-1)}{2}\}-\{\frac{n_{j}(n_{j}-1)-(n_{j}-1)(n_{j}-2)}{2}\}=n_{i}-n_{j}+1$
- 由于 $n_i-n_j+1$ 肯定是一个正数，因此边数在增多。为了让边的数量最大，需要不断增加一个连通分量的顶点，减少另外连通分量的顶点。
- 由此可知， $G$ 必须由一个具有 $n - k + 1$ 个顶点的完全图和 $k - 1$ 个孤立顶点组成。
- 具有 $n - k + 1$ 个顶点的完全图的边数为 $(n - k) (n - k + 1) /2$ ，得证。

推论5.3：任何具有 $n$ 个顶点且边数多于 $(n - 1) (n - 2) /2$ 的简单图都是连通的。

证明：

把任意一个图 $G$ 分成包含 $n - 1$ 个顶点的子图和一个顶点 $n_0$
只需要保证包含 $n - 1$ 个顶点的子图是完全图，再用其余的边连接最后一个顶点 $n_0$ 。
顶点个数为 $n - 1$ 的完全图的边数为 $(n - 1) (n - 2) /2$ ，那么只要边数多余 $(n - 1) (n - 2) /2$ 则整个图 $G$ 必定是完全图。

断集、割集和桥

如何衡量一个连通图的连通性有多强？
- 看看移除多少条边或顶点才能使连通图不连通
- 点连通度、边连通度
断集 disconnecting set
- 在连通图 $G$ 中，一个断集是一组边的集合，移除集合中的这些边会使 $G$ 不连通。断集是使得图失去连通性的边集。
割集 cutset
- 一个断集的任何真子集都不是断集，则称该断集为割集。
- 移除割集中的边总是会留下一个恰好有两个连通分量的图。
- 在上图 5.3 中， ${e_3,e_6,e_7,e_8\}$ 是割集。
桥 bridge
- 如果一个割集只有一条边 $e$ ，我们称 $e$ 为桥。
边连通度 $\lambda(G)$
- 如果 $G$ 是连通的，它的边连通度 $\lambda(G)$ 是 $G$ 中最小割集的大小。因此， $\lambda(G)$ 是为使 $G$ 不连通而需要删除的最少边数。
- 如果 $\lambda(G)\geq k$ ，那么 $G$ 是 $k$ 边连通的。

分离集和割点

分离集 separating set
- 在连通图 $G$ 中，一个分离集是一组顶点，删除这些顶点会使 $G$ 不连通；当删除一个顶点时，也会移除与顶点关联的边。
割点 cut-vertex
- 如果一个分离集只包含一个顶点 $v$ ，我们称 $v$ 为割点。
点连通度 $\kappa(G)$
- 如果 $G$ 是连通的且不是完全图，它的顶点连通度 $\kappa(G)$ 是 $G$ 中最小分离集的大小。 $\kappa(G)$ 是为使 $G$ 不连通而需要删除的最少顶点数。
- 如果 $\kappa(G)\geq k$ ，那么 $G$ 是 $k$ 连通的。
- 可以证明，如果 $G$ 是任何连通图，那么 $\kappa(G)\leq\lambda(G)$ 。
  - 直观理解，一个顶点可能与多条边相关联，删除一个顶点可能会导致与该顶点相连的所有边都失去作用，从而更容易使图变得不连通；而删除一条边只会影响与该边直接相关的两个顶点之间的连接。
  - 所以，为了使图不连通，需要删除的顶点数量通常不会超过需要删除的边的数量，即点连通度一般小于等于边连通度。