集合与图论学习笔记05

定义

定义 5.1 边集、点集、有向图、无向图、多重图、简单图、带权图、竞赛图

设 $V$ 是一个非空集，$E$ 是 $V$ 上的二元关系，称有序对 $(V,E)$ 为有向图（directed graph，或 digraph）。$V$ 的元素称为有向图的顶点（vertex），$E$ 的元素称为有向图的边（edge）。如果 $(u,v) \in E$，则称 $u$ 到 $v$ 有一条有向边，记作 $u \to v$。$V$ 称为有向图的顶点集，$E$ 称为有向图的边集（弧集）

设 $V$ 是一个非空集，$E$ 是 $V$ 上的无序二元关系，称有序对 $(V,E)$ 为无向图（undirected graph）。$V$ 的元素称为无向图的顶点，$E$ 的元素称为无向图的边。如果 $\{u,v\} \in E$，则称 $u$ 和 $v$ 之间有一条无向边，记作 $u - v$。$V$ 称为无向图的顶点集，$E$ 称为无向图的边集

如果允许边集中存在重复的边，则称该图为多重图（multigraph）。否则，称该图为简单图（simple graph）

设 $(V,E)$ 是一个有向图或无向图，$w$ 是定义在 $E$ 上的实值函数，称有序三元组 $(V,E,w)$ 为带权图（weighted graph）。$w$ 称为权重函数，$w(e)$ 称为边 $e$ 的权重

设 $(V,E)$ 是一个有向图，且对于任意两个不同的顶点 $u,v \in V$，恰有一条边连接它们（即要么 $u \to v$，要么 $v \to u$），则称该有向图为竞赛图（tournament）

定理 5.1.1

$n$ 个顶点的完全图 $K_n$ 的边数为 $\frac{n(n-1)}{2}$

$n$ 个顶点的完全有向图 $DK_n$ 的边数为 $n(n-1)$

定义 5.2 度、入度、出度

设 $(V,E)$ 是一个无向图，$v \in V$。与顶点 $v$ 关联的边的数目（自环计算两次）称为顶点 $v$ 的度（dree），记作 $d(v)$ 或 $d(v)$。

图 $G$ 中顶点的最小度数称为图 $G$ 的最小度，记作 $\delta(G)$；图 $G$ 中顶点的最大度数称为图 $G$ 的最大度，记作 $\Delta(G)$。

设 $(V,E)$ 是一个有向图，$v \in V$。以顶点 $v$ 为终点的边的数目称为顶点 $v$ 的入度（indree），记作 $d^-(v)$ 或 $d^-(v)$；以顶点 $v$ 为起点的边的数目称为顶点 $v$ 的出度（outdree），记作 $d^+(v)$ 或 $d^+(v)$。

定理 5.2.1

握手定理：在无向图中，所有顶点的度数之和等于边数的两倍，即 $\sum_{v \in V} d(v) = 2|E|$

证明：点击查看证明

证明：设无向图 $(V,E)$ 中有 $m$ 条边 $e_1, e_2, \ldots, e_m$。每条边 $e_i$ 连接两个顶点，记作 $e_i = \{u_i, v_i\}$。则每条边对顶点度数的贡献为 2（因为每条边连接两个顶点）

因此，所有顶点的度数之和为：$\sum_{v \in V} d(v)= \sum_{i=1}^{m} 2 = 2m = 2|E|$

定理 5.2.2

有向图的度数定理：在有向图中，所有顶点的入度之和等于所有顶点的出度之和，且均等于边数，即 $\sum_{v \in V} d^-(v) = \sum_{v \in V} d^+(v) = |E|$。

证明：点击查看证明

证明：设有向图 $(V,E)$ 中有 $m$ 条边 $e_1, e_2, \ldots, e_m$。每条边 $e_i$ 连接两个顶点，记作 $e_i = (u_i, v_i)$，其中 $u_i$ 是起点，$v_i$ 是终点。则每条边对入度和出度的贡献均为 1（因为每条边有一个起点和一个终点）

因此，所有顶点的入度之和为：$\sum_{v \in V} d^-(v)= \sum_{i=1}^{m} 1 = m = |E|$。同理，所有顶点的出度之和也为：$\sum_{v \in V} d^+(v)= \sum_{i=1}^{m} 1 = m = |E|$

定理 5.2.3

奇度定理：在无向图中，度为奇数的顶点数目为偶数。

证明：点击查看证明

证明：设无向图 $(V,E)$ 中有 $n$ 个顶点 $v_1, v_2, \ldots, v_n$。将顶点集 $V$ 分为两部分：度为奇数的顶点集 $O$ 和度为偶数的顶点集 $E$。设 $|O| = k$，则度为奇数的顶点数目为 $k$ $\sum_{v \in V} d(v) = \sum_{v \in O} d(v) + \sum_{v \in E} d(v)$ 为偶数 $\sum_{v \in E} d(v)$ 为偶数，所以 $\sum_{v \in O} d(v)$ 也为偶数。由于度为奇数的顶点数目为 $k$，每个顶点的度为奇数，因此 $\sum_{v \in O} d(v)$ 为奇数的和。奇数个奇数之和为奇数，偶数个奇数之和为偶数。因此，$k$ 必须为偶数

