Lec 10-11: 图论 (Graph Theory)¶
1. 基本概念¶
1.1 图的定义¶
图 \(G = (V,E)\)，其中： - \(V\) 是顶点集合 (vertex set)，非空 - \(E\) 是边集合 (edge set)，\(E \subseteq V \times V\)
1.2 图的分类¶
| 类型 | 说明 |
|---|---|
| 无向图 (undirected graph) | 边没有方向 |
| 有向图 (directed graph) | 边有方向 |
| 简单图 (simple graph) | 无自环、无重边 |
| 多重图 (multigraph) | 允许重边 |
| 完全图 (complete graph) | 任意两个顶点间都有边，\(K_n\) |
1.3 顶点的度¶
- 度 (degree)：与该顶点相连的边的数目，记作 \(\deg(v)\)
- 握手定理 (Handshaking Lemma)： $\(\sum_{v \in V} \deg(v) = 2|E|\)$
- 无向图中，奇度顶点的个数为偶数
2. 图的同构 (Graph Isomorphism)¶
两个图 \(G = (V,E)\) 和 \(G' = (V',E')\) 同构，当存在双射 \(f: V \to V'\)，使得 \((u,v) \in E\) 当且仅当 \((f(u), f(v)) \in E'\)。
3. 欧拉图 (Eulerian Graph)¶
3.1 定义¶
- 欧拉通路：经过图中每条边恰好一次的路径
- 欧拉回路：经过图中每条边恰好一次的回路
- 欧拉图：具有欧拉回路的图
3.2 判定定理¶
| 图类型 | 欧拉通路存在条件 | 欧拉回路存在条件 |
|---|---|---|
| 无向图 | 恰有 0 或 2 个奇度顶点 | 所有顶点度数为偶数 |
| 有向图 | 除起点和终点外，所有顶点入度=出度 | 所有顶点入度=出度 |
4. 哈密尔顿图 (Hamiltonian Graph)¶
4.1 定义¶
- 哈密尔顿通路：经过图中每个顶点恰好一次的路径
- 哈密尔顿回路：经过图中每个顶点恰好一次的回路
- 哈密尔顿图：具有哈密尔顿回路的图
4.2 必要条件¶
- \(G\) 是哈密尔顿图 \(\to\) \(G\) 去掉任意 \(k\) 个顶点后，连通分支数 \(\leq k\)
4.3 充分条件¶
Dirac 定理：若 \(n \geq 3\) 且每个顶点的度数 \(\geq n/2\)，则 \(G\) 是哈密尔顿图
5. 二分图 (Bipartite Graph) 与匹配¶
5.1 二分图¶
- 顶点集可划分为 \(V_1\) 和 \(V_2\)，每条边连接 \(V_1\) 和 \(V_2\) 中的顶点
- 判定：图 \(G\) 是二分图 \(\leftrightarrow\) \(G\) 中不含奇环
5.2 匹配算法¶
- 匹配 (matching)：边集 \(M \subseteq E\)，其中任意两条边没有公共端点
- 最大匹配：边数最多的匹配
- 完美匹配：覆盖所有顶点的匹配
- 匈牙利算法：求解二分图最大匹配的经典算法
6. 平面图 (Planar Graph)¶
- 欧拉公式：\(V - E + F = 2\)（连通平面图）
- \(V\): 顶点数，\(E\): 边数，\(F\): 面数