图论基础

9 minIntermediate2026/6/14

图的基本概念、度与握手定理、路径与回路、连通性、欧拉图与哈密顿图、二部图、树与生成树。

1. 图的基本概念

1.1 图的定义

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

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

1.2 特殊图

  • 完全图 KnK_n：nn 个顶点，每对顶点间有一条边，∣E∣=(n2)|E| = \binom{n}{2}
  • 零图：无边图
  • 平凡图：只有一个顶点的图
  • 正则图：每个顶点的度都相同的图。kk-正则图：每个顶点度为 kk

1.3 子图

  • 子图：H=(V′,E′)H = (V', E')，V′⊆VV' \subseteq V，E′⊆EE' \subseteq E
  • 生成子图：V′=VV' = V 的子图
  • 导出子图：由顶点子集 V′V' 导出，包含 V′V' 之间所有边

2. 度与握手定理

2.1 度

顶点 vv 的度 deg⁡(v)\deg(v) 是与 vv 关联的边数（自环算2度）。

  • 孤立点：deg⁡(v)=0\deg(v) = 0
  • 悬挂点：deg⁡(v)=1\deg(v) = 1

2.2 握手定理

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

∑v∈Vdeg⁡(v)=2∣E∣\sum_{v \in V} \deg(v) = 2|E|

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

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

有向图版本：

∑v∈Vdeg⁡+(v)=∑v∈Vdeg⁡−(v)=∣E∣\sum_{v \in V} \deg^+(v) = \sum_{v \in V} \deg^-(v) = |E|

其中 deg⁡+(v)\deg^+(v) 为出度，deg⁡−(v)\deg^-(v) 为入度。

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

∑deg⁡=3+3+4+4+4=18=2∣E∣\sum \deg = 3+3+4+4+4 = 18 = 2|E|，∣E∣=9|E| = 9。

3. 路径与回路

3.1 基本概念

  • 通路（walk）：顶点与边交替的序列 v0e1v1e2⋯ekvkv_0 e_1 v_1 e_2 \cdots e_k v_k
  • 迹（trail）：边不重复的通路
  • 路径（path）：顶点不重复的通路（除起终点外）
  • 回路（circuit）：起终点相同的迹
  • 圈（cycle）：起终点相同且其余顶点不重复的通路，长度 ≥3\geq 3

3.2 路径长度

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

4. 连通性

4.1 无向图的连通性

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

4.2 有向图的连通性

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

4.3 连通度

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

Whitney 不等式：κ(G)≤λ(G)≤δ(G)\kappa(G) \leq \lambda(G) \leq \delta(G)

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

4.4 割点与桥

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

5. 欧拉图与哈密顿图

5.1 欧拉图

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

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

判定定理：

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

Fleury 算法（求欧拉回路）：

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

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

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

5.2 哈密顿图

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

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

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

充分条件：

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

Ore 定理：若 GG 是 nn 阶简单图（n≥3n \geq 3）且对任意不相邻顶点 u,vu, v 有 deg⁡(u)+deg⁡(v)≥n\deg(u) + \deg(v) \geq n，则 GG 是哈密顿图。

必要条件：若 GG 是哈密顿图，则对 VV 的任意非空真子集 SS，G−SG - S 的连通分量数 c(G−S)≤∣S∣c(G-S) \leq |S|。

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

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

6. 二部图

6.1 定义

若 VV 可划分为 V1V_1 和 V2V_2（V1∩V2=∅V_1 \cap V_2 = \emptyset），使得每条边连接 V1V_1 和 V2V_2 中的顶点，则 GG 为二部图（偶图），记作 G=(V1,V2,E)G = (V_1, V_2, E)。

完全二部图 Km,nK_{m,n}：∣V1∣=m|V_1| = m，∣V2∣=n|V_2| = n，V1V_1 中每个顶点与 V2V_2 中每个顶点相连。

6.2 判定

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

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

6.3 匹配

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

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

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

Hall 婚姻定理：二部图 G=(V1,V2,E)G = (V_1, V_2, E) 中存在 V1V_1 到 V2V_2 的完美匹配   ⟺  \iff 对任意 S⊆V1S \subseteq V_1，∣N(S)∣≥∣S∣|N(S)| \geq |S|。

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

7. 树与生成树

7.1 树的定义

树是连通无圈图。

等价定义（对 nn 阶图 GG）：

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

7.2 树的性质

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

7.3 生成树

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

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

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

7.4 最小生成树

Kruskal 算法：

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

Prim 算法：

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

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