Skip to main content

图论

参考资料​

引入​

图（Graph）是描述「对象之间联系」的数学结构。社交网络（人与好友）、路网（路口与道路）、电路、程序的函数调用、任务依赖——凡是「一堆东西加上它们之间的连接」，都是图。

图论的奠基性问题是欧拉解决的 柯尼斯堡七桥问题（1736）：能否一次走遍七座桥且每座只走一次？欧拉把陆地抽象成点、桥抽象成边，发现答案只取决于「奇数度的点有几个」，从此开创了图论。这正是图论的思维方式——把具体问题抽掉无关细节，只留下点和边的连接结构。

基本概念​

定义​

图 G=(V,E)G=(V,E) 由 顶点集（Vertex Set）VV 和 边集（Edge Set）EE 组成。∣V∣|V| 称图的 阶。

  • 无向图：边是无序对 { u,v }\set{u,v}，连接没有方向。
  • 有向图：边是有序对 (u,v)(u,v)，从 uu 指向 vv。
  • 多重图：允许 平行边（两点间多条边）和 自环（连到自己的边）。
  • 简单图：既无平行边也无自环——最常打交道的图。
  • 加权图：每条边带一个权值（距离、费用、容量等）。

度数​

无向图里，顶点 vv 的 度（Degree）d(v)d(v) 是与它关联的边数，自环算 22（两端都连到 vv）。

有向图区分 入度 d−(v)d^-(v)（指进来的边数）与 出度 d+(v)d^+(v)（指出去的边数），d(v)=d−(v)+d+(v)d(v)=d^-(v)+d^+(v)。

度为 00 的顶点叫 孤立点，度为 11 的叫 悬挂点。

握手定理​

每条边恰好贡献 22 个「度」（两个端点各 11），于是：

∑v∈Vd(v)=2∣E∣\sum_{v\in V}d(v)=2|E|

这就是 握手定理（Handshaking Lemma）——名字来自「一群人握手，所有人握手次数之和必为偶数（每次握手算两人各一次）」。

推论：奇度顶点的个数必为偶数。 因为总度数是偶数，偶度顶点贡献偶数，剩下奇度顶点的度数之和也得是偶数，那它们只能有偶数个。

有向图对应版本：∑d+(v)=∑d−(v)=∣E∣\sum d^+(v)=\sum d^-(v)=|E|。

例：度数之和必为偶数，可用来快速否定。问「能否有一个 55 个顶点、各点度数为 3,3,3,3,33,3,3,3,3 的简单图」？度数和 =15=15 为奇数，违反握手定理，不存在。

度序列与可图化​

给定一列非负整数，能否画出一个简单图恰好以它为各顶点的度？这叫 可图化（graphical）判定，Havel–Hakimi 定理 给出递归办法：把序列降序排，取出最大度 dd，从其后 dd 个数各减 11，再降序、重复；若中途出现负数则不可图化，若最终全为 00 则可图化。

例：判断 (3,3,2,2,2)(3,3,2,2,2) 可否图化。降序已就绪，取出首项 33，把其后 33 个数各减 11：

(3,3,2,2,2) → (3−1‾,2−1,2−1,  2)=(2,1,1,2) →降序 (2,2,1,1)(3,3,2,2,2)\ \to\ (\underline{3-1},2-1,2-1,\;2)=(2,1,1,2)\ \xrightarrow{\text{降序}}\ (2,2,1,1)

再取出首项 22，后 22 个减 11：(2,2,1,1)→(2−1‾,1−1,  1)=(1,0,1)→降序(1,1,0)(2,2,1,1)\to(\underline{2-1},1-1,\;1)=(1,0,1)\xrightarrow{\text{降序}}(1,1,0)。再取出首项 11，后 11 个减 11：(1,1,0)→(1−1‾,  0)=(0,0)(1,1,0)\to(\underline{1-1},\;0)=(0,0)，全零，故 可图化。直觉上每步都是「让度最大的点先连出去」，逐步消化掉它的需求。