定理 5.2.4

完全图的度数：完全图 $K_n$ 中每个顶点的度数为 $n-1$，即 $d(v) = n-1$，其中 $v \in V(K_n)$

定理 5.2.5

完全有向图的度数：完全有向图 $DK_n$ 中每个顶点的入度和出度均为 $n-1$，即 $d^-(v) = d^+(v) = n-1$，其中 $v \in V(DK_n)$

定理 5.2.6

竞赛图的度数1：在竞赛图中，每个顶点的入度和出度之和均为 $n-1$，即 $d^-(v) + d^+(v) = n-1$，其中 $v \in V$
竞赛图的度数2：在竞赛图中，存在一个顶点，其出度至少为 $\frac{n-1}{2}$，即存在 $v \in V$，使得 $d^+(v) \ge \frac{n-1}{2}$

证明：点击查看证明

证明：设竞赛图 $(V,E)$ 中有 $n$ 个顶点 $v_1, v_2, \ldots, v_n$。根据竞赛图的定义，每个顶点的入度和出度之和均为 $n-1$，即 $d^-(v_i) + d^+(v_i) = n-1$，其中 $i = 1, 2, \ldots, n$

因此，所有顶点的出度之和为：$\sum_{i=1}^{n} d^+(v_i) = \sum_{i=1}^{n} (n-1 - d^-(v_i)) = n(n-1) - \sum_{i=1}^{n} d^-(v_i)$。根据有向图的度数定理，$\sum_{i=1}^{n} d^-(v_i) = |E|$，因此 $\sum_{i=1}^{n} d^+(v_i) = n(n-1) - |E|$。

由于每条边都有一个起点和一个终点，因此 $|E| = \frac{n(n-1)}{2}$。将其代入上式，得到 $\sum_{i=1}^{n} d^+(v_i) = n(n-1) - \frac{n(n-1)}{2} = \frac{n(n-1)}{2}$

根据平均值原理，至少存在一个顶点 $v_j$，使得 $d^+(v_j) \ge \frac{\sum_{i=1}^{n} d^+(v_i)}{n} = \frac{\frac{n(n-1)}{2}}{n} = \frac{n-1}{2}$

竞赛图的度数3：在竞赛图中，存在一个顶点，其入度至少为 $\frac{n-1}{2}$，即存在 $v \in V$，使得 $d^-(v) \ge \frac{n-1}{2}$

证明：点击查看证明

证明：与出度证明类似

竞赛图的度数4：所有的顶点入度的平方和与出度的平方和相等，即 $\sum_{v \in V} (d^-(v))^2 = \sum_{v \in V} (d^+(v))^2$

证明：点击查看证明

因此，$d^+(v_i) = n-1 - d^-(v_i)$。将其代入出度的平方和，得到：

$\sum_{i=1}^{n} (d^+(v_i))^2 = \sum_{i=1}^{n} (n-1 - d^-(v_i))^2 = \sum_{i=1}^{n} ((n-1)^2 - 2(n-1)d^-(v_i) + (d^-(v_i))^2)$

$= n(n-1)^2 - 2(n-1)\sum_{i=1}^{n} d^-(v_i) + \sum_{i=1}^{n} (d^-(v_i))^2$

根据有向图的度数定理，$\sum_{i=1}^{n} d^-(v_i) = |E|$。由于竞赛图中有 $\frac{n(n-1)}{2}$ 条边，因此 $\sum_{i=1}^{n} d^-(v_i) = \frac{n(n-1)}{2}$

将其代入上式，得到：$\sum_{i=1}^{n} (d^+(v_i))^2 = n(n-1)^2 - 2(n-1)\frac{n(n-1)}{2} + \sum_{i=1}^{n} (d^-(v_i))^2 = \sum_{i=1}^{n} (d^-(v_i))^2$

竞赛图的度数5：在竞赛图中，任意两个不同顶点 $u,v$ 的入度之差等于它们出度之差的相反数，即 $d^-(u) - d^-(v) = -(d^+(u) - d^+(v))$

证明：点击查看证明

因此，$d^+(v_i) = n-1 - d^-(v_i)$。对于任意两个不同顶点 $u,v \in V$，有：

$d^-(u) - d^-(v) = (n-1 - d^+(u)) - (n-1 - d^+(v)) = - (d^+(u) - d^+(v))$

定理 5.2.7

$\delta(G)<= \frac{2|E|}{|V|} <= \Delta(G)$

证明：点击查看证明

证明：

