Zobin

Lovin' Tech with Tea

图和简单图

⚠ 转载请注明出处：作者：ZobinHuang，更新日期：March.2 2022


知识共享许可协议

    本作品由 ZobinHuang 采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。


目录

有特定需要的内容直接跳转到相关章节查看即可。

正在加载目录...

数学前置知识

    在开启图论之旅之前，我们首先对必要的数学前置知识进行回顾。

充分条件和必要条件

    上图诠释了充分条件的概念。充分条件可以理解为数字电路中的 "或" 门。如果 `A` 是 `B` 的充分条件，则只要 `A` 满足，则 `B` 也成立。而使得 `B` 成立的条件有可能不止有 `A` 一个。

    上图诠释了充分条件的概念。必要条件可以理解为数字电路中的 "或" 门。如果 `A` 是 `B` 的必要条件，则 `A` 只是使得 `B` 成立的条件中的一环。如果 `A` 成立，`B` 不一定成立；但是如果 `A` 不成立，则 `B` 一定不成立。

    在一个命题 `p \rightarrow q` 中，`p` 是 `q` 的充分条件，而 `q` 是 `p` 的必要条件。事实上，充分条件与必要条件是同一个命题的两个不同视角，其阐明的是命题中条件与结论的逻辑关系。

    由上面的分析可得，如果 `A` 是 `B` 的充要条件，则说明只有 `A` 能证明 `B`，也即 `A` 是导致 `B` 的唯一因素，因此这是一种对称的关系，也即「`B` 是 `A` 的充要条件」也成立。

反证法

    基于上面的「充分条件」和「必要条件」的理解，现在让我们来提供在图论中经常出现的反证法的思路。

    以我们要证「`A` 是 `B` 的充分条件」(i.e. `A` 成立就有 `B` 成立) 为例，如果我们无法正面证明，我们其实可以转而证明「`\bar{A}` 是 `\bar{B}` 的必要条件」(i.e. 如果 `\bar{A}` 不成立，则 `\bar{B}` 一定不成立)，因为如果我们能证明后者，那么根据我们原本要证明的命题的假设 `A` 是成立的，则 `\bar{A}` 一定不成立，则 `\bar{B}` 也就不成立，则就有 `B` 成立。

关于图的一些定义

    图论是离散数学涉及的学科之一 (p.s. 图论、群论 & 数论)。图用于描述事物间的二元关系。

    记一个有序二元数组 `G=(V,E)` 成为一个图，其中 `V` (Vertex) 为 `G` 的 顶点集，其不为空集，其元素称为 顶点 (点); `E` (Edge) 为 `G` 的 边集，它的每一个元素称为 边，它联结 `V` 中的两个点，且如果两个点是无序的，则为 无向边，否则为 有向边。

    使用 `n(G)` 来表示一个图的顶点数，`m(G)` 来表示一个图的边数，`d(v)` 表示一个点的 度 (degree)。

    图和点的关系是不对等的: 一个图有点不一定有边，有边一定有点。

简单图

    关于图，还有如下相关概念:

  1. 平凡图: 只有一个顶点的图
  2. 空图: 只有点没有边的图
  3. 有限图: 顶点个数有限的图，反之则是无限图
  4. 重边: 如果有多条两个顶点相同的边，则说这些边是重边 (p.s. 注意对于有方向的边，如果两端顶点相同，方向不同，则不是重边)
  5. 环: 如果一条边上的两个点是一样的，则这条边是环;
  6. 相邻: 两个点相邻则说明它们之间有边将它们连接起来; 两条边相邻则说明它们之间有公共连接的点;
  7. 相关联: 用于描述点与边之间的关系

    没有环和没有重边的图称为 简单图，简单图是图论研究的重点。

图的同构

    图 `G_1=(V_1, E_1)` 和图 `G_2=(V_2, E_2)`，若存在双射 (i.e. 一一映射) `f: V1 \rightarrow V_2`，使得对任意 `a, b \in V_1`，`(a,b) \in E_1` `\leftrightarrow` `[f(a), f(b)] \in E_2`，并且 `(a,b)` 和 `[f(a), f(b)]` 有相同重数，则 `G_1` 和 `G_2` 同构，记为 `G_1 \cong G_2`。

    上面的数学概念总结起来就是两个条件: [1] 点的一一映射关系 和 [2] 相同的点邻接关系。

    判断两个图不同构的方法：首先必须保证顶点的一一映射关系 (i.e. [1] 数量要相同; [2] 各个度数的点能否进行对应)，然后边数要相同，然后看一些特殊的邻接关系能否进行对应 (e.g. `G` 有三个点两两相邻, `G'` 是否存在; `G` 中唯二的度数为 4 的点相邻，`G'` 中是否相邻)。

    基于顶点数目和边的数目，构造所有可能的非同构的简单图的方法论：从顶点度数最大的值从大往小找。