子图与补图​

  • 子图（Subgraph）：V′⊆VV'\subseteq V，E′⊆EE'\subseteq E，且 E′E' 的端点都在 V′V' 里。
  • 生成子图：保留全部顶点（V′=VV'=V），只删边。
  • 导出子图：选定 V′V' 后，把 V′V' 内部的边 全部 保留。
  • 补图 G‾\overline{G}：顶点相同，原来有边的现在没边、原来没边的现在补边。简单图 GG 与 G‾\overline{G} 的边集恰好拼成完全图。

特殊图​

名称记号描述边数
完全图KnK_nnn 顶点两两相连(n2)\dbinom{n}{2}
完全二部图Km,nK_{m,n}两部分 m,nm,n 顶点，跨部分两两相连mnmn
圈CnC_nnn 顶点环状相连nn
路径PnP_nnn 顶点链状相连n−1n-1
轮图WnW_n圈 CnC_n 加一个连所有顶点的中心2n2n

二部图​

二部图（Bipartite Graph）的顶点能分成两组 X,YX,Y，使得 每条边都跨组、组内无边——像「学生」与「课程」之间的选课关系。

判定有个漂亮的结论：一个图是二部图   ⟺  \iff 它不含奇圈。直觉是，二部图沿边走会在两组间「左右横跳」，要回到起点必须走偶数步。这也对应着「图的 22-着色」。

路径与连通​

概念​

  • 通路（walk）：顶点和边交替的序列，顶点、边都可重复。
  • 迹（trail）：边不重复的通路。
  • 路径（path）：顶点不重复（从而边也不重复）。
  • 回路 / 圈（cycle）：起点终点相同的路径。

简单说，限制越来越严：通路 → 不重边的迹 → 不重点的路径。

连通性​

无向图中，任意两顶点之间都存在通路，则为 连通图；否则图分裂成若干 连通分量（Connected Component）——每个分量是一块极大的连通部分。

有向图的连通分两个层次：

  • 强连通：任意两顶点 互相可达（uu 能到 vv，vv 也能到 uu）。
  • 弱连通：把方向擦掉、当成无向图后连通。

强连通比弱连通严格。一张图也可以划分成若干 强连通分量，这在编译器、依赖分析里是核心工具。

图的矩阵表示​

把图交给计算机，靠的就是矩阵——抽象的「连接」变成可计算的数。

邻接矩阵​

A=(aij)A=(a_{ij})，aija_{ij} 是顶点 vi,vjv_i,v_j 之间的边数（简单图里就是 0/10/1）。

  • 无向图的 AA 对称；有向图未必。
  • 关键性质：AkA^k 的 (i,j)(i,j) 项 == 从 viv_i 到 vjv_j 长度恰为 kk 的通路数。

最后一条很有用：邻接矩阵的幂能数路径，可达性、计数问题都能转化成矩阵运算。

例：取路径图 1−2−31-2-3（边 { 1,2 },{ 2,3 }\set{1,2},\set{2,3}），求从 11 到 33 长度恰为 22 的通路数。邻接矩阵

A=(010101010),A2=(101020101)A=\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix},\qquad A^2=\begin{pmatrix}1&0&1\\0&2&0\\1&0&1\end{pmatrix}

(A2)13=1(A^2)_{13}=1，确有一条 1→2→31\to2\to3；而 (A2)22=2(A^2)_{22}=2 表示从 22 出发走两步回到 22 有两条（2→1→22\to1\to2 和 2→3→22\to3\to2）。继续算 A3A^3，(A3)13=0(A^3)_{13}=0，说明 1,31,3 之间没有长度 33 的通路（奇偶性使然，二部图里同侧两点只有偶长通路）。

关联矩阵​

M=(mij)M=(m_{ij})，顶点 viv_i 与边 eje_j 关联时 mij=1m_{ij}=1。无向图每条边连两个端点，所以 每列恰有两个 11（列和为 22）——这其实就是握手定理的矩阵版。

最短路​

加权图上常问：从 uu 到 vv 边权之和最小的路径是多少？这就是 最短路（Shortest Path）问题，是导航、路由的核心。

  • 边权非负时，Dijkstra 算法 从起点出发，每次「贪心」地确定当前最近的未定点。
  • 允许负权时用 Bellman–Ford；求所有点对之间最短路则用 Floyd–Warshall（思想和上一章关系传递闭包的 Warshall 完全一致：让每个点轮流当中转站，看绕过它能否更近）。