设图 $G=(V,E)$ 中有 $n$ 个顶点和 $m$ 条边。根据握手定理，所有顶点的度数之和为 $2m$，即 $\sum_{v \in V} d(v) = 2m$

因此，顶点的平均度数为 $\frac{\sum_{v \in V} d(v)}{n} = \frac{2m}{n}$

由于最小度数 $\delta(G)$ 不大于平均度数，最大度数 $\Delta(G)$ 不小于平均度数，因此有 $\delta(G) \le \frac{2m}{n} \le \Delta(G)$

定义 5.3 可图化可简单图化

设 $d_1, d_2, \ldots, d_n$ 是非负整数序列。如果存在一个图，其顶点的度数依次为 $d_1, d_2, \ldots, d_n$，则称该序列是可图化的（graphical）

如果存在一个简单图，其顶点的度数依次为 $d_1, d_2, \ldots, d_n$，则称该序列是可简单图化的（simply graphical）。

定理 5.3.1

一个图是可图化的充分必要条件是其度数序列的和为偶数

证明：点击查看证明

证明：必要性：设图 $(V,E)$ 中有 $m$ 条边 $e_1, e_2, \ldots, e_m$。根据握手定理，所有顶点的度数之和等于边数的两倍，即 $\sum_{v \in V} d(v) = 2|E|$。由于 $2|E|$ 是偶数，因此所有顶点的度数之和也必须为偶数

充分性：

$d=(d_1,d_2,...d_n)$ 中有偶数个奇数，记为 $2k(0\le k\le [\frac{n}{2}])$ ，奇数分别为 $d_{i_1},d_{i_2},...,d_{i_{2k}}$

采用下面的方法构造一个图 $G$

顶点集 $V=\{v_1,v_2,...,v_n\}$，首先在顶点 $v_{i_r}$ 和 $v_{i_{k+r}}$ 之间加入一条边，$r=1,2,...,k$

若 $d_i$ 为偶数，令 $d_i'=d_i$；若 $d_i$ 为奇数，令 $d_i'=d_i-1$。则 $d'=(d_1',d_2',...,d_n')$ 中全为偶数

