图论基础

1. 图的基本概念

1.1 图的定义

图 $G=(V,E)$ 由顶点集 $V$ 和边集 $E$ 组成。

• 无向图：$E$ 中元素为无序对 $\{u,v\}$
• 有向图：$E$ 中元素为有序对 $(u,v)$
• 多重图：允许平行边（同一对顶点间有多条边）
• 简单图：无平行边、无自环

1.2 特殊图

• 完全图 $K_n$：$n$ 个顶点，每对顶点间有一条边，$|E|=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$
• 零图：无边图
• 平凡图：只有一个顶点的图
• 正则图：每个顶点的度都相同的图。$k$-正则图：每个顶点度为 $k$

1.3 子图

• 子图：$H=(V^{\prime },E^{\prime })$，$V^{\prime }\subseteq V$，$E^{\prime }\subseteq E$
• 生成子图：$V^{\prime }=V$ 的子图
• 导出子图：由顶点子集 $V^{\prime }$ 导出，包含 $V^{\prime }$ 之间所有边

2. 度与握手定理

2.1 度

顶点 $v$ 的度 $\mathrm{deg}(v)$ 是与 $v$ 关联的边数（自环算2度）。

• 孤立点：$\mathrm{deg}(v)=0$
• 悬挂点：$\mathrm{deg}(v)=1$

2.2 握手定理

定理：在任何无向图中，所有顶点的度数之和等于边数的两倍：

${\sum }_{v\in V}\mathrm{deg}(v)=2|E|$

证明：每条边贡献2个度（连接两个端点）。

推论：任何图中度数为奇数的顶点个数必为偶数。

有向图版本：

${\sum }_{v\in V}{\mathrm{deg}}^{+}(v)={\sum }_{v\in V}{\mathrm{deg}}^{-}(v)=|E|$

其中 ${\mathrm{deg}}^{+}(v)$ 为出度，${\mathrm{deg}}^{-}(v)$ 为入度。

例：一个图有5个顶点，度数分别为3, 3, 4, 4, 4，求边数。

$\sum \mathrm{deg}=3+3+4+4+4=18=2|E|$，$|E|=9$。

3. 路径与回路

3.1 基本概念

• 通路（walk）：顶点与边交替的序列 $v_0{e}_1{v}_1{e}_2\cdots e_k{v}_k$
• 迹（trail）：边不重复的通路
• 路径（path）：顶点不重复的通路（除起终点外）
• 回路（circuit）：起终点相同的迹
• 圈（cycle）：起终点相同且其余顶点不重复的通路，长度 $\ge 3$

3.2 路径长度

• 无权图中路径长度为边数
• 带权图中路径长度为边权之和

4. 连通性

4.1 无向图的连通性

• 连通：顶点 $u$ 和 $v$ 之间存在路径
• 连通图：任意两个顶点都连通
• 连通分量：极大连通子图

4.2 有向图的连通性

• 强连通：任意两个顶点互相可达
• 弱连通：忽略方向后连通
• 单向连通：任意两个顶点至少一个方向可达

4.3 连通度

• 点连通度 $\kappa (G)$：使 $G$ 不连通需删除的最少顶点数
• 边连通度 $\lambda (G)$：使 $G$ 不连通需删除的最少边数

Whitney 不等式：$\kappa (G)\le \lambda (G)\le \delta (G)$

其中 $\delta (G)$ 为最小度。

4.4 割点与桥

• 割点：删除该顶点后连通分量数增加
• 桥：删除该边后连通分量数增加

5. 欧拉图与哈密顿图

5.1 欧拉图

欧拉回路：经过每条边恰好一次的回路。

欧拉通路：经过每条边恰好一次的通路。

判定定理：

• 无向连通图有欧拉回路 $⟺$ 每个顶点的度数为偶数
• 无向连通图有欧拉通路 $⟺$ 恰有0个或2个奇度顶点
  • 0个奇度顶点：欧拉回路
  • 2个奇度顶点：欧拉通路从一个奇度顶点到另一个

Fleury 算法（求欧拉回路）：

1. 从任意顶点出发
2. 每步选择一条未走过的边，除非该边是当前顶点唯一的桥
3. 直到所有边走完