Dijkstra 逐步算例​

例：顶点 { 1,2,3,4 }\set{1,2,3,4}，有向边权 1→2:11\to2:1、1→3:41\to3:4、2→3:22\to3:2、2→4:72\to4:7、3→4:33\to4:3，从 11 出发求单源最短路。维护距离表 dd，每轮取未定点中 dd 最小者「定下来」并松弛它的出边：

轮次定点d1d_1d2d_2d3d_3d4d_4
初始—00∞\infty∞\infty∞\infty
111001144∞\infty
22200113388
33300113366
44400113366

第 22 轮定下 22 后，经 2→32\to3 把 d3d_3 从 44 松弛到 1+2=31+2=3；第 33 轮定下 33，经 3→43\to4 把 d4d_4 松弛到 3+3=63+3=6（优于经 22 的 1+7=81+7=8）。最终 1→41\to4 最短路为 1→2→3→41\to2\to3\to4，长 66。贪心成立的前提是 边权非负：一旦某点被定下，没有更短的路能再绕回来。

Floyd 逐步算例​

例：同一张图用 Floyd 求全源最短路。初始矩阵 D(0)D^{(0)} 填入直接边权（无边记 ∞\infty，对角线 00），然后让 k=1,2,3,4k=1,2,3,4 依次当中转：

D(0)=(014∞∞027∞∞03∞∞∞0)D^{(0)}=\begin{pmatrix}0&1&4&\infty\\\infty&0&2&7\\\infty&\infty&0&3\\\infty&\infty&\infty&0\end{pmatrix}

k=2k=2 时检查「经过 22 是否更近」：D13←min⁡(4, D12+D23)=min⁡(4,1+2)=3D_{13}\leftarrow\min(4,\,D_{12}+D_{23})=\min(4,1+2)=3，D14←min⁡(∞,1+7)=8D_{14}\leftarrow\min(\infty,1+7)=8。k=3k=3 时：D14←min⁡(8, D13+D34)=min⁡(8,3+3)=6D_{14}\leftarrow\min(8,\,D_{13}+D_{34})=\min(8,3+3)=6，D24←min⁡(7,2+3)=5D_{24}\leftarrow\min(7,2+3)=5。最终

D(4)=(0136∞025∞∞03∞∞∞0)D^{(4)}=\begin{pmatrix}0&1&3&6\\\infty&0&2&5\\\infty&\infty&0&3\\\infty&\infty&\infty&0\end{pmatrix}

与 Dijkstra 的 1→4=61\to4=6 吻合。三重循环 k,i,jk,i,j 的写法和 Warshall 求传递闭包一模一样，只是把「∨\lor」换成了「取 min⁡\min」、把「∧\land」换成了「相加」。

树​

树（Tree）== 连通且无圈 的无向图。它是最简洁的连通结构——刚好连通，多一条边就出圈、少一条边就断开。文件系统、表达式解析、组织架构都是树。

等价定义​

设 ∣V∣=n|V|=n，下列条件相互等价（满足其一即为树）：

  1. TT 连通且无圈。
  2. TT 连通且 ∣E∣=n−1|E|=n-1。
  3. TT 无圈且 ∣E∣=n−1|E|=n-1。
  4. TT 中任意两顶点有且仅有 一条路径 相连。
  5. TT 连通，但删去任一条边后不再连通（边都是「桥」）。
  6. TT 无圈，但添加任一条边后恰好形成 一个圈。

把这些连起来理解：nn 个点的树恰好 n−1n-1 条边，是「用最少的边连通所有点」的方案，少一条就断、多一条就成圈。度为 11 的顶点称 叶子。

生成树​

连通图 GG 的 生成树（Spanning Tree）是它的生成子图且为树——保留所有顶点、抽掉一些边直到「刚好无圈连通」。任何连通图都有生成树。

加权图上找边权之和最小的生成树，就是 最小生成树（Minimum Spanning Tree，MST），对应「用最少成本把所有点连起来」（修路、铺网）。两个经典贪心算法：

  • Kruskal：把边按权 从小到大 排序，依次尝试加入，不形成圈就保留（用并查集判圈）。
  • Prim：从一个顶点出发，每次加入连接「树内与树外」的 最小边，逐步长大。

