概念地图
图
顶点加边；许多计数问题在这里变成结构问题。
深色为本章概念，浅色为其他章
陪练模式
不想只是读？让它带你走一遍。
导师把这一章拆成小步，每一步先问你，再讲；你用自己的话答，它先认下对的部分再纠偏。用你自己的 AI，对话只存在这台设备上。
定位01
延伸阅读
欧拉 · 1736 年 · 哥尼斯堡七桥
把一个关于城市桥梁的问题抽掉几何信息，只留下连接关系，从而给出不可能性的证明。他反对的是靠试走来回答；代价是这一步同时丢掉了距离与方位，凡是依赖它们的问题都无法再用这个模型。
奠基
十九世纪的图论发展 · 凯莱、柯克曼等
把图从一次性技巧变成一个研究对象，处理树的计数与着色问题。这一步让「结构」本身成为可计数的东西；代价是许多自然问题（如着色数）没有像计数公式那样的闭式。
转向
计算复杂性的介入 · 二十世纪后半叶
证明了图上的一批自然问题（如判定三着色）在计算上极难，因此「有定义」与「算得出」被彻底分开。这是对「建模成图就解决了」这一读法的正面修正。
修正
布鲁迪 · 图论导引一章
本课对象。教材从定义与握手引理入手，本章要说清握手引理正是第 3 章那条「两种数法」，只是数的对象换成了边的端点。
本课对象
机制02
只留连接关系
把七座桥的问题变成可解的那一步，不是想出了什么技巧，而是丢掉了信息：桥有多长、岛在哪个方位全部不要，只留「谁和谁相连」。这样得到的对象就是一个图。这是第 1 章那条原则在结构问题上的样子：先定等价——两个布局若连接关系相同就算同一个图。丢掉的信息越多，能回答的问题越少，但能回答的那些会变得非常干净。
机制一个空间布局通过只保留连接关系被换成一个可以计数与判定的结构对象。
可迁移性测试
换到服务依赖：把机房位置、带宽、协议版本全部丢掉，只画「谁调用谁」，就能立刻判断有没有循环依赖。不同构的地方在于循环依赖的危害程度确实依赖带宽与超时设置，而这些正是被丢掉的信息。
机制03
数端点，不数边
图上的第一条定理不需要任何技巧，欧拉那条线索留下的第一个形式结果就是它——握手引理。它在本课论证里的位置很具体：它是第 3 章那条「两种数法」的又一次应用，只是这次被数两遍的集合换成了「（边，它的一个端点）」这样的配对，而下一块的推导会把这一点摊开。
机制边的端点集合通过被按顶点与按边两种方式清点给出一条恒等式。
可迁移性测试
换到会议出席统计：把每场会议的出席人次加起来，等于每个人参加的场次之和——两边数的都是「（人，会）」这样的配对。不同构的地方在于会议可以有一个人或很多人，而普通图的每条边恰好两个端点，所以那里的系数是 2。
推导04
握手引理与它的一个直接后果
这一段要证的是度数之和等于边数两倍，并由它推出奇度顶点必为偶数个。
图是有限的、无向的、无自环的
定理前提。有自环时通常约定它给该顶点贡献 2，否则等式要改写。
顶点 的度数 定义为与它关联的边数
定理前提，也是这条定理的全部内容所在：度数是按边数的。
每条边恰有两个端点
定理前提。超图允许一条边连多个顶点，那里的系数不再是 2。
推导 · 0 / 4
推导实例05
七桥问题：不可能性从哪一步得到
为什么哥尼斯堡的七座桥不能一次不重复地全部走遍？
把「一笔画」翻译成度数条件，再用握手引理的后果。
裂缝06
本章命题的边界
争议地形07
本书主张
把问题抽象成图能把复杂情形化为可判定的结构问题，图论提供了一整套现成的定理。
另一种看法
复杂性一线主张：抽象成图只解决了「有定义」，没有解决「算得出」；图上的许多自然问题在计算上极难，因此建模成功之后往往仍然无从下手，甚至比原问题更容易让人误以为已经解决。
分歧扎在
分歧扎在「建模成功算不算解决」这一条上，而不在数学上。两边都同意抽象是必要的一步，争的是抽象之后剩下的困难有多大。
什么证据能裁决
能裁决它的是实例上的表现：把一批现实问题抽象成图之后，统计其中有多少能在可接受时间内得到答案。若比例很高，建模即解决的主张成立；若多数落在难解的一类，抽象只是把困难换了位置。
目前的证据把天平压向「取决于落在哪一类问题」：连通性、匹配、最短路一类有高效算法，着色、团、哈密顿路一类没有。还差的是一个事前判断新问题会落在哪一类的判据——现有做法多是先归约再说。
边界与反例08
把「只留连接关系」的建模承诺写成可检验的规格
要检验的建模承诺是：某个现实系统的关键行为只依赖连接关系，因而丢掉其余信息不影响结论。
去掉哪条假设：被丢掉的属性（距离、容量、时序、类型）对目标结论无影响
抽象成图能代表现实的前提；某个被丢掉的属性一旦起作用，图上的结论就不再适用。
该情形下的具体反例：两个连接关系完全相同的服务依赖图，因超时设置不同而一个会雪崩、一个不会
图完全相同，行为不同，说明结论依赖了被丢掉的属性。
这条承诺对应的可观测量：连接关系相同而被丢属性不同的一组真实系统，其目标行为
必须找到图同构而属性不同的实例对，否则无法分辨。
什么观测算它不成立：图同构的实例对在目标行为上的差异超过事前登记的阈值
阈值按行为本身的自然波动事前定死。
事前登记的失败条件：差异超阈值，或图上的预测在实例对中至多对一半
两者都按承诺不成立处理。
推导 · 0 / 3
接口09
挂在哪个槽位
挂在哪个槽位你已有的那条结论多半是「画个图就清楚了」——一条关于可视化的判断。本章要动的是它真正起作用的地方。
本章对你已有的结构做的是 (a) 替换「画图让人看清」这条结论，还是 (b) 约束它：起作用的是丢掉了什么，而不是画出来了什么？
慢变量登记两个慢变量：你最近画的结构图里有几张写明了丢掉哪些属性，以及有几次结论其实依赖了被丢掉的那一项。三天后先看第二个。
小结10
本章小结
01图是一次刻意的信息丢弃，只保留连接关系；丢得越多，能答的问题越少但越干净。
02握手引理是「两种数法」在端点配对集合上的应用，不需要任何技巧。
03「奇度顶点必为偶数个」是握手引理加奇偶算术的直接后果。
04有向、超边、自环各自打破一条前提，等式的形式随之改变。
05唯一承担观测风险的是「被丢掉的信息对结论无影响」。
提取练习 · 合上书，先自己答一遍。
?「度数之和等于边数的两倍」是 (a) 由两种数法得到的 还是 (b) 关于现实的建模承诺？
?七桥的不可能性来自 (a) 搜索了所有路径 还是 (b) 一个必要条件不被满足？
受迫二选一11
B 标签辨识
「所有顶点度数之和等于边数的两倍」这一步是什么？
二选一
受迫二选一12
C 裂缝定位
哪个情境下本章框架会给出自信而错误的答案？
二选一
读到这里，把它记为已读。