更多概念

完全图

    完全图: 任意两个顶点都是相邻的简单图，记为 `K_n`，其中 `n` 是图中点的数目。

    完全图的边数 `m(K_n) = C_{n}^{2} = \frac{n(n-1)}{2}`，每个顶点的度数都为 `d(v)=n-1`。

    顶点数相同的两个完全图同构。

    完全图增加/删除一个点后仍然是完全图。

二部图

    偶图/二部图 (Bipartite Graph): 可以把一个图的顶点集分为两个集合 `X` 和 `Y`，且保证 `X` 中的顶点是互不相邻的，`Y` 中的顶点也是互不相邻的。

    判断一个图是否是二部图的办法: 对顶点进行 0/1 标号，判断是否有顶点之间的邻接关系存在冲突，若全图不冲突则为偶图。

    如果完全图 `K_{n}` 的 `n \ge 3`，则其一定不是二部图。

    快速判断是否是二部图的一个定理:

一个图是二部图当且当它不包含奇圈

    下面我们就上述定理的必要性 (从左向右) 和充分性 (从右向左) 进行证明。

    必要性显然: 设 `G` 是具有二分类 `(X, Y)` 的二部图, 并且 `C = v_0v_1… v_kv_0` 是 `G` 的一个圈。不失一般性, 可假定 `v_o \in X`。一般地，`v_{2i}\inX`，`v_{2i+1}\inX`。又因为 `v_0\inX`，因此 `C` 是偶圈。

    充分性: 我们在 `G` 中任意选取点 `u`，然后定义 `V(G)` 的分类如下:

  • `X={x|d(u,x)` 是偶数, `x\inV(G)}`
  • `Y={y|d(u,y)` 是奇数, `y\inV(G)}`

    现在我们尝试基于图 `G` 不包含奇圈的已知条件来证明 `X` 和 `Y` 是图 `G` 的二部划分。

    首先我们证明在 `X` 中的任意两点 `v` 和 `w` 都不相邻。设 `P` 是一条最短 `(u,v)` 路，`Q` 是一条最短 `(u,w)` 路，`u_1` 是 `P` 和 `Q` 的最后一个交点。由于 `P` 和 `Q` 是最短路，所以 `P` 和 `Q` 中 `u` 到 `u_1` 段的距离相同，因此奇偶性相同。又因为 `P` 和 `Q` 的长度是偶数，所以 `P` 和 `Q` 中 `u_1v` 段和 `u_1w` 段的奇偶性也相同。因此此时如果 `v` 和 `w` 邻接，则会形成奇圈，与已知条件矛盾。

    然后我们可以使用同样的道理证明在 `Y` 中的任意两点也不相邻，此处略去证明。

    综合上述关于二部图的性质，总结起来就是：要证明一个图是二部图，则需要找到二部划分；要证明一个图不是二部图，仅需找到一个奇圈。

完全二部图

    完全二部图: 有三层意思: [1] 偶图; [2] `X` 中的一个点和 `Y` 中的任意一个点邻接; [3] 简单图。记完全偶图为 `K_{m,n}`，其中 `m` 和 `n` 分别为集合 `X` 和 `Y` 的顶点的个数。

    若 `m,n \ge 2`，则完全二部图增加/删除一个点后仍然是完全二部图。

    完全二部图 `K_{m,n}` 的顶点数为 `n(K_{m,n}) = m+n`。

    完全二部图 `K_{m,n}` 的边数为 `m(K_{m,n}) = m \cdot n`

    完全二部图中顶点的度数有两种情况: `d(v)=m, v \in X` 或 `d(v)=m, v \in Y`。

补图

    对于一个简单图 `G=(V,E)`，令 `E_{1} = {uv|u \ne v, u,v \in V}`，则称图 `H=(V,E_{1})` 为图 `G` 的 补图 (Complement Graph)，记为 `H=\bar{G}`。

    完全图 `G` 的补图是一个以 `V(G)` 为顶点集的空图，也叫做 独立集 (Independent Set)。

    如果一个图 `G` 的补图和其自身同构，则其为 自补图 (Self-complementary Graph)。

