Appearance
图论基础与染色
引言
图论是组合数学的一个重要分支，用点和边的语言来描述离散结构之间的关系。在数学竞赛中，图论方法可以将许多看似无关联的题目统一到同一框架下，尤其是染色问题和 Ramsey 理论，深刻而优雅。
一、图的基本概念
图的定义
一个图 $G = (V, E)$由顶点集$V$和边集$E \subseteq \lbrace \lbrace u, v\rbrace \mid u, v \in V, u \neq v\rbrace $ 组成。若边有方向，则称为有向图；否则为无向图。本文主要讨论简单无向图。
1.1 度与握手定理
顶点度 (Degree)
顶点 $v$的度$\deg(v)$是与$v$ 相连的边的条数。
握手定理 (Handshaking Lemma)
$$\sum_{v \in V} \deg(v) = 2|E|$$ 即图中所有顶点的度数之和等于边数的两倍。
直观理解
每条边连接两个顶点，在计算度数和时恰好被数了两次，就像一次握手涉及两个人。
重要推论
任意图中，奇度顶点的个数必为偶数。
证明：设 $V_o$ 为奇度顶点集，$V_e$ 为偶度顶点集。$\sum_{v \in V_o} \deg(v) + \sum_{v \in V_e} \deg(v) = 2|E|$为偶数。右式中$\sum_{v \in V_e} \deg(v)$为偶数（偶数和），故$\sum_{v \in V_o} \deg(v)$ 必为偶数。而奇度个数之和为偶数，说明奇度顶点个数为偶数。$\square$
1.2 路径与回路
基本术语
- 路径 (Path)：顶点序列 $v_1, v_2, \ldots, v_k$，相邻顶点间有边，且顶点不重复。
- 回路 / 圈 (Cycle)：起点与终点相同的路径，且中间顶点不重复。
- 简单路径：经过的边不重复的路径。（不含重边）
- 连通图：任意两个顶点之间都存在路径。
二、图的连通性
连通分量 (Connected Component)
图的极大连通子图称为连通分量。一个非连通图可分解为若干个连通分量。
割点与桥
- 割点 (Cut Vertex)：去掉该点（及其关联边）后图的连通分量数增加。
- 桥 (Bridge / Cut Edge)：去掉该边后图的连通分量数增加。
Menger 定理（简介）
图中两个不相邻顶点 $u$和$v$之间顶点不交的路径的最大数目，等于分离$u$和$v$ 所需删除的最少顶点数。这是图连通性的核心定理（竞赛中不要求证明，但可利用其思想）。
三、二部图（偶图）
二部图 (Bipartite Graph)
若图 $G$的顶点集$V$可以划分为两个不相交的子集$X$和$Y$，使得每条边都连接 $X$中的一个顶点和$Y$中的一个顶点，则称$G$ 为二部图（偶图）。
二部图的判定定理
一个图是二部图 当且仅当 它不含奇圈（长度为奇数的回路）。
判定方法
实际判定二部图常用「二染色法」：任取一顶点染红色，其所有邻居染蓝色，邻居的邻居染红色……若过程中不出现冲突（即两端同色的边），则为二部图；若出现冲突，则不是。
例1：二部图判定
判断完全图 $K_4$和$K_{3,3}$ 是否为二部图。
- 解析
$K_4$含有三角形（长度为$3$ 的奇圈），故不是二部图。 $K_{3,3}$中所有圈长度均为偶数（事实上$K_{3,3}$ 由定义就是二部图），故是二部图。
:::
四、欧拉图与哈密顿图
4.1 欧拉图
欧拉回路与欧拉图
经过图中每条边恰好一次的回路称为欧拉回路。存在欧拉回路的图称为欧拉图。
欧拉定理
一个连通图存在欧拉回路 当且仅当 每个顶点的度数均为偶数。
一个连通图存在欧拉路径（经过每条边恰好一次但不必回到起点）当且仅当 恰有两个奇度顶点（此时路径以这两个顶点为起点和终点）。
证明要点
必要条件：每次进入一个顶点必有一条边离开（非起点/终点），所以中间顶点的度数必为偶数。 充分条件：用归纳法或 Fleury 算法构造。
4.2 哈密顿图
哈密顿回路
经过图中每个顶点恰好一次的回路称为哈密顿回路。存在哈密顿回路的图称为哈密顿图。
充分条件（竞赛常用）
- Dirac 定理（1952）：若 $n \geq 3$的简单图$G$中每个顶点的度数均$\geq n/2$，则 $G$ 是哈密顿图。
- Ore 定理（1960）：若 $n \geq 3$的简单图$G$中任意两个不相邻顶点$u, v$满足$\deg(u) + \deg(v) \geq n$，则 $G$ 是哈密顿图。
注意
以上均为充分非必要条件。判定哈密顿性一般是 NP 完全的，竞赛中通常只需应用这些充分条件。
例2：哈密顿图的判定
证明：$n \geq 3$个顶点的完全图$K_n$ 是哈密顿图。
- 解析
$K_n$中每个顶点度数为$n-1 \geq n/2$（$n \geq 3$），由 Dirac 定理直接得证。实际上，$K_n$中任意一个包含所有$n$ 个顶点的环排列都是一个哈密顿回路。
:::
五、树 (Tree)
树的等价定义
以下关于连通图 $T$ 的命题等价：
- $T$ 是无圈连通图（树的定义）。
- $T$连通且$|E| = |V| - 1$。
- $T$无圈且$|E| = |V| - 1$。
- $T$ 中任意两个顶点之间存在唯一一条简单路径。
重要性质
- $n$个顶点的树恰有$n-1$ 条边。
- 任何树至少有两个叶子（度数为 $1$ 的顶点）。
证明（至少两片叶子）：设树有 $n$ 个顶点，$n-1$条边。由握手定理$\sum \deg(v) = 2(n-1)$。若树中叶子数 $< 2$，即至多 $1$个度数为$1$的顶点，其余顶点度数$\geq 2$，则度数和 $\geq 1 + 2(n-1) = 2n-1 > 2(n-1)$，与握手定理矛盾。$\square$
例3：树的叶子数
已知一棵树有 $3$个度数为$4$ 的顶点，$2$个度数为$3$的顶点，其余顶点度数均为$1$。求树有多少片叶子。
- 解析
设叶子数为 $x$，顶点总数 $n = 3 + 2 + x = x + 5$。边数为 $n-1 = x+4$。 由握手定理：$3 \times 4 + 2 \times 3 + x \times 1 = 2(x+4)$ $12 + 6 + x = 2x + 8$，即 $18 + x = 2x + 8$，解得 $x = 10$。
:::
六、染色问题
6.1 顶点染色
色数 (Chromatic Number)
图 $G$的色数$\chi(G)$ 是使相邻顶点染不同颜色所需的最少颜色数。
基本结论
- $\chi(G) = 1 \iff G$ 无边。
- $\chi(G) = 2 \iff G$ 是二部图（且有边）。
- $\chi(K_n) = n$（完全图每个顶点都需要不同颜色）。
- Brooks 定理：若 $G$既不是完全图也不是奇圈，则$\chi(G) \leq \Delta(G)$（最大度）。
6.2 边染色
边色数 (Edge Chromatic Number)
图 $G$的边色数$\chi'(G)$ 是使相邻边（共顶点的边）染不同颜色所需的最少颜色数。
Vizing 定理
对任意简单图 $G$：$\Delta(G) \leq \chi'(G) \leq \Delta(G) + 1$。二部图的边色数等于最大度 $\Delta(G)$（Kőnig 定理）。
6.3 四色定理
四色定理
任何平面图可以用至多 $4$ 种颜色进行正常顶点染色。这是图论中最著名的定理，由 Appel 和 Haken 于 1976 年借助计算机证明。
七、拉姆齐理论 (Ramsey Theory)
Ramsey 数 $R(s,t)$
$R(s,t)$是最小的正整数$n$，使得任意 $n$个顶点的完全图$K_n$的边任意染成红蓝两色，要么存在一个全红的$K_s$，要么存在一个全蓝的 $K_t$。
已知 Ramsey 数
- $R(3,3) = 6$
- $R(3,4) = 9$
- $R(3,5) = 14$
- $R(4,4) = 18$
- $R(3,6) = 18$
- $R(3,7) = 23$
例4：经典 Ramsey 问题
证明：在任意 $6$个人中，必有$3$个人两两认识，或者$3$个人两两不认识。即证$R(3,3) \leq 6$。
- 证明（标准 Ramsey 论证）
用 $6$个顶点表示$6$ 个人，两人认识则连红边，不认识则连蓝边。问题转化为：$K_6$ 的边任染红蓝两色，必存在同色三角形。
任选一个顶点 $v$。$v$有$5$条边连向其余$5$个顶点，由鸽巢原理，至少有$\lceil 5/2 \rceil = 3$条边同色（红或蓝）。不妨设$v$与$a, b, c$ 之间为红边。
若 $a, b, c$之间有任何一条红边（比如$ab$），则 $v, a, b$构成红色三角形。若$a, b, c$之间全是蓝边，则$a, b, c$ 构成蓝色三角形。无论哪种情况，都存在同色三角形。$\square$
:::
另证：$R(3,3) = 6$ 的等式证明
还需要证明 $5$个顶点不一定有同色三角形。构造$K_5$如下：将$5$个顶点排成正五边形，外圈边染红色（形成一个$5$-圈），内弦染蓝色（也形成一个 $5$-圈）。不存在同色三角形（因为 $5$-圈的色数为 $3$，不含三角形）。故 $R(3,3) > 5$，综合得 $R(3,3) = 6$。
例5：Ramsey 型极值问题
证明：任意 $9$个人中，必有$3$个人两两认识，或者$4$个人两两不认识。即证$R(3,4) \leq 9$。
- 证明要点
用图论语言：$K_9$的边染红蓝两色，必有红色$K_3$或蓝色$K_4$。
选取顶点 $v$。若 $v$有至少$4$条蓝边连接到$A = \lbrace a_1, a_2, a_3, a_4\rbrace $，则考察 $A$的导出子图。若其中存在蓝边，则该蓝边与$v$构成蓝色$K_3$ 不成立（等等，目标需调整）......
准确证明：选取 $v$，设其红邻居集为 $R$，蓝邻居集为 $B$。如果 $|B| \geq 6$，则在 $B$中，由$R(3,3)=6$，$B$中必有红色$K_3$（目标达成）或蓝色 $K_3$，若为蓝色 $K_3$则加上$v$构成蓝色$K_4$（目标达成）。
如果 $|B| \leq 5$，则 $|R| \geq 3$。若 $R$中任意两点间为蓝边，则加上$v$构成蓝色$K_3$；但 $R$中有红边则得红色$K_3$。根本在于：当 $|B| \geq 4$时用$R(3,3)$ 归纳......
标准证明：设 $v$的蓝邻居数$\geq 4$，则若蓝邻居中有两两蓝色，则此两蓝色邻点与 $v$构成蓝色$K_3$（？不对，我们要的是蓝色 $K_4$）。让我们重新组织：
在 $K_9$中，顶点$v$有$8$条边。若$v$至少$4$条红边通向$R$，$R$中若有红边则得红$K_3$（完成），若 $R$全蓝则$R$为蓝$K_4$（完成）。若 $v$至少$6$条蓝边通向$B$，由 $R(3,3)=6$，$B$中要么有红$K_3$（完成），要么有蓝 $K_3$，连同 $v$得蓝$K_4$（完成）。$8$ 条边中必有一类数量达到上述阈值。$\square$
:::
八、用图论解决竞赛组合问题
图论模型化的思路
很多竞赛中的组合题目看似与图论无关，但巧妙地建立图模型后就能套用图论定理。核心技巧：
- 点和边的抽象：将研究对象视为顶点，关系视为边。
- 染色建模：将分类/归属问题转化为染色问题。
- 匹配与覆盖：将配对/选择问题转化为图的匹配问题。
例6：图论建模
某班有 $n$个学生，每个学生恰认识班上$k$个其他同学。证明：若$k \geq n/2$，则可以安排所有学生围坐一圈，使得相邻两人都互相认识。
- 解析
以学生为顶点，互相认识的两人之间连边，得到图 $G$。每个顶点度数均为 $k \geq n/2$。由 Dirac 定理，$G$ 中存在哈密顿回路，即可以安排所有学生围坐一圈且相邻两人互相认识。
:::
例7：二部图的应用
在一个舞会上，有 $m$个男生和$n$个女生。已知每个男生至少认识$k$个女生，每个女生最多认识$k$ 个男生。证明：所有男生都可以同时找到一个互相认识的女生做舞伴。
- 解析（Hall 婚姻定理）
构造二部图，男生在左，女生在右，认识则连边。条件为：每个男生度数 $\geq k$，每个女生度数 $\leq k$。 取任意 $r$个男生组成集合$X$，$|X| = r$。$X$中男生发出的总边数$\geq rk$。这些边全部落在 $N(X)$（$X$的邻居集）中的女生上，每个女生最多接收$k$条边，故$|N(X)| \cdot k \geq rk$，即 $|N(X)| \geq r = |X|$。 由 Hall 婚姻定理，存在完美匹配。$\square$
:::
Hall 婚姻定理（导引）
二部图 $G = (X, Y, E)$存在覆盖$X$的匹配当且仅当对任意$S \subseteq X$，$|N(S)| \ge |S|$。这是匹配理论的基石，详见 高级图论与网络流，那里还讨论了 König 定理、Menger 定理、Tutte 1-因子定理与最大流最小割定理。