图论：点和线的学问
【章首引子】你打开手机地图查最短路线——它不是瞎试所有路，而是从起点一步步往外扩。这个"一步步往外扩"就是 Dijkstra 算法。点是地点、边是道路，整张地图就是一张图。导航、社交六度、课程依赖，全是图论。
① 是什么：节点、边、特殊图
啥图论基本概念
图：点（节点）+ 线（边）。点代表人/地点/网页，线代表关系/道路/链接。度：一个点连了几条边。握手定理：所有点度数之和 = 边数的 2 倍（每条边贡献 2 度）。
特殊图：树（连通无回路，n 点 n−1 边）、二分图（点分两组，边只在组间）、欧拉图（能一笔画完）、哈密顿图（每点走一次）。
② 怎么想到的
思解题心法
一笔画：奇度点必须是 0 或 2 个，否则至少两笔。
最短路径 Dijkstra：从起点每次挑"目前已知最近"的点扩展。
最小生成树：Prim/Kruskal，把所有点连起来用最少边。
③ 完整解法：三个例题
证图论：点和线的学问的核心定理与公式
推导思路：①任取一条边 $e=uv$，它连接两个端点，于是它对 $u$ 的度数贡献 $1$，对 $v$ 的度数也贡献 $1$。②把所有顶点的度数加起来，等价于"逐条边去数：这条边在它的两个端点处各被算了几次"。③每条边恰好被数到 $2$ 次（两个端点各一次），所以总和 $\sum_v\deg(v)=2|E|$，必为偶数。④把顶点按度数奇偶分成两组：偶度顶点之和当然是偶数，而总和 $2|E|$ 也是偶数，两者相减可知奇度顶点之和为偶数；奇数个奇数相加才是奇数，故奇度顶点必有偶数个。
直觉把握：握手定理说：聚会上所有人"握过多少次手"加在一起，一定是偶数——因为每一次握手都同时被两个人各记了一次。AI/工程里，图神经网络的消息传递本质就是邻接矩阵乘法；知识图谱、推荐系统的用户-物品二部图、依存句法树，全都是图；PageRank 是在图上做随机游走求稳态分布；而 Transformer 的自注意力，其实就是在一个全连接图上做一轮消息传递。
④ 用途与案例
地图导航
点是地点、边是道路带距离，Dijkstra 算最短路线——手机地图的核心。
社交六度
社交关系是巨大图，任意两人平均隔 6 层。推荐系统用二分图匹配。
网络布线
把所有机房连起来用最少光纤 = 最小生成树。
课程依赖
先修课关系是有向图，拓扑排序排课表——不能让你先学数据结构再学编程。
⑤ 延展
展知识衔接地图
往研究生走：图论 → 代数拓扑/网络科学（图同调、复杂网络）。往算法走：图神经网络 GNN 是当下 AI 热点，把邻居信息聚合到节点上。
把"图论的图"当成"函数图像"。完全两码事！图论的图是点边网络（地铁图、社交图），不是坐标系里的曲线。看到"图"字先想清楚哪个图。
练习
【基础】树有 10 个节点，几条边？
查看思路与解答
n−1 = 9 条边。【进阶】一个图 6 个点，每点度 2，它是什么图？
查看思路与解答
总度数 12 = 2×边数 → 6 条边。6 个点 6 条边、每点度 2，且连通——一个 6 环（单回路）。① 图 = 点+边描述一切关系；导航=最短路径、推荐=二分图匹配、一笔画=奇度点≤2。
② 树 = n 点 n−1 边无回路；握手定理 Σdeg=2|E|。