例：判断 $K_5$ 是否有欧拉回路。

$K_5$ 中每个顶点度为4（偶数），连通，故有欧拉回路。

5.2 哈密顿图

哈密顿回路：经过每个顶点恰好一次的回路。

哈密顿路径：经过每个顶点恰好一次的路径。

判定：哈密顿图的判定是 NP 完全问题，没有简单的充要条件。

充分条件：

Dirac 定理：若 $G$ 是 $n$ 阶简单图（$n\ge 3$）且 $\delta (G)\ge n/2$，则 $G$ 是哈密顿图。

Ore 定理：若 $G$ 是 $n$ 阶简单图（$n\ge 3$）且对任意不相邻顶点 $u,v$ 有 $\mathrm{deg}(u)+\mathrm{deg}(v)\ge n$，则 $G$ 是哈密顿图。

必要条件：若 $G$ 是哈密顿图，则对 $V$ 的任意非空真子集 $S$，$G-S$ 的连通分量数 $c(G-S)\le |S|$。

例：判断 Petersen 图是否为哈密顿图。

Petersen 图有10个顶点，每个顶点度为3。取 $S$ 为中间5个顶点，$c(G-S)=5>|S|=5$… 不，实际上 $c(G-S)=5=|S|$，不违反必要条件。但 Petersen 图确实不是哈密顿图（需更细致的分析）。

6. 二部图

6.1 定义

若 $V$ 可划分为 $V_1$ 和 $V_2$（$V_1\cap V_2=\varnothing$），使得每条边连接 $V_1$ 和 $V_2$ 中的顶点，则 $G$ 为二部图（偶图），记作 $G=(V_1,V_2,E)$。

完全二部图 $K_{m,n}$：$|V_1|=m$，$|V_2|=n$，$V_1$ 中每个顶点与 $V_2$ 中每个顶点相连。

6.2 判定

定理：无向图是二部图 $⟺$ 图中无奇圈。

证明： $\Rightarrow$：若 $G$ 是二部图且有奇圈，则圈上顶点交替属于 $V_1,V_2$，奇圈导致首尾顶点同属一个集合，矛盾。 $\Leftarrow$：对每个连通分量，从任一顶点出发 BFS，交替分配到 $V_1,V_2$。无奇圈保证不矛盾。

6.3 匹配

匹配：边集 $M\subseteq E$，$M$ 中任意两条边不共享端点。

最大匹配：边数最多的匹配。

完美匹配：覆盖所有顶点的匹配。

Hall 婚姻定理：二部图 $G=(V_1,V_2,E)$ 中存在 $V_1$ 到 $V_2$ 的完美匹配 $⟺$ 对任意 $S\subseteq V_1$，$|N(S)|\ge |S|$。

其中 $N(S)$ 为 $S$ 的邻域。

7. 树与生成树

7.1 树的定义

树是连通无圈图。

等价定义（对 $n$ 阶图 $G$）：

1. $G$ 连通且无圈
2. $G$ 连通且 $|E|=n-1$
3. $G$ 无圈且 $|E|=n-1$
4. $G$ 中任意两个顶点间有唯一路径
5. $G$ 连通且删除任一边后不连通

7.2 树的性质

• 树中至少有两个叶子（度为1的顶点）（$n\ge 2$ 时）
• 树中任意两个顶点间有唯一路径
• 树添加任一边产生唯一圈
• 树删除任一边产生两个连通分量

7.3 生成树

生成树：连通图 $G$ 的生成子图且为树。

存在性：连通图必有生成树。

生成树个数：$n$ 个顶点的完全图 $K_n$ 的生成树个数为 $n^{n-2}$（Cayley 公式）。

7.4 最小生成树

Kruskal 算法：

1. 将边按权从小到大排序
2. 依次取边，若不形成圈则加入
3. 直到 $n-1$ 条边

Prim 算法：

1. 从任一顶点开始
2. 每步选择连接已选顶点集与未选顶点集的最小权边
3. 直到所有顶点入选

两者时间复杂度分别为 $O(|E|\log |E|)$ 和 $O(|E|\log |V|)$。