第1章 远征起点：从七座桥出发

第 1 章 · 远征起点：从七座桥出发

章节摘要：任何一支远征队出发前都要先学会读地图。本章从哥尼斯堡的散步难题讲起，看欧拉如何把陆地与桥梁抽象成顶点与边，从而开创图论；随后清点远征地图的基本要素——顶点、边、度、子图与路径；最后巡视图的整个家族，认识简单图、多重图、完全图、二分图这些在后续战役中反复露面的编制单位。读完本章，你应当能用统一的语言描述任何"连接问题"。

学习目标

阅读完本章，你应当能够：

1. 复述七桥问题的抽象过程，说清"把问题化成图"这一步为什么比求解本身更关键。
2. 给出图的形式化定义，区分有向图与无向图、加权图与无权图。
3. 计算任意顶点的度，在有向图中区分入度与出度，并用握手定理校验数据。
4. 列举至少五种特殊图类（完全图、二分图、树、多重图、DAG）及其判别特征。
5. 用 Python 与 networkx 构造上述各类图并读取基本属性。

核心概念速览

金句：抽象不是删减细节，而是把无关的细节从问题里请出去。

子章节导航

第 1 节"七桥问题：一支远征队的诞生"回到历史现场，完整重演欧拉的论证——为什么所有陆地度数均为偶数是回路存在的必要条件。这一节建立的全册方法论：先抽象，再推理，最后才谈计算。

第 2 节"顶点、边与度：远征地图的基本要素"把地图语言系统化，定义度、邻居、通路、回路、连通、子图，并证明握手定理。它是后面每一章都要调用的词汇表。

第 3 节"图的家族图谱：常见图类型巡礼"像点验编制一样巡视各类特殊图：完全图、二分图、树、森林、多重图、有向无环图。后续章节的算法都建立在这些特定地形上——例如二分图匹配（第 7 章）、拓扑排序（第 6 章）。

子章节之间的逻辑关系

一句话论点：历史故事给动机，形式语言给精度，图类盘点给地形——三者合起来，远征队才算"识字"。

第1节 七桥抽象(动机) ──→ 第2节 形式要素(语言) ──→ 第3节 图类家族(地形)
      │                        │                        │
      └── 提供"为何抽象" ────────┴── 提供"怎么描述" ───────┴── 提供"在哪作战"
                                                        ↓
                                          第2章起：把地图存进计算机
​

前置知识与后续延伸

前置：初中代数（集合与计数的基本直觉）、Python 基础语法。不需要离散数学基础，涉及的地方随讲随补。

后续延伸：本章只解决"图是什么"，尚未回答"图在计算机里长什么样"——这正是第 2 章（表示与存储）的入口；而度与连通这些词汇，会在第 4 章（连通性勘定）与第 9 章（欧拉图判定）被反复征用。

学习建议与常见误区

啃本章时最容易绊倒的地方有三处，提前打预防针。其一，把"图"与"图形"混为一谈：图论里的图只关心顶点、边与连接关系，顶点画在纸上哪里、边画成直线还是弧线，全都无关紧要——两幅看起来完全不同的图，只要连接关系一致就是同一个图，这点在第 9 章平面图一节还会反过来讨论（什么时候连接关系允许"画得不交叉"）。其二，忽视定义里的"无序对与有序对"：无向边是两顶点的无序对，有向边是有序对，一字之差决定了整册算法的行为差异，第 4 章强连通、第 6 章拓扑排序都要回头看这条分界。其三，学概念不动手：每节的 networkx 代码建议逐行敲一遍，用代码打印出的度数、边数去对照握手定理的等式，手感远比背诵牢固。读完本章的自测标准很简单——随便拿一个身边的连接问题（地铁线路、好友关系、课程先修），你能不假思索地说出顶点是什么、边是什么、有没有方向、有没有权重，远征的第一步就算迈稳了。