大学算法图论第 1 讲：把握手定理、存储结构和那些“背下来的结论“，全部跑一遍

大家好我是熊猫钓鱼欢迎大家和我一起探讨技术。希望您能点赞关注谢谢这是《把定理跑出来》系列的第一篇面向大学计算机的「数据结构·图」与「离散数学·图论」课程。这门课的常规学法是定义背下来、定理证明看一遍、结论记在错题本上。但握手定理、“完全图 n(n−1)/2 条边”、稀疏图用邻接表这些结论背下来和长在身上是两回事。这个系列的做法是课本每给出一个结论我们就在计算机里造几十万个图去检验它——顺便把结论背后的边界条件、考试爱挖的坑一起跑出来。全文 8 张图全部由文末代码生成随机种子固定SEED2026任何机器可复现。摘要本讲覆盖图论入门的三块基石每块都有实测数据握手定理Σdeg(v) 2|E|K₅/K₁₀/K₂₀、ER 随机图、含 20 个自环的图全部严丝合缝264 2641000 个随机图的奇数度顶点个数全为偶数有向图细节——出度和 入度和 915但边数 921差的 6 是自环每个自环同时贡献 1 出度 1 入度计数公式K₆₀ 实测 1770 边 60×59/220 组随机图的 |E(G)| |E(补图)| 恒等于 C(n,2)度序列与同构度序列 [2,2,2,2,2,2] 可以是六元环 C₆也可以是两个三角形 2×C₃——度序列相同推不出同构判断题高频坑Erdős–Gallai 可图化判定与暴力构造 189 组零分歧经典陷阱序列 [3,3,3,1]和为偶数但不可图化被准确拒绝存储结构横评邻接矩阵 vs 邻接表内存与耗时各测两档密度——稀疏图上表省一个数量级0.3 vs 4.0 MB、判边稠密图上矩阵快 78 倍28 vs 2175 ms、遍历邻居稀疏图上表快 60~90 倍关键反转稠密图上表的内存反超矩阵 18 倍73.4 vs 4.0 MB稀疏用表的边界条件第一次被量化出来随机图初探G(3000, 0.02) 的实测度分布与理论二项分布完全重合连通性相变实验显示平均度刚过 1最大连通分量占比从 0.01 陡升到 0.58。关键词图论入门握手定理邻接矩阵邻接表度序列图同构Erdős–Gallai随机图连通性相变目录0. 系列计划六讲把图论课跑穿1. 图的最小定义与术语速查2. 握手定理每根柱子都严丝合缝2.1 自环与有向图的两个细节2.2 推论奇数度顶点必有偶数个2.3 考试怎么考3. 计数公式从完全图到补图4. 度序列、可图化与同构的坑5. 四种存储结构背图不如实测5.1 内存n² 的税与 m 的税5.2 操作耗时两个方向的优势5.3 考试怎么考6. 彩蛋随机图的两张面孔7. 本讲检查清单8. 复现指南9. 下一讲预告0. 系列计划六讲把图论课跑穿先亮出整个系列的地图对齐多数教材的章节顺序也覆盖 408 考研图论考纲讲次主题要跑出来的结论第 1 讲本篇基本概念、度数、存储握手定理计数公式度序列≠同构存储结构横评第 2 讲DFS/BFS 与连通性遍历序列与存储结构的关系连通分量计数ER 连通相变完整版第 3 讲欧拉图与哈密顿图一笔画充要条件的构造性验证Hierholzer 逐步生成哈密顿的 NP 难规模墙第 4 讲最短路三件套Dijkstra 负权失效反例Floyd 的 O(n³) 规模墙三算法横评第 5 讲生成树与拓扑排序MST 切割性质实测Kruskal/Prim 分野AOE 关键路径工期第 6 讲网络流与二分图匹配最大流最小割定理数值验证Hall 定理Konig 定理对拍每一讲的结构都一样课本怎么说 → 我们跑给你看 → 考试怎么考 → 代码复现。这个系列不做知识普及课本已经写得很好做的是把背下来的结论升级成跑出来的直觉。1. 图的最小定义与术语速查一个图G (V, E)顶点集 V边集 E。本讲反复用到的术语一张表过完术语定义本讲实验里的角色度 deg(v)与 v 关联的边数自环算 2 度握手定理的主角完全图 Kₙ任意两点都有边边数公式验证补图 Ḡ把没有的边全补上边数守恒验证度序列所有顶点的度排成的序列同构反例的载体可图化序列存在某个图以它为度序列Erdős–Gallai 定理同构两图形状相同存在保边的双射判断题高频坑连通分量极大连通子图相变实验的主角ER 随机图 G(n,p)n 个顶点每对以概率 p 连边本讲的实验小白鼠下面所有实验的图都用同一个极简实现支持自环、无平行边classGraph:def__init__(self,n,directedFalse):self.adj[set()for_inrange(n)]# 邻接表self.loops[0]*n# 自环计数self.m0defdegree(self,v):returnlen(self.adj[v])2*self.loops[v]# 自环贡献 2 度2. 握手定理每根柱子都严丝合缝课本原话在任何无向图中所有顶点的度数之和等于边数的两倍即 Σdeg(v) 2|E|。证明一句话每条边贡献两个端点所以被数两次。——但每条边贡献两度这句话在自环和有向图上怎么落地课本往往一笔带过。我们直接跑图 1左五类图的 Σdeg(v) 与 2|E| 对比。K₅ 2020、K₁₀ 9090、K₂₀ 380380、ER(200,0.03) 11981198、含 20 个自环的图 264264——每根柱子都严丝合缝。右1000 个随机图的奇数度顶点个数分布全部落在偶数上。2.1 自环与有向图的两个细节细节 1自环为什么算 2 度实验里那个120 条普通边 20 个自环的图如果自环按 1 度算Σdeg 会是 244 ≠ 264 2|E|握手定理当场破产。自环的两个端点是同一个顶点所以它给这个顶点的度数贡献 2——握手定理成立本身就反过来规定了自环的计数规则。细节 2有向图的出度和 入度和 边数实测n150、p0.04 的有向随机图Σ出度 Σ入度 915但边数 |E| 921。差哪去了差在 6 个自环上——我的实现里自环不进邻接表单独用loops[]计数所以出度和/入度和统计不到它们。若按课本约定自环的出度 1、入度 1则 Σ出度 Σ入度 921 |E|严格成立。这 6 的差值本身就是活教材自环怎么算从来不是定义题是约定题——你的实现和课本的约定不一致时定理看起来就像错了。写图算法先统一自环规则。2.2 推论奇数度顶点必有偶数个课本原话奇数度顶点的个数为偶数。推理Σdeg 2|E| 是偶数奇数度顶点的度贡献奇数偶数个奇数相加才是偶数。1000 个随机图n 从 10 到 60、p 从 0.02 到 0.3实测奇数度顶点个数全部是偶数最大出现过 38 个。2.3 考试怎么考判断题“存在一个简单图度序列为 [3,3,3,1]” → 和为 10 是偶数握手定理过了但不存在见第 4 节 Erdős–Gallai选择题“无向图 G 有 16 条边8 个顶点其中 7 个顶点的度都是 3第 8 个顶点的度是” → Σdeg 2×16 3232 − 21 11填空题“n 个顶点的无向完全图有 ____ 条边” → 第 3 节实测。3. 计数公式从完全图到补图课本原话Kₙ 有 n(n−1)/2 条边完全二分图 K_{a,b} 有 a×b 条边。图 2左Kₙ 边数实测 vs 公式曲线n 到 60实测 1770 60×59/2每个点都压在线上。右20 个随机图的 |E(G)| |E(补图)| 恒等于 C(n,2)——G 有多少边不重要它和补图加起来永远是那个数。补图这个性质考试常以这种形式出现“n8 的图 G 有 7 条边它的补图有几条边” → C(8,2) − 7 21 − 7 14。图 2 右把 20 个随机图的堆叠柱画出来红虚线就是 C(n,2) 的天花板——每根柱子都顶到线上一次都没有例外。4. 度序列、可图化与同构的坑坑 1度序列相同 ⟹ 同构吗不。这是判断题最爱挖的坑我们造一个最小反例图 3六元环 C₆ 与两个三角形 2×C₃。度序列都是 [2,2,2,2,2,2]但 C₆ 去掉任何一个顶点后仍连通最少 1 块2×C₃ 去掉一个顶点后至少碎成 2 块——去点后的连通性这个不变量不同所以不同构。坑 2度序列合法吗判定一个序列能不能成为某个简单图的度序列叫可图化问题。课本给的是必要条件和为偶数但充分的判定是 Erdős–Gallai 定理1960非增序列 d₁≥…≥dₙ 可图化当且仅当和为偶数且对一切 kΣᵢ₌₁..k dᵢ ≤ k(k−1) Σᵢ₌ₖ₊₁..ₙ min(dᵢ, k)我拿它跟暴力构造stub 配对模型随机配对 20 万次找简单图实现对拍 300 组随机序列189 组可判定的全部一致零分歧。经典陷阱序列的判定结果序列和握手定理Erdős–Gallai结论[3,3,3,1]10过不过不可图化——考试判断题的标准反例[4,3,3,2,2]14过过可图化[5,5,5,5,5,5]30过过可图化就是 K₆[4,4,4,4,4,4]24过过可图化八面体图5. 四种存储结构背图不如实测数据结构课本在这一节花了最多篇幅邻接矩阵、邻接表、十字链表有向图、邻接多重表无向图。四种结构的图各画各的但**“什么时候用哪个课本只给了一句稀疏用表、稠密用矩阵”**。这句口诀的边界到底在哪跑。图 8四种存储结构对齐在一张图上示例图 5 点 5 边。邻接矩阵的对称性压缩存储考点、邻接表的链式结构、十字链表入弧链 出弧链的双索引设计、邻接多重表一条边只存一个结点的去重思想——课本分散在三页的内容一张图看完。5.1 内存n² 的税与 m 的税图 4实测内存tracemalloc 口径。稀疏图m2n矩阵 1.0/4.0 MB vs 表 0.1/0.3 MB——表省一个数量级。稠密图mn²/4反转——表 18.2/73.4 MB vs 矩阵 1.0/4.0 MB表贵 18 倍。“稀疏用表这句口诀原来是有下半场的当边多到一定程度邻接表里每个 int 结点的指针和对象开销Python 里尤其夸张会反超矩阵的每格 1 字节”。矩阵交的是n² 的固定税表交的是m 的变动税——谁贵看密度。5.2 操作耗时两个方向的优势图 5左判断u-v 是不是边10 万次查询。稠密 n2000矩阵 28ms vs 表 2175ms——矩阵快 78 倍O(1) 下标 vs O(deg) 线性扫。稀疏时表反而快8 vs 21ms因为 deg≈2 的链表比 numpy 索引的 Python 循环开销还低。右遍历全图邻居。矩阵 3.6~6.4ms vs 表 0.0~0.1ms——表快 60~90 倍矩阵要扫 n² 个格子表只走 2m 个结点。把两张图合起来读就是本讲最重要的一条工程结论判边找矩阵遍历找表。没有更好的存储只有更适合操作的存储——BFS/DFS 天天遍历邻居所以算法题默认邻接表图数据库/社交网络天天问A 和 B 认识吗所以用矩阵或哈希。5.3 考试怎么考408 真题在这节的出题套路基本固定“下列哪种存储结构便于判断两点之间是否有边” → 邻接矩阵“n 个顶点 e 条边的无向图邻接表存储需要多少个表结点” →2e每条边存两次——握手定理在存储上的投影“邻接矩阵适合 ____ 图邻接表适合 ____ 图” → 稠密 / 稀疏图 4 告诉你这个口诀的边界在哪“十字链表适用于 ____ 图邻接多重表适用于 ____ 图” → 有向 / 无向。6. 彩蛋随机图的两张面孔课程大纲里随机图通常不考但它是理解图论为什么有用的最好入口——真实世界的所有网络社交、网页、路网都是随机图变体。两个小实验收尾图 6G(3000, 0.02) 的度分布。平均度实测 60.3理论值 (n−1)p 59.98红点理论二项分布整个压在蓝柱实测上。课本说ER 图度分布近似泊松——你不需要背看一眼图就永远记得。图 7连通性相变n800每档 40 次重复。横轴 cpc/n即平均度纵轴最大连通分量占比c1 时图碎成一地小片占比 0.02c 刚过 1巨分量瞬间诞生c1.52 时已吞下 58% 的顶点——这就是随机图论著名的0-1 律。紫色虚线标出理论线 c≈ln n≈6.7那里才几乎必然全连通本实验只扫到 1.6这条线留给你自己复现。为什么课程要关心这个因为它解释了一个工程现象社交网络六度空间、病毒式传播、网络攻防的断网阈值——都建立在平均度过 1 巨分量出现这个相变上。7. 本讲检查清单学完这一讲合上书你应该能回答□ 握手定理对自环怎么算自环贡献 2 度有向自环出度1 入度1 □ Kₙ 多少条边补图边数怎么算n(n−1)/2C(n,2)−|E(G)| □ 度序列相同能推出同构吗不能记住 C₆ vs 2×C₃ □ [3,3,3,1] 可图化吗不可——和为偶数只是必要条件充分看 Erdős–Gallai □ 邻接表存无向图要多少表结点2e握手定理的投影 □ 稀疏/稠密图各用什么存储判边找矩阵、遍历找表内存边界看图 4 □ 平均度刚过 1 时随机图发生什么巨分量诞生0-1 律8. 复现指南graph-course/ ├── course1.py # 六组实验内核Graph 实现 E1~E6~300 行 ├── figs1.py # 8 张配图 ├── results/course1.json # 全部实验数据 └── figures/ # 8 张图python course1.py# 跑六组实验 → results/course1.jsonpython figs1.py# 生成 8 张图环境Python 3.11 numpy matplotlib无其他依赖。种子 SEED2026重跑逐字节一致耗时数据毫秒级抖动正常。本讲涉及的每个课本结论都有对应的断言握手定理五类图精确相等、奇数度顶点 1000 次全偶、Erdős–Gallai 与暴力 189 组零分歧、计数公式逐点核对——不是演示是验证。9. 下一讲预告第 2 讲《遍历与连通》DFS/BFS 的序列为什么和存储结构绑定连通分量、双连通分量、强连通分量Tarjan各解决什么问题以及——把本讲图 7 的相变实验做完整扫到 cln n看几乎必然连通长什么样。这个系列不替你背书只负责让每一个被背下来的结论都先在你眼前发生过一次。系列目录第 1 讲 基本概念与存储本篇· 第 2 讲 遍历与连通 · 第 3 讲 欧拉图与哈密顿图 · 第 4 讲 最短路三件套 · 第 5 讲 生成树与拓扑排序 · 第 6 讲 网络流与匹配