自补图拥有性质: `n(G) \mod 4 = 0,1`

    证明: 由于 `G \cong \bar{G}`，故 `m(G) + m(\bar{G}) = m(K_n) = \frac{1}{2}n(n-1)`，所以 `m(G)=\frac{1}{4}n(n-1)`。

    注意上面的条件是必要条件，自补图一定拥有上述性质，但是拥有上述性质的图不一定是自补图。

度

     `G` 的顶点 `v` 的 度 (degree) `d(v)` 是指 `G` 中与 `v` 关联的边的数目，每个环计算两次。使用 `\delta(G)` 和 `\Delta(G)` 来表示图 `G` 的最大度和最小度。

    奇数度的点称为 奇度点, 偶数度的顶点称 偶度点。

    如果图 `G` 中所有顶点的度都为 `k`，则称该图为 k-正则图 (k-regular)，其中3-正则图为 3 次图 (cubic)。

图论第一定理 (握手定理): 图 `G=(V,E)` 中所有顶点的度的和等于边数 `m` 的 2 倍，也即 `\sum_{v \in V(G)}d(v) = 2m`

    基于上述定理我们可以进而衍生出两个推论:

在任何图中, 奇度点的个数为偶数
正则图的阶数和点数不同时为奇数

    上述两个定理都可以基于握手定理进行证明，这里略去。

度序列

    一个图 `G` 的各个点的度 `d_1`, `d_2`, …, `d_n` 构成的非负整数组 (`d_1`, `d_2`, …, `d_n`)称为 `G`的 度序列 (Degree Sequence)。

    给出一个非负数组，如果它是某简单图的度序列, 我们称它为 可图序列 (Graphic Sequence), 简称 图序列。

    下面我们给出两个用于判断一个序列是否是可图序列的定理:

非负整数组 (`d_1`, `d_2`, …., `d_n`) 是图的度序列的充分必要条件是: `\sum_{i=1}^{n}d(v_i)` 为偶数。

    证明如下:

    充分性: 如果 `\sum_{i=1}^{n}d(v_i)` 为偶数，那么值为奇数的 `d_{i}` 的个数即为偶数。那么我们可以这么作图: [1] 对于 `d_{j}` 为偶数的顶点，作 `\frac{d_{j}}{2}` 个环; [2] 对于 `d_{j}` 为奇数的 `t` 个顶点 (i.e. `t` 为偶数)，首先将这些顶点划分为 `\frac{t}{2}` 组，然后每个组中的两个顶点进行连线，并且各个顶点再作 `\frac{d_{j}-1}{2}` 个环。

    必要性: 如果非负整数组 (`d_1`, `d_2`, …., `d_n`) 是图的度序列，那么根据握手定理可以得出 `\sum_{i=1}^{n}d(v_i) = 2 \cdot m(G)` 为偶数。

非负整数组 `\pi=(d_{1}, d_{2}, ..., d_{n}), d_{1} \ge d_{2} \ge ... \ge d_{n}`, `\sum_{i=1}^{n}d_{i}=2m` 是可图序列的充分必要条件是:
`\pi_{1}=(\underbrace{d_{2}-1, d_{3}-1, ..., d_{d_{1}+1}-1}_{这部分是 -1}, \underbrace{d_{d_{1}+2}, ..., d_{n}}_{这部分是保持不变})` 是可图序列

    上述定理是 Havel-Hakimi 定理，其证明过程此处略。

    另外我们还应该关注一个度序列的性质:

一个简单图 `G` 的 `n` 个点的度不能互不相同

    其证明过程类似于鸽笼问题，如下:

    由于图 `G` 为简单图，故 `\Delta(G) \le n-1`。那么:

  1. 如果图 `G` 没有孤立点，则 `1 \le d(v) \le n-1`, `\forall v \in V(G)`，由鸽笼原理可得至少有两个点度数相同;
  2. 如果图 `G` 有一个孤立点，设 `G_{1}` 表示 `G` 去掉孤立点后的部分，则 `1 \le d(v) \le n-2`, `\forall v \in V(G_{1})`，同理由鸽笼原理，`G_{1}` 中至少有两个点度数相同;
  3. 如果图 `G` 中有两个以上的孤立点，则这两个孤立点本身度数就相同

频序列

    设 `n` 阶图 `G` 的各点的度取 `s` 个不同的非负整数 `d_{1}`, `d_{2}`, …, `d_{s}`. 又设度为 `d_{i}` 的点有 `b_{i}` 个 (i = 1, 2, …, s), 则有 `\sum_{i=1}^{s}b_{i} = n`，故非整数组 `(b_1, b_2, …, b_s)` 是 `n` 的一个划分, 称为 `G` 的 频序列。

一个 `n` 阶图 `G` 和它的补图有相同的频序列.