再在 $v_i$ 上加入 $\frac{d_i'}{2}$ 条自环，则得到一个图 $G$，其顶点的度数依次为 $d_1,d_2,...,d_n$，所以是可图化的

定理 5.3.2

一个简单图是可简单图化的充分必要条件是其度数序列满足埃尔德什-加拉伊定理

埃尔德什-加拉伊定理：点击查看内容

设 $d_1, d_2, \ldots, d_n$ 是非负整数序列，且 $d_1 \ge d_2 \ge \ldots \ge d_n$。则该序列是可简单图化的充分必要条件是：

1. $\sum_{i=1}^{n} d_i$ 为偶数;
1. 对每个 $k$，$1 \le k \le n$，都有 $\sum_{i=1}^{k} d_i \le k(k-1) + \sum_{i=k+1}^{n} min(d_i, k)$

证明：

定理 5.3.3

哈基米定理

$d=(d_1,d_2,...d_n)$ 是一个有限多个非负整数组成的非递减序列，$d$ 可简单图化当且仅当有穷序列 $d'=(d_2-1,d_3-1,...,d_{d_1+1}-1,d_{d_1+2},...,d_n)$ 只含有非负整数且是可简单图化的

证明：点击查看证明

证明：

必要性：设简单图 $G$ 的顶点集为 $V = \{v_1, v_2, \ldots, v_n\}$，其中 $d(v_i) = d_i$。选择度数最大的顶点 $v_1$，将其与其他 $d_1$ 个顶点连接边。这样，连接后的顶点的度数分别减少 1，得到新的度数序列 $d'=(d_2-1,d_3-1,...,d_{d_1+1}-1,d_{d_1+2},...,d_n)$。由于连接边不会引入自环或多重边，因此新的图仍然是简单图，因此 $d'$ 是可简单图化的

充分性：设 $d'=(d_2-1,d_3-1,...,d_{d_1+1}-1,d_{d_1+2},...,d_n)$ 是可简单图化的。根据假设，存在一个简单图 $G'$，其顶点的度数依次为 $d_2-1, d_3-1, \ldots, d_{d_1+1}-1, d_{d_1+2}, \ldots, d_n$

通过添加一个新的顶点 $v_1$，并将其与其他 $d_1$ 个顶点连接边，来构造一个新的简单图 $G$

新的图 $G$ 的顶点的度数依次为 $d_1, d_2, \ldots, d_n$，因此 $d$ 是可简单图化的

定义 5 4 图的同构

设 $G_1=(V_1,E_1)$ 和 $G_2=(V_2,E_2)$ 是两个图。如果存在一个双射 $f: V_1 \to V_2$，使得对于任意 $u,v \in V_1$，$\{u,v\} \in E_1$ 当且仅当 $\{f(u),f(v)\} \in E_2$，则称图 $G_1$ 与图 $G_2$ 同构（isomorphic），记作 $G_1 \cong G_2$。函数 $f$ 称为同构映射（isomorphism）

定理 5.4.1

图 $G_1$ 和 $G_2$ 同构当且仅当对某一顶点的顺序，它们的邻接矩阵相同

证明：点击查看证明

证明：

若这两个图同构，则存在一个双射 $f: V_1 \to V_2$，使得对于任意 $u,v \in V_1$，$\{u,v\} \in E_1$ 当且仅当 $\{f(u),f(v)\} \in E_2$。这意味着在邻接矩阵中，如果顶点 $u$ 和 $v$ 之间有边，则在对应的邻接矩阵中，位置 $(u,v)$ 和 $(v,u)$ 的值为 1，否则为 0

对应的，有 $(f(u), f(v))$ 和 $(f(v), f(u))$ 位置的值也为 1 或 0

因此，通过重新排列顶点的顺序，可以使得两个图的邻接矩阵相同

定义 5.5 子图、补图

设 $G=(V,E)$ 是一个图。如果 $G'$ 是由 $G$ 的部分顶点和部分边构成的图，即 $G'=(V',E')$，其中 $V' \subseteq V$ 且 $E' \subseteq E$，则称 $G'$ 为图 $G$ 的子图（subgraph），记作 $G' \subseteq G$

设 $G=(V,E)$ 是一个图。图 $G$ 的补图（complement graph）记作 $\overline{G}=(V,\overline{E})$，其中 $\overline{E} = \{\{u,v\} | u,v \in V, u \ne v, \{u,v\} \notin E\}$。即补图 $\overline{G}$ 包含了图 $G$ 中没有的所有边

若一个图和它的补图同构，则称该图为自补图（self-complementary graph）

自补图的性质：

自补图的顶点数 $n$ 满足 $n \equiv 0 \text{ 或 } 1 \mod 4$

定义 5.6 路径、回路、简单路径、简单回路

设 $G=(V,E)$ 是一个图，$G$ 的一个有限点边交替序列 $P = v_0 e_1 v_1 e_2 v_2 \ldots e_k v_k$，其中 $v_i \in V$，$e_i \in E$，且 $e_i = \{v_{i-1}, v_i\}$，称为图 $G$ 中从顶点 $v_0$ 到顶点 $v_k$ 的一条路径（path），记作 $P: v_0 \to v_k$

路径的长度为边的数目 $k$。如果 $v_0 = v_k$，则称该路径为回路（circuit）或闭路径（closed path）

边 $e_1, e_2, \ldots, e_k$ 称为路径 $P$ 上的边，顶点 $v_0, v_1, \ldots, v_k$ 称为路径 $P$ 上的顶点

若边互不相同，则称这个路径为链（简单路径），若顶点互不相同，则称这个路径为路

类似的，可以定义有向路径，有向路，有向链，有向闭路径，有向回路，有向闭链等

定理 5.6.1

路径与度数的关系1：若图 $G$ 中每个顶点的度数至少为 2，则图 $G$ 中存在一条回路

证明：点击查看证明

证明：

设图 $G=(V,E)$ 中每个顶点的度数至少为 2

若 $G$ 包含自环或者多重边，结论显然成立

若 $G$ 是简单图，任取顶点 $v_0$ 构造一个顶点序列，从其相邻点中任取一个顶点 $v_1$，再从 $v_1$ 的相邻点中任取一个未出现过的顶点 $v_2$，依此类推（每个点的度数至少为 2 保证了这个过程可以继续），直到某一步无法继续为止

设此时的顶点序列为 $v_0, v_1, \ldots, v_k$

由于图 $G$ 是有限图，必然存在 $i$ 和 $j$，使得 $0 \le i < j \le k$，且 $v_i = v_j$。因此，顶点序列 $v_i, v_{i+1}, \ldots, v_j$ 构成了一条回路

定理 5.6.2

$G$ 是简单图，若 $\delta(G) ≥ k$，则 $G$ 中有长度为 $k$ 的路

证明：点击查看证明

证明：设 $G$ 的一条极大路为 $P=v_0v_1...v_m$，则 $P$ 的长度为 $m-1$

设路的一个端点 $u$，由于 $P$ 是极大的，说明 $u$ 的所有邻接点都在路 $P$ 上，否则 $P$ 可继续扩展，与 $P$ 的极大性矛盾

因此，$u$ 的度数 $d(u) \le m-1$，又由于 $\delta(G) \ge k$，所以有 $m-1 \ge k$

则 $m≥ k+1$，即路 $P$ 的长度至少为 $k$

故图 $G$ 中有长度为 $k$ 的路

定义 5.7 连通图、强连通图、连通分支

若两个不同的顶点 $u,v$ 之间存在一条路径，则称顶点 $u$ 和顶点 $v$ 是连通的（connected）

设 $G=(V,E)$ 是一个无向图。如果对于任意两个不同的顶点 $u,v \in V$，都存在一条从 $u$ 到 $v$ 的路，则称图 $G$ 为连通图（connected graph）

设 $G=(V,E)$ 是一个无向图。$G$ 的极大连通子图称为图 $G$ 的连通分支（connected component）

即：每个顶点的导出子图 $G_i$ 都是 $G$ 的一个连通分支，且 $G_i$ 与 $G_j$（$i \ne j$）没有公共顶点

$G$ 有 $k$ 个连通分支，则称图 $G$ 为 $k$-连通图，当 $k=1$ 时，称图 $G$ 为连通图

设 $G=(V,E)$ 是一个有向图。如果对于任意两个不同的顶点 $u,v \in V$，都存在一条从 $u$ 到 $v$ 的有向路，则称图 $G$ 为强连通图（strongly connected graph）

定理 5.7.1

路径与度数的关系2：若图 $G$ 中恰有两个顶点的度数为奇数，则图 $G$ 中存在一条从一个奇度顶点到另一个奇度顶点的路径

证明：点击查看证明

证明：

如果 $G$ 是连通图，则从一个奇度顶点出发，沿着边不断前进，必然会到达另一个奇度顶点，从而构成一条路径

如果 $G$ 不是连通图，有连通分支 $G_1, G_2, \ldots, G_k$，则奇度顶点必然存在至少 2 个位于同一个连通分支中，这是因为：

每个连通分支中的顶点度数之和为偶数，因此每个连通分支中奇度顶点的数目为偶数

定理 5.7.2

设图 $G$ 是有 $n$ 个顶点的简单图，若 $G$ 有 $e$ 条边， $\omega$ 个分支，则有 $n-\omega \le e \le \frac{(n - \omega)(n - \omega + 1)}{2}$

证明：点击查看证明

证明：

先证明左边

设图 $G$ 的连通分支为 $G_1, G_2, \ldots, G_\omega$，每个连通分支 $G_i$ 有 $n_i$ 个顶点和 $e_i$ 条边，则有 $\sum_{i=1}^{\omega} n_i = n$ 且 $\sum_{i=1}^{\omega} e_i = e$。由于每个连通分支至少有 $n_i - 1$ 条边，因此有：$e = \sum_{i=1}^{\omega} e_i \ge \sum_{i=1}^{\omega} (n_i - 1) = n - \omega$

再证明右边

去掉某一个连通分支有 $n-n_i \ge \omega-1$ 即 $n_i \le n-\omega+1$，且 $n_i-1 \le n-\omega$

由于每个连通分支最多有 $\frac{n_i(n_i - 1)}{2}$ 条边，因此有：$e = {i=1}^{} e_i {i=1}^{} (n-+1)_{i=1}^{}(n_i-1)= $

因此，有：$e \le \frac{(n - \omega)(n - \omega + 1)}{2}$

定理 5.7.3

$G$ 是简单图，有 $n$ 个顶点，$\delta>[\frac{n}{2}]-1$，则 $G$ 是连通图

证明：点击查看证明

证明：

设图 $G=(V,E)$ 中有 $n$ 个顶点，且每个顶点的度数至少为 $[\frac{n}{2}]-1$

假设图 $G$ 不是连通图，设 $G$ 有 $k$ 个连通分支，它们的顶点数分别为 $n_1, n_2, \ldots, n_k$，则有 $\sum_{i=1}^{k} n_i = n$ 且 $k \ge 2$

每个连通分支的顶点度最多为 $n_i - 1$，因此有：

$[\frac{n}{2}]-1 < n_i - 1$，即 $n_i > [\frac{n}{2}]$

累加有：$n=\sum_{i=1}^{k} n_i > k[\frac{n}{2}]$

当 $n$ 为偶数时，$[\frac{n}{2}] = \frac{n}{2}$，则有 $n > k \cdot \frac{n}{2}$，即 $k < 2$，与 $k \ge 2$ 矛盾！

当 $n$ 为奇数时，$[\frac{n}{2}] = \frac{n-1}{2}$，则有 $n > k \cdot \frac{n-1}{2}$，即 $k < \frac{2n}{n-1}$。由于 $\frac{2n}{n-1} < 3$，因此 $k < 3$，则 $k=2$

当 $k=2$ 且 $n$ 为奇数时，不妨设顶点数分别为 $n_1$ 和 $n_2$，则有 $n_1 + n_2 = n$

不妨设 $n_1 \le n_2$，则有 $n_1 \le \frac{n}{2}$

又 $n_1 > \frac{n-1}{2}$

$n$ 为奇数可知，$n_1$ 不可能为整数，矛盾！

因此，图 $G$ 必须是连通图

定理 5.7.4

图 $G$ 是有 $n$ 个顶点的简单图，若对于任意两个不相邻的顶点 $u,v$，都有 $d(u)+d(v) \ge n-1$，则 $G$ 是连通图

证明：点击查看证明

证明：

假设图 $G$ 不是连通图，设 $G$ 有 $k$ 个连通分支，它们的顶点数分别为 $n_1, n_2, \ldots, n_k$，则有 $\sum_{i=1}^{k} n_i = n$ 且 $k \ge 2$

选择两个不同连通分支 $G_i$ 和 $G_j$，分别取其中的顶点 $u \in V(G_i)$ 和 $v \in V(G_j)$，则 $u$ 和 $v$ 不相邻

因此，有 $d(u) + d(v) \ge n - 1$。然而，由于 $u$ 和 $v$ 分别属于不同的连通分支，它们的度数之和最多为 $(n_i - 1) + (n_j - 1) = n_i + n_j - 2$，其中 $n_i$ 和 $n_j$ 分别是连通分支 $G_i$ 和 $G_j$ 的顶点数

因此，有 $n_i + n_j - 2 \ge n - 1$，即 $n_i + n_j \ge n + 1$。然而，由于 $\sum_{i=1}^{k} n_i = n$，这意味着其他连通分支的顶点数之和为 $n - (n_i + n_j) \le -1$，矛盾

因此，图 $G$ 必须是连通图

定理 5.7.5

设 $G$ 是有 $n$ 个顶点的简单图，若对于任意两个不相邻的顶点 $u,v$，都有 $d(u)+d(v) \ge n$，则 $G$ 是强连通图

证明：点击查看证明

证明：

假设图 $G$ 不是强连通图，设 $G$ 有 $k$ 个强连通分支，它们的顶点数分别为 $n_1, n_2, \ldots, n_k$，则有 $\sum_{i=1}^{k} n_i = n$ 且 $k \ge 2$

选择两个不同强连通分支 $G_i$ 和 $G_j$，分别取其中的顶点 $u \in V(G_i)$ 和 $v \in V(G_j)$，则 $u$ 和 $v$ 不相邻

因此，有 $d(u) + d(v) \ge n$。然而，由于 $u$ 和 $v$ 分别属于不同的强连通分支，它们的度数之和最多为 $(n_i - 1) + (n_j - 1) = n_i + n_j - 2$，其中 $n_i$ 和 $n_j$ 分别是强连通分支 $G_i$ 和 $G_j$ 的顶点数

因此，有 $n_i + n_j - 2 \ge n$，即 $n_i + n_j \ge n + 2$。然而，由于 $\sum_{i=1}^{k} n_i = n$，这意味着其他强连通分支的顶点数之和为 $n - (n_i + n_j) \le -2$，矛盾

因此，图 $G$ 必须是强连通图

定理 5.7.6

设 $G$ 是简单连通图，每一个顶点都是偶顶点，则 $\omega(G-v)=\frac{1}{2}d(v)$

证明：点击查看证明

证明：

去除 $v$ 后的图 $G'$ 中有 $k=\omega(G-v)$ 个连通分支 $G_i$，每个连通分支 $G_i$ 中顶点的度数之和为偶数，因此每个连通分支中奇点的数目为偶数

每个与 $v$ 相连的顶点都是奇点，设 $d_i$ 为 $v$ 与某个连通分支 $G_i$ 相连的边数，则该连通分支中奇点的数目为 $d_i$，因此 $d_i$ 必须为偶数

又 $G$ 是连通的，所以 $d_i>0$

因此，$d(v)=\sum_{i=1}^{k} d_i\ge 2k$，其中每个 $d_i$ 都是正偶数，所以有 $k \le \frac{d(v)}{2}$

即 $\omega(G-v) \le \frac{1}{2}d(v)$

定义 5.8 邻接矩阵、路径矩阵

设图 $G=(V,E)$，其中 $V = \{v_1, v_2, \ldots, v_n\}$。图 $G$ 的邻接矩阵（adjacency matrix）$M = [a_{ij}]$ 是一个 $n \times n$ 的矩阵，其中：

\[ m_{ij} = \begin{cases} 1, & \text{如果 } \{v_i, v_j\} \in E \\ 0, & \text{否则} \end{cases} \]

图 $G$ 的路径矩阵（path matrix）$P = [p_{ij}]$ 是一个 $n \times n$ 的矩阵，其中：

\[ p_{ij} = \begin{cases} 1, & \text{如果存在从 } v_i \text{ 到 } v_j \text{ 的路径} \\ 0, & \text{否则} \end{cases} \]

$P(G)$ 是一个布尔矩阵，$G$ 是连通图当且仅当 $P(G)$ 中所有元素均为 1

无向图的邻接矩阵是对称矩阵

定理 5.8.1

设图 $G$ 的邻接矩阵为 $M$，则图 $G$ 的路径矩阵 $P$ 可由下式计算得到：$ P = M + M^2 + M^3 + + M^{n-1} $

证明：点击查看证明

证明：

设图 $G=(V,E)$ 中有 $n$ 个顶点 $v_1, v_2, \ldots, v_n$，其邻接矩阵为 $M = [m_{ij}]$。根据邻接矩阵的定义，$m_{ij} = 1$ 当且仅当存在一条从顶点 $v_i$ 到顶点 $v_j$ 的边

$M^k$ 的元素 $m_{ij}^{(k)}$ 表示从顶点 $v_i$ 到顶点 $v_j$ 的长度为 $k$ 的路径的数量

图 $G$ 中存在一条从顶点 $v_i$ 到顶点 $v_j$ 的路径，当且仅当存在某个 $k$，使得 $1 \le k \le n-1$，且 $m_{ij}^{(k)} > 0$

图 $G$ 的路径矩阵 $P = [p_{ij}]$ 可以表示为：

\[ p_{ij} = \begin{cases} 1, & \text{如果存在某个 } k \text{，使得 } 1 \le k \le n-1 \text{ 且 } a_{ij}^{(k)} > 0 \\ 0, & \text{否则} \end{cases} \]

所以，路径矩阵 $P$ 可以通过邻接矩阵的幂次和来计算得到：\[ P = M + M^2 + M^3 + \ldots + M^{n-1} \]

此外，可以改为并逻辑运算来表示路径矩阵：\[ P = M \lor M^2 \lor M^3 \lor \ldots \lor M^{n-1} \]

定理 5.8.2

设图 $G$ 的邻接矩阵为 $M$，则图 $G$ 的路径矩阵 $P$ 可由下式计算得到：$ P = (I + M)^{n-1} $

证明：点击查看证明

证明：

$I$ 是 $n \times n$ 的单位矩阵，其对角线元素为 1，其他元素为 0

$(I + M)$ 的元素表示从顶点 $v_i$ 到顶点 $v_j$ 的路径的数量，包括长度为 0 的路径（即从顶点到自身的路径）

$(I + M)^{k}$ 的元素表示从顶点 $v_i$ 到顶点 $v_j$ 的长度不超过 $k$ 的路径的数量

图 $G$ 中存在一条从顶点 $v_i$ 到顶点 $v_j$ 的路径，当且仅当存在某个 $k$，使得 $1 \le k \le n-1$，且 $(I + M)^{k}_{ij} > 0$

图 $G$ 的路径矩阵 $P = [p_{ij}]$ 可以表示为：

\[ p_{ij} = \begin{cases} 1, & \text{如果存在某个 } k \text{，使得 } 1 \le k \le n-1 \text{ 且 } (I + M)^{k}_{ij} > 0 \\ 0, & \text{否则} \end{cases} \]

所以，路径矩阵 $P$ 可以通过邻接矩阵的幂次和来计算得到：\[ P = (I + M)^{n-1} \]

定义 5.9 割边、边割、键、割点、顶点割

图 $G$ 的割边（桥）是指使得 $\omega(G - e) > \omega(G)$ 的边 $e \in E$，即去掉该边后图的连通分支数增加

对 $V$ 的子集 $S$，若边 $e = \{u,v\}$ 满足 $u \in S$ 且 $v \notin S$，则称边 $e$ 跨越割 $(S, \overline{S})$，其中 $\overline{S} = V - S$

图 $G$ 的边割（割集）是指使得 $\omega(G - E(S, \overline{S})) > \omega(G)$ 的边集 $E(S, \overline{S})$，即去掉该边集后图的连通分支数增加

$G$ 的极小边割（任何真子集都不是边割的边割）称为键

若 $E$ 可以分为两个非空子集 $E_1$ 和 $E_2$ ，使得 $G[E_1]$ 和 $G[E_2]$ 只剩公共顶点 $v$，则称顶点 $v$ 为图 $G$ 的割点

若 $V$ 的子集 $V'$ 使得 $G-V'$ 不连通，则称 $V'$ 为图 $G$ 的顶点割

$k$ 顶点割是指包含 $k$ 个顶点的顶点割

定理 5.9.1

$e$ 是 $G$ 的割边当且仅当 $e$ 不属于 $G$ 的任何回路

证明：点击查看证明

证明：

必要性：设 $e = \{u,v\}$ 是图 $G$ 的割边，假设 $e$ 属于图 $G$ 的某个回路 $C$

去掉边 $e$ 后，回路 $C$ 仍然存在，因为回路中还有其他边连接顶点 $u$ 和 $v$

因此，去掉边 $e$ 后图的连通分支数不会增加，与 $e$ 是割边的定义矛盾

充分性：设 $e = \{u,v\}$ 不属于图 $G$ 的任何回路。去掉边 $e$ 后，顶点 $u$ 和 $v$ 之间不再有直接连接

由于 $e$ 不属于任何回路，说明在去掉边 $e$ 后，顶点 $u$ 和 $v$ 之间没有其他路径连接

因此，去掉边 $e$ 后图的连通分支数增加，即 $\omega(G - e) > \omega(G)$，所以 $e$ 是割边

定义 5.10 连通度、边连通度

$G$ 中的最小顶点割的大小称为图 $G$ 的连通度（connectivity），记作 $\kappa(G)$

若 $\kappa(G)=k$ 则称图 $G$ 为 $k$-连通图

$G$ 中的最小边割的大小称为图 $G$ 的边连通度（edge connectivity），记作 $\lambda(G)$

若 $\lambda(G)=k$ 则称图 $G$ 为 $k$-边连通图

定理 5.10.1

对任意图 $G$，都有 $\kappa(G) \le \lambda(G) \le \delta(G)$

证明：点击查看证明

证明：

首先证明 $\lambda(G) \le \delta(G)$：

设图 $G=(V,E)$ 中有一个顶点 $v$，其度数为 $\delta(G)$

去掉与顶点 $v$ 相连的所有边后，顶点 $v$ 将与图的其他部分断开连接，从而增加了图的连通分支数

因此，去掉的边数至少为 $\delta(G)$，即 $\lambda(G) \le \delta(G)$

接下来证明 $\kappa(G) \le \lambda(G)$：

对 $\lambda(G)$ 采用数学归纳法

当 $\lambda(G) = 0$ 时，图 $G$ 已经是不连通的，因此 $\kappa(G) = 0$，结论成立

假设当 $\lambda(G) < k$ 时，结论成立，即 $\kappa(G) < k$，当 $\lambda(G) = k$ 时，设图 $G$ 的一个最小边割为 $E' = \{e_1, e_2, \ldots, e_k\}$

任取一个边 $e$，考虑 $H=G-e$

则 $\lambda(H)\le k-1$，即 $\kappa(H)\le k-1$

若 $H$ 包含完全图作为其生成子图，则 $G$ 也包含完全图作为其生成子图，因此 $\kappa(G)\le \kappa(H)\le k-1$

否则设 $S$ 是 $H$ 的一个具有 $\kappa(H)$ 个元素的顶点割

由于 $H-S$ 是不连通的，且 $e$ 是它的割边

要么 $G-S$ 是不连通的，此时有 $\kappa(G)\le |S|=\kappa(H)\le k-1$；

要么 $G-S$ 是连通的，且 $e$ 是它的割边

此时要么 $v(G-S)=2$，此时有 $\kappa(G)\le v(G)-1 \le \kappa(H)+1 \le k$

要么$G-S$ 有 $1$ 顶点割 $\{v\}$，从而 $S \cup \{v\}$ 是 $G$ 的一个顶点割，且有 $\kappa(G)\le |S|+1=\kappa(H)+1 \le k$

根据数学归纳法，对任意图 $G$，都有 $\kappa(G) \le \lambda(G)$

定义 5.11 块、独立集、覆盖、团

没有割点的连通图称为块（block）

设$G=(V,E)$ 是一个图，$V$ 的一个子集 $S \subseteq V$ ，如果对于任意两个不同的顶点 $u,v \in S$，都有 $\{u,v\} \notin E$，则称 $S$ 为图 $G$ 的独立集（independent set）

设 $G=(V,E)$ 是一个图，$V$ 的一个子集 $S \subseteq V$ ，如果对于任意一条边 $e = \{u,v\} \in E$，都有 $u \in S$ 或 $v \in S$，则称 $S$ 为图 $G$ 的覆盖（cover）

简单图 $G$ 的一个团是指 $V$ 的一个子集 $S$，使得 $G[S]$ 是完全图

设 $G=(V,E)$ 是一个图，$V$ 的一个子集 $S \subseteq V$ ，如果对于任意两个不同的顶点 $u,v \in S$，都有 $\{u,v\} \in E$，则称 $S$ 为图 $G$ 的团（clique）

更详细的相关定理和证明参考第十节

(´-ω-｀)

集合与图论学习笔记05

定义

定义 5.1 边集、点集、有向图、无向图、多重图、简单图、带权图、竞赛图

定理 5.1.1

定义 5.2 度、入度、出度

定理 5.2.1

定理 5.2.2

定理 5.2.3

定理 5.2.4

定理 5.2.5

定理 5.2.6

定理 5.2.7

定义 5.3 可图化 可简单图化

定理 5.3.1

定理 5.3.2

定理 5.3.3

定义 5 4 图的同构

定理 5.4.1

定义 5.5 子图、补图

定义 5.6 路径、回路、简单路径、简单回路

定理 5.6.1

定理 5.6.2

定义 5.7 连通图、强连通图、连通分支

定理 5.7.1

定理 5.7.2

定理 5.7.3

定理 5.7.4

定理 5.7.5

定理 5.7.6

定义 5.8 邻接矩阵、路径矩阵

定理 5.8.1

定理 5.8.2

定义 5.9 割边、边割、键、割点、顶点割

定理 5.9.1

定义 5.10 连通度、边连通度

定理 5.10.1

定义 5.11 块、独立集、覆盖、团

定义 5.3 可图化可简单图化