两者都基于同一条「切割性质」：横跨任一割的最小边一定属于某棵 MST。

Kruskal 逐步算例​

例：顶点 { 1,2,3,4 }\set{1,2,3,4}，无向带权边 { 1,2 }:1\set{1,2}:1、{ 2,3 }:2\set{2,3}:2、{ 1,3 }:3\set{1,3}:3、{ 3,4 }:4\set{3,4}:4、{ 1,4 }:5\set{1,4}:5，求最小生成树。按权从小到大依次考虑，用并查集判圈：

边权是否成圈决定
{ 1,2 }\set{1,2}11否加入
{ 2,3 }\set{2,3}22否加入
{ 1,3 }\set{1,3}33是（1,2,31,2,3 已连通）跳过
{ 3,4 }\set{3,4}44否加入
{ 1,4 }\set{1,4}55—（已 33 条边）停止

44 个顶点选满 n−1=3n-1=3 条边即停。MST 为 { { 1,2 },{ 2,3 },{ 3,4 } }\set{\set{1,2},\set{2,3},\set{3,4}}，总权 1+2+4=71+2+4=7。

Prim 逐步算例​

例：同一张图，从顶点 11 出发用 Prim。每轮在「树内连树外」的边里挑最小的：

轮次树内顶点候选最小边加入边（权）
1{ 1 }\set 1{ 1,2 }:1\set{1,2}:1{ 1,2 }\set{1,2}（11）
2{ 1,2 }\set{1,2}{ 2,3 }:2\set{2,3}:2{ 2,3 }\set{2,3}（22）
3{ 1,2,3 }\set{1,2,3}{ 3,4 }:4\set{3,4}:4{ 3,4 }\set{3,4}（44）

同样得总权 77 的树。两个算法路径不同——Kruskal 全局排边、Prim 从一点长大——但因切割性质，结果权值必然相同。

欧拉图与哈密顿图​

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

欧拉条件的直觉：每次「路过」一个顶点都要「进一条边、出一条边」，成对消耗，所以中间顶点的度必须是偶数；起点和终点若不同，则它俩可以是奇度。柯尼斯堡七桥的四块陆地全是奇度（共 44 个奇度点 >2>2），所以一笔走完不可能——这就是欧拉的答案。

tip

欧拉看边、哈密顿看点——一字之差，难度天壤。

判断欧拉图只需数一数奇度顶点，是 多项式时间 能解的；而判断哈密顿图属于 NP-完全，一般图上 没有已知的高效算法。直觉上「遍历每条边」有局部的度数约束可循，「遍历每个点」却是全局的、牵一发动全身。

判欧拉算例​

例：七桥问题。四块陆地的度数（按桥数）为 5,3,3,35,3,3,3，奇度点有 44 个，既超过 22，故 既无欧拉回路也无欧拉通路——一笔走遍七桥不可能。

例：完全图 K5K_5 每个顶点度为 44，全是偶数且连通，故 有欧拉回路。而 K4K_4 每点度为 33，奇度点有 44 个，无欧拉通路。一般地，KnK_n 有欧拉回路   ⟺  n\iff n 为奇数（此时每点度 n−1n-1 为偶）。

判哈密顿算例​

例：圈 C5C_5（55 个顶点的环）显然有哈密顿回路——它本身就是。但用 Dirac 定理验证却「测不出来」：每点度为 2<5/22<5/2，不满足充分条件。这印证了 Dirac/Ore 是 充分非必要——条件不满足，不代表没有哈密顿回路，得另行判断。

例：含 悬挂点（度为 11）的连通图一定 没有哈密顿回路，因为回路要求每点恰好进出各一次、度至少为 22。这是排除哈密顿回路最快的一招。

哈密顿图的充分条件​

虽无充要条件，但有好用的 充分条件。设简单图 GG 有 n≥3n\ge 3 个顶点：

  • Ore 定理：若对任意 不相邻 顶点 u,vu,v 都有 d(u)+d(v)≥nd(u)+d(v)\ge n，则 GG 是哈密顿图。
  • Dirac 定理（Ore 的推论）：若每个顶点 d(v)≥n/2d(v)\ge n/2，则 GG 是哈密顿图。

