离散数学 学习笔记
离散数学学习笔记 Author: Sunglassman
图论
Hamilton 图
设 $G(V, E)$ 为图，若 $G$ 中有一条经过所有顶点一次仅一次的回路，称这个回路为 Hamilton 回路，称 $G$ 为 Hamilton 图。
半 Hamilton 图：有一条经过所有顶点一次仅一次的路，称该路为半 Hamilton 路，称 $G$ 为半 Hamilton 图。
这是一个典型的 NP-完全问题。
Th： 设 $G(V,E)$ 为 Hamilton 图， 对 $V$ 的每个非空真子集 $S$ ，均有 $\omega(G-S)\le |S|$，其中 $\omega(G-S)$ 表示 $G-S$ 的连通分支数。
证明：
因为 $G$ 为 Hamilton 图， 它有一个 Hamilton 回路 $C$.
所以 $C$ 为 $G$ 的生成子图.
所以 $C-S$ 为 $G-S$ 的生成子图.
$\omega(G-S)\le \omega(C-S) \le |S|$.
注意： Hamilton回路不存在任意一个子回路。
Petersen 图：
Petersen 图 不是 Hamilton 图。
Th： 设 $G(V,E)$ 为 $n$ 个顶点的简单图，对于每一对不相邻的顶点 $u,v$， 满足 $d(u)+d(v)\ge n$，则 $G$ 一定是 Hamilton 图。 $<=> G+(u,v)$ 为 Hamilton 图.
**证明：**反设有一个 $n$ 个顶点的简单图 $G(V,E)$ 满足条件但不是 Hamilton 图。
对 $G$ 中的两个不相邻的顶点 $u,v$ ，若 $G+(u,v)$ 不是 Hamilton 图，则把 $(u,v)$ 连起来，否则不连接。
不断地这样下去，直到不能连任意两个不相邻的顶点。
则 $G$ 就成为了满足条件的极大的非 Hamilton 图。
由于完全图一定是 Hamilton 图，则 $G$ 肯定不是完全图 $K_n$。
设 $u,v$ 是 $G$ 上两个不相邻的顶点，由 $G$ 的构造知，$G+(u,v)$ 为 Hamilton 图。
断言：$u$ 一定有一个邻点 $v_i$ 使 $v_{i-1}$ 是 $v$ 的一个邻点。
若该结论不成立，则设 $d(u)=k$，则 $d(v)\le (n-1)-k$，这时 $d(u)+d(v)\le n-1<n$ 与 $d(u)+d(v)\ge n$ 矛盾。
由断言得，$G$ 是一个 Hamilton 图，矛盾！
Th： 设 $G(V,E)$ 为 $n$ 个顶点的简单图，若对任意两个不相邻的顶点 $u,v$ 均有 $d(u)+d(v)\ge n-1$ ，则 $G$ 为半 Hamilton 图。
证明： 构造 $G’=G+u$ 满足 $u$ 与 $G$ 上每一个顶点都连起来，则对任意两个点 $x,y$ ，有 $d(x)+d(y)\ge n+1$. 由于 $G’$ 是一个有 $n+1$ 个顶点的图，则由上述定理，$G’$ 是 Hamilton 图。
将 $u$ 去掉则 $G$ 是一个半 Hamilton 图。
Hamilton 闭包：
竞赛图：
**定义： ** 任意两个顶点间均有一条有向边。（任意两个选手进行一场比赛，根据胜负连边）
如果不考虑方向就是完全图。
Th: 任何竞赛图都是一个半 Hamilton 有向图
证明：
设 $G(V,E)$ 是竞赛图，当 $|v| \le 3$ 时：
当 $|v|=2$ 时，显然。
当 $|v|=3$ 时，显然有一个点，它的入度和出度均为 $1$。以这个点为中间点可以构造一个半 Hamilton 路。
设 $|V|=k$ 时结论成立，即 $k$ 个顶点的竞赛图为半 Hamiltion 有向图。
当 $|V|=k+1$ 时，$\forall u\in V$ ，因为 $G-u$ 为 $k$ 个顶点的竞赛图，由归纳假设知， $G-u$ 是半 Hamilton 图。
Th: 任何强连通的竞赛图一定是 Hamilton 有向图。
证明: 设 $G(V, E)$ 为强连通的竞赛图， $|V| = n$, 则 $n \ge 3$。
（如果 $n=1, 2$，强连通 $G$ 没有回路。$n=3$ 时，强连通的竞赛图必为 3-回路。）
我们使用数学归纳法证明 $G$ 一定包含长度为 $3, 4, 5, \dots, n$ 的回路（即 $G$ 是泛圈的）。
1. 基础情况 ($k=3$): 证明 $G$ 一定包含长度为 $3$ 的回路。
任取 $u \in V$，令 $V_1 = {v \in V \mid (u, v) \in E}$ (u的出邻域), $V_2 = {v \in V \mid (v, u) \in E}$ (u的入邻域)。
由于 $G$ 是竞赛图, $V_1 \cup V_2 = V - {u}$。
由于 $G$ 是强连通的, $u$ 必须有出边和入边，所以 $V_1 \neq \emptyset$ 且 $V_2 \neq \emptyset$。
因为 $G$ 强连通，一定存在从 $V_1$ 到 $V_2$ 的边（否则 $V_1$ 无法到达 $V_2$）。
设 $v_1 \in V_1, v_2 \in V_2$ 使得 $(v_1, v_2) \in E$。
此时，我们有 $u \to v_1 \to v_2 \to u$，这是一个长度为 3 的回路。
2. 归纳步骤:
假设 $G$ 有一条长度为 $k$ 的回路 $C_k$（其中 $3 \le k < n$），下面证明 $G$ 有一条长度为 $k+1$ 的回路。
设 $C_k = v_1 \to v_2 \to \dots \to v_k \to v_1$，其顶点集为 $V_k = {v_1, v_2, \dots, v_k}$。
因为 $k < n$，所以存在 $u \in V - V_k$。
我们分两种情况讨论：
(1) 若 $\exists u \in V - V_k$，使得 $u$ 同时存在来自 $V_k$ 的入边和指向 $V_k$ 的出边。
即 $\exists v_i, v_j \in V_k$，使得 $(v_i, u) \in E$ 且 $(u, v_j) \in E$。
因为 $G$ 是竞赛图， $u$ 和 $C_k$ 上的所有 $k$ 个顶点都有边。
如果 $u$ 没有 $v_i \to u$ 和 $u \to v_{i+1}$ 这样的相邻对，那么 $C_k$ 上的所有顶点 $v$ 要么满足 $v \to u$，要么满足 $u \to v$。
因为 $u$ 既有入边又有出边，所以沿着 $C_k$ 走，一定存在一个 $i$，使得 $v_i \to u$ 且 $u \to v_{i+1}$ (下标对 $k$ 取模)。
此时，我们可以构造长度为 $k+1$ 的回路：
$v_1 \to \dots \to v_i \to u \to v_{i+1} \to \dots \to v_k \to v_1$。
(2) 假设 (1) 的条件不成立。
这意味着对于任何 $u \in V - V_k$， $u$ 不
同时具有来自 $V_k$ 的入边和指向 $V_k$ 的出边。
由于 $G$ 是竞赛图，这说明 $\forall u \in V - V_k$，
- 要么 $u$ 指向 $V_k$ 中所有顶点 (即 $\forall v_i \in V_k, u \to v_i$)，
- 要么 $V_k$ 中所有顶点指向 $u$ (即 $\forall v_i \in V_k, v_i \to u$)。
我们定义两个集合：
- $A = { u \in V - V_k \mid \forall v_i \in V_k, u \to v_i }$
- $B = { u \in V - V_k \mid \forall v_i \in V_k, v_i \to u }$
根据我们的假设, $V - V_k = A \cup B$。
因为 $G$ 是强连通的：
- $A \neq \emptyset$。（否则 $V-V_k = B$，所有边从 $V_k$ 指向 $B$，$B$ 无法返回 $V_k$，与强连通矛盾。）
- $B \neq \emptyset$。（否则 $V-V_k = A$，所有边从 $A$ 指向 $V_k$，$V_k$ 无法到达 $A$，与强连通矛盾。）
再次因为 $G$ 是强连通的，一定存在一条从 $B$ 指向 $A$ 的边。
设 $b \in B$ 且 $a \in A$，使得 $b \to a$。
现在我们来构造 $k+1$ 的回路。
首先，我们可以利用 $a$ 和 $b$ 构造一个长度为 $k+2$ 的回路 $C_{k+2}$：
- $a \to v_1$ (根据 $a \in A$ 的定义)
- $v_1 \to v_2 \to \dots \to v_k$ (来自 $C_k$ 的路径)
- $v_k \to b$ (根据 $b \in B$ 的定义)
- $b \to a$ (我们找到的边)
连接起来，得到 $C_{k+2} = a \to v_1 \to v_2 \to \dots \to v_k \to b \to a$。
接下来，我们证明这个 $C_{k+2}$ 一定包含一个 $k+1$ 的回路。
考虑 $C_{k+2}$ 上的顶点 $a$ 和 $v_2$。
根据 $a \in A$ 的定义， $a$ 指向 $C_k$ 中的所有顶点，所以 $a \to v_2$ 这条边必定存在。
因此，我们可以利用 $a \to v_2$ 这条“捷径” (chord) 来“跳过” $v_1$，构造出一条更短的回路：
$C_{k+1} = a \to v_2 \to v_3 \to \dots \to v_k \to b \to a$。
这个新回路的顶点集为 ${a, v_2, v_3, \dots, v_k, b}$，共 $1 + (k-1) + 1 = k+1$ 个顶点。
我们就找到了一个长度为 $k+1$ 的回路。
结论
综上所述，无论情况 (1) 还是 (2) 成立，我们总能从 $k$-回路构造出 $k+1$-回路。
根据数学归纳法， $G$ 包含所有长度为 $3, 4, \dots, n$ 的回路。特别地，$G$ 包含长度为 $n$ 的回路，即哈密顿回路 (Hamiltonian cycle)。
最短路算法
todoooo
平面图
$K_5$ 不是平面图，$K_{3,3}$ 不是平面图