图论 · 从基础语言到现代结构理论
一张 graph 只是「一组顶点 + 一组连接它们的边」，简单到能写在餐巾纸上；难的是从这点结构里推出深刻的定理。本系列沿一条经典脉络铺开 （Diestel 教材的骨架）：先把基础语言说清楚，再看五类经典结构 （匹配 / 连通性 / 平面图 / 着色 / 流），然后看一类反复出现的母题——整体条件如何逼出局部结构 （极值 / Ramsey / Hamilton / 随机图），最后落到现代结构理论 （无限图与图子式）。
每页都把抽象定义落到一张能动手的图上：拖顶点、改参数、点单步，看增广路怎么扩、切分怎么分两侧、着色怎么回退、Euler 公式怎么对上数。能单步执行的算法走统一的 frame 引擎 （预先展开成快照、纯函数渲染）；纯定理则用构造 / 反例 / 等价刻画把「为什么成立」摆出来。前置知识只需读得懂集合与简单计数；若想先熟悉图上的算法，可看 Shortest Path 与 MST。
图的基本语言：顶点、边、度、路、圈、连通
从最小的词汇起步：vertex / edge / degree，握手引理 Σdeg = 2|E| 为何恒成立；walk / path / cycle 的区别；一张图怎么裂成若干连通分支，哪些点是 cut vertex、哪些边是 bridge；再认识 tree / forest、bipartite、complete 与 multigraph。在一张图上点亮这些概念。
子图谱系：子图、导出、生成、细分、子式
「从一张图里取出一张小图」有好几种严格不同的方式，层层放宽：subgraph 删点删边、induced subgraph 选一组点连带其全部内部边、spanning subgraph 留全部点；再到改写拓扑结构的两类——subdivision / topological minor（把边换成路）与 minor（允许收缩连通块成点）。并排看同一张图按不同方式取出的结果，这套层级是图子式理论的入口。
匹配：增广路与三条配对定理
matching = 一组两两不共端点的边。怎么把它做到最大？单步走增广路 (augmenting path)：沿「未匹配——匹配」交替路翻转，每找到一条匹配数 +1。再看三块基石：Hall 定理（二部图完美匹配的充要条件 = 邻集不缩水）、König 定理（二部图里最大匹配 = 最小点覆盖）、Tutte 定理（一般图完美匹配的奇分支判据）。
连通性：分隔集与 Menger 定理
一张图「有多连通」？答案藏在两个对偶的量里：要拆开两个点 s, t 最少删几个点 (separator)，与它们之间最多能找出几条内部不相交的路。Menger 定理说这两个数恒相等——局部的「路冗余」等于全局的「难拆程度」。单步找出不相交路、再标出最小分隔集看二者对齐；并引出 Mader 定理 与高连通度下必含的稠密子结构。
平面图：Euler 公式、Kuratowski 与对偶
哪些图能画在纸上而边不交叉？平面图把平面切成若干面 (face)，顶点、边、面三者被 Euler 公式 V - E + F = 2 死死拴住，由此推出「平面图边数 ≤ 3V−6」。Kuratowski / Wagner 定理给出终极判据：不可平面 ⟺ 含 K₅ 或 K₃,₃ 的子式。再看每张平面图如何生成它的对偶图，面变点、边仍是边。
着色：顶点、边、列表与完美图
给顶点染色使相邻异色，最少几种颜色 = 色数 χ(G)。贪心着色随顶点序受 Δ+1 约束，单步看它何时被迫开新色；再到边着色（Vizing 定理把边色数锁在 Δ 或 Δ+1）、list coloring（每点各有自己的可选色单），以及 χ = ω 恒成立的完美图 (perfect graph)。四色定理在这里只是冰山一角。
流：网络流、最大流-最小割与群流
在带容量的有向网络里，从源 s 到汇 t 最多能推多少流量？单步沿残量网络找增广路 (Ford–Fulkerson)，并直接看到最大流 = 最小割这一对偶——它正是 König / Menger 的共同祖先。再看抽象化的群流 (group-valued flow) 与令人意外的流–着色对偶 (Tutte)：平面图的流数与对偶图的色数互为镜像。
极值图论：边一多就躲不开的子结构
「边足够多的图，必然含某个固定子图」——这是极值图论的母题。Turán 定理给出不含 K_{r+1} 的图的最大边数，极图是均匀的完全多部图；单步加边看三角形在越过门槛的瞬间被迫出现。再眺望两座高峰：Hadwiger 猜想（χ ≥ t ⟹ 含 K_t 子式）与 正则性引理（任何稠密图都能切成近似随机的少数块）。
Ramsey 理论：完全的混沌并不存在
把 K₆ 的边任意红蓝二染，必出现同色三角形——这不是巧合，而是 Ramsey 定理：结构大到一定程度，有序必然涌现。交互地给完全图边染色，看同色 K_s 如何躲不掉；理解 R(3,3)=6 的两面（下界靠构造一张无同色三角的 5 点染色、上界靠鸽巢），以及 Ramsey 数为何增长得快到至今算不出 R(5,5)。
Hamilton 圈：度数够高就一定绕得回来
能否找一个圈恰好经过每个顶点一次 (Hamiltonian cycle)？判定本身 NP-完全，但「整体度数足够大」可作充分保证：Dirac 定理（每点度 ≥ n/2）、Ore 定理（任两不相邻点度数之和 ≥ n）。单步用旋转-延伸 (rotation–extension) 从一条最长路逼出哈密顿圈，看度数条件如何在每一步堵死「走投无路」。
随机图：概率方法与阈值现象
不去构造而去「抽样」：G(n,p) 每条边独立以概率 p 出现。随 p 增大，「连通」「含三角形」「无孤立点」等性质几乎都在某个阈函数 (threshold) 处骤然从「几乎必不」翻转到「几乎必然」。拖动 p 看连通分支瞬间汇成巨块（巨型分支涌现），并理解概率方法：用「随机图存在」反证「某种图存在」。
无限图：射线、末端与拓扑圈空间
顶点无穷多时，许多有限图的直觉失效，却生出全新结构。无限图「通往无穷」的方向用射线 (ray) 刻画，等价的射线归并成一个末端 (end)——图的「无穷远点」。把图连同它的末端补成一个紧拓扑空间，有限图里的「圈空间」就推广成拓扑圈空间，让 Euler 回路、生成树等定理在无限图上重新成立。可视化无限二叉树 / 网格的射线与末端。
图子式理论：树宽与图子式定理
二十世纪图论的巅峰。树分解 (tree decomposition) 把一张图摊到一棵树上，树宽 (treewidth) 量度它「离树有多远」——树宽小的图，难题大多变易。图子式定理 (Robertson–Seymour)：任意无穷图序列里总有一张是另一张的子式（图在子式序下良拟序），因此每个对子式封闭的图类都有有限的禁用子式清单（Kuratowski 是其特例）。可视化树分解的袋 (bag) 沿树滑动。
这套体系为什么这样分层
相关链接
- Reinhard Diestel — Graph Theory diestel-graph-theory.com 本系列分层骨架所本的标准研究生教材；作者主页提供电子版与勘误。
- Wikipedia — Graph theory en.wikipedia.org 术语、定理与历史的索引式总览，适合按词条对照本系列各页。
- Shortest Path · Dijkstra 本站 图上的算法侧：relaxation 与单步 settle，与本系列的「流 / 连通性」互为补充。
- Minimum Spanning Tree · Prim / Kruskal 本站 生成树与切分定理的算法实现，正好对照本系列「基础语言」里的 tree / cut。