直觉是「边足够多、足够稠密」就一定能串起一条遍历所有点的回路。注意这是充分非必要——圈 CnC_n 是哈密顿图却不满足条件。

平面图与欧拉公式​

平面图（Planar Graph）是能画在平面上、边互不交叉 的图。电路板布线、地图绘制都关心平面性。

平面图把平面分成若干 面（Face，含无界的外部面）。欧拉公式：连通平面图满足

V−E+F=2V-E+F=2

其中 V,E,FV,E,F 分别是顶点数、边数、面数。这是一条极强的约束，由它能推出简单连通平面图（V≥3V\ge 3）必有 E≤3V−6E\le 3V-6。据此可证 K5K_5（完全图）和 K3,3K_{3,3}（三对三完全二部图）都不是 平面图——它们边太多塞不下。

库拉托夫斯基定理 进一步给出充要刻画：一个图是平面图当且仅当它不含 K5K_5 或 K3,3K_{3,3} 的「细分」。

例：用欧拉公式求面数。一个连通平面图有 V=6V=6 个顶点、E=9E=9 条边，问它把平面分成几个面？由 V−E+F=2V-E+F=2 得 F=2−V+E=2−6+9=5F=2-V+E=2-6+9=5（含外部面）。

例：用 E≤3V−6E\le 3V-6 证 K5K_5 非平面。K5K_5 有 V=5V=5、E=(52)=10E=\binom{5}{2}=10，而 3V−6=9<103V-6=9<10，边数超标，故 不可能画成平面图。对 K3,3K_{3,3} 则要用更强的 E≤2V−4E\le 2V-4（二部图无三元环，每个面至少 44 条边界）：V=6,E=9V=6,E=9，2V−4=8<92V-4=8<9，同样非平面。这两条不等式都是欧拉公式的直接推论。

对偶图​

给定平面图，把 每个面 变成一个顶点，相邻的面之间 连一条边（对应它们共享的原边），得到 对偶图（Dual Graph）。对偶把「面」和「点」的角色互换，在地图着色、电路分析里很有用。

图的着色​

顶点着色​

用 kk 种颜色给顶点染色，要求 相邻顶点颜色不同。所需的 最少 颜色数称 色数（Chromatic Number）χ(G)\chi(G)。

着色抽象的是「冲突分组」——把互相冲突的东西分到不同组里，最少分几组。考试排考场（同一学生的科目不能撞）、寄存器分配（同时活跃的变量不能共用寄存器）都是着色。

  • 二部图：χ=2\chi=2（充要：无奇圈）。
  • 完全图 KnK_n：χ=n\chi=n（人人相邻，只能各染一色）。
  • 圈 CnC_n：偶圈 χ=2\chi=2，奇圈 χ=3\chi=3。

例：求 C5C_5（五元奇圈）的色数。先证 χ≥3\chi\ge3：若只用两色，沿环交替染 1,2,1,2,…1,2,1,2,\dots，绕一圈回到起点时第 55 个顶点是 11，却与起点（也是 11）相邻，冲突，故 22 色不够。再给出一种 33 色方案 1,2,1,2,31,2,1,2,3 确实合法，所以 χ(C5)=3\chi(C_5)=3。

例：求轮图 W5W_5（C5C_5 外加一个连所有顶点的中心）的色数。外圈是奇圈需 33 色，中心与外圈每点都相邻、不能用外圈用过的任何色，得再加 11 色，故 χ(W5)=4\chi(W_5)=4。一般地，WnW_n 当外圈为奇圈时 χ=4\chi=4、偶圈时 χ=3\chi=3。求色数的通法是「下界靠找团 / 奇圈，上界靠给出构造」，两边夹出确切值。

四色定理​

四色定理（Four Color Theorem）：任何 平面图 的色数 ≤4\le 4，即任何地图用四种颜色就能让相邻区域不同色。它于 19761976 年首次借助计算机穷举验证完成，是历史上第一个主要依赖计算机的著名证明，至今没有纯手工的简短证明。

边也可着色：边着色 要求共端点的边不同色，最少颜色数称 边色数，对应任务调度里「同一时刻同一资源不能两用」的约束。