图论

参考资料

• 图论 - 维基百科
• 七桥问题 - 维基百科

引入

图 是描述「对象之间联系」的数学结构。社交网络、路网、电路、依赖关系都是图。图论的奠基性问题是欧拉解决的 柯尼斯堡七桥问题（1736）。

基本概念

定义

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

• 无向图：边是无序对 $\set{u,v}$。
• 有向图：边是有序对 $(u,v)$。
• 多重图：允许平行边和自环。
• 简单图：不允许平行边和自环。

度数

无向图：顶点 $v$ 的 度 $d(v)$ 是关联边的条数（自环算 $2$）。

有向图：入度 $d^-(v)$ 与 出度 $d^+(v)$。

握手定理

$$\sum_{v\in V}d(v)=2|E|$$

推论：奇度顶点的个数必为偶数。

子图与补图

• 子图：$V'\subseteq V$，$E'\subseteq E$。
• 生成子图：$V'=V$。
• 导出子图：$E'$ 是 $V'$ 间所有边。
• 补图 $\bar G$：与 $G$ 顶点相同，边集互补。

特殊图

名称	记号	描述
完全图	$K_n$	$n$ 顶点两两相连
完全二部图	$K_{m,n}$	两部分各 $m,n$ 顶点，每个跨部分连边
圈	$C_n$	$n$ 顶点环状相连
路径	$P_n$	$n$ 顶点链状相连
轮图	$W_n$	圈 $C_n$ 加一个与所有顶点相连的中心

路径与连通

概念

• 通路：顶点和边交替的序列，端点不必不同。
• 简单通路：边不重复。
• 路径：顶点不重复。
• 回路 / 圈：起点终点相同。

连通性

无向图：任意两顶点之间存在路径 $\Rightarrow$ 连通图；否则分为多个 连通分支。

有向图：

• 任意两顶点 互可达 $\Rightarrow$ 强连通。
• 忽略方向后连通 $\Rightarrow$ 弱连通。

树

树 = 连通且无圈 的图。

等价定义

设 $|V|=n$，下列条件相互等价：

1. $T$ 是树。
2. $T$ 连通且 $|E|=n-1$。
3. $T$ 无圈且 $|E|=n-1$。
4. $T$ 任意两顶点有且仅有一条路径相连。
5. $T$ 添加任一条边后恰好形成一个圈。
6. $T$ 删除任一条边后不再连通。

生成树

连通图 $G$ 的 生成子图 且是树。任何连通图都存在生成树。

经典算法：

• Kruskal：按边权递增加边，不形成圈则保留。
• Prim：从一个顶点出发，每次加入连接「树内 / 树外」的最小边。

欧拉图与哈密顿图

概念	定义	存在条件
欧拉通路	经过 每条边恰一次 的通路	连通图恰有 $0$ 或 $2$ 个奇度顶点
欧拉回路	经过 每条边恰一次 的回路	连通图所有顶点度均为偶数
哈密顿通路	经过 每个顶点恰一次 的通路	NP-完全问题，无简单充要条件
哈密顿回路	经过 每个顶点恰一次 的回路	同上

tip

欧拉看边、哈密顿看点——一字之差，难度天壤。 判断欧拉只需数度；判断哈密顿在一般图上没有高效算法。

哈密顿图的充分条件（Ore 定理）

简单图 $G$ 有 $n\ge 3$ 个顶点，若对任意不相邻顶点 $u,v$ 都有 $d(u)+d(v)\ge n$，则 $G$ 是哈密顿图。

图的着色

顶点着色

用 $k$ 种颜色给顶点染色，相邻顶点颜色不同。所需最少颜色数称为 色数 $\chi(G)$。

• 二部图：$\chi=2$。
• $K_n$：$\chi=n$。
• 圈：$\chi=2$（偶圈）或 $3$（奇圈）。

四色定理

任何 平面图 的色数 $\le 4$（1976 年首次借助计算机证明）。

图的矩阵表示

邻接矩阵

$A=(a_{ij})$，$a_{ij}=$ 顶点 $v_i,v_j$ 之间的边数。

• 无向图：$A$ 对称。
• $A^k$ 的 $(i,j)$ 项 = 从 $v_i$ 到 $v_j$ 长度为 $k$ 的通路数。

关联矩阵

$M=(m_{ij})$，$m_{ij}=1$ 当顶点 $v_i$ 与边 $e_j$ 关联。无向图列和恒为 $2$。