第9章 远征地图档案：特殊图类

第 9 章 · 远征地图档案：特殊图类

章节摘要：远征凯旋在望，参谋部开始整理行囊里积攒的地图档案——那些在前几章战役中反复露面、各自携带独特性质的特殊图类。欧拉图与哈密顿图把第 1 章的七桥问题与"绕全城巡视"并置对照：一笔画有干净的判定定理，全程巡视却是著名难题；平面图研究"边不交叉"的地形，欧拉公式与五色四色定理在此安家；随机图与小世界则打开另一扇门——当图不再是设计出来而是"掷骰子长出来"的，结构会自己涌现。把特殊图类归档，等于给全册见过的图建立户籍系统，也为第 10 章的实战检阅备好检索索引。

本章知识点清单

读完本章，下列考核点应当条条落地：

1. 陈述并证明欧拉回路存在性判定（每个顶点度数均为偶数且连通），并实现 Hierholzer 算法。
2. 说明哈密顿回路判定为何没有已知高效算法，掌握回溯搜索与 Dirac 条件两类工具。
3. 用欧拉公式（顶点减边加面等于二）推出平面图的边数上界与平均度上界。
4. 说明平面性与子图细分的关系（判定原理），以及对偶图的概念。
5. 解释随机图的两种经典模型与"涌现阈值"现象，复现巨型分量的诞生曲线。
6. 描述小世界现象的度量（高聚类、短路径），并说明它与规则图、随机图的位置关系。

核心概念速览

金句：图类的"户籍"比"国籍"诚实——欧拉图看度数的奇偶，哈密顿图却至今没有一张人人通行的身份证。

子章节导航

第 1 节"欧拉图与哈密顿图：一笔画与全程巡视"回到全册的起点哥尼斯堡，把七桥问题的解法升格为完整判定定理与构造算法；紧接着的哈密顿问题形似神异——一问每边、一问每点，难度却是天壤。两问并置最能体现"问题定义的细微改动如何翻转复杂度"。

第 2 节"平面图：不交叉的行军地图"处理能画在平面上而边互不交叉的图。欧拉公式把顶点、边、面连成恒等式，一连串紧约束（边数上界、平均度上界、必含低度顶点）由此倾泻而出，五色定理的优雅证明也在此展开。

第 3 节"随机图与小世界：地图之外的疆域"换一种提问方式：不设计图，而是规定概率规则让图自己生长。平均边数的缓慢爬升会突然引爆出横贯全图的巨型分量——相变与涌现是本节的关键词，小世界现象则架起通向网络科学专题册的桥。

三节之间的档案逻辑

一句话论点：欧拉问"边"、哈密顿问"点"、平面问"面"、随机问"概率"——四问各执一个维度，合起来是图论结构观的完整版图。

   第1节 边与点的两极
   欧拉图：偶度 ⇔ 一笔画（易判定易构造）
   哈密顿图：无通用快判（难解家族成员）
        │
   第2节 面的约束
   平面图：欧拉公式 → 边数与度的紧上界 → 稀疏是宿命
        │
   第3节 概率的疆域
   随机图：相变涌现巨型分量
   小世界：规则与随机的折衷 → 网络科学（另册展开）
​

前置知识与后续延伸

前置：第 1 章的七桥问题与图类词汇（本章直接回收开篇伏笔）、第 3 章的遍历步法（Hierholzer 算法以深度优先为骨架）、第 8 章着色的五色四色背景（平面图一节回收伏笔）。

后续延伸：随机图与小世界是站内网络科学专题册的入口，本册只在数学层面点到即止并指路；欧拉路径在 DNA 测序的碎片拼接、平面性在电路布线与地图制图中都是生产级工具，第 10 章实战检阅再会。哈密顿问题作为旅行商问题的特例，其难度将延伸到运筹与近似算法的领域。