图论
“图是一张抛开位置、只保留连接的地图。”
公式
G = (V, E), Σ(v∈V) deg(v) = 2|E|怎么读: 一个图由顶点集 V 和连接它们的边集 E 组成；把每个顶点的度相加，等于边数的两倍
- V
- — 顶点集——「点」的集合
- E
- — 边集——连接点的「线」的集合
- deg(v)
- — v 的度——与它相连的边数
- Σdeg(v) = 2|E|
- — 度数之和等于边数的两倍（握手引理）
引子
友谊关系、地铁线路图、互联网、分子结构——它们全都可以用同一幅简单的图景来表示：点与线。
通俗地说
图是由点（顶点）和连接它们的线（边）组成的集合。它只记录「谁和谁相连」，抛开了位置、形状和距离。这是一张被剥离到只剩骨架的关系地图。
直觉
想象一张地铁线路图——真实的距离和方向都是错的，但「哪一站连着哪一站」被完整保留了下来。这正是图的精神所在。无论点代表的是人、城市还是网页，无论线代表的是友谊、道路还是链接，只看连接的结构，就能让截然不同的问题变成同一个问题。
如何构建
两部分——顶点集 V 和边集 E。每个顶点的「度」是与它相连的边数。握手引理：把所有顶点的度加起来，恰好是边数的两倍（每条边在它的两个端点各被计一次）。这个简单的计数出人意料地强大。
示例
一个三角形图：3 个顶点，3 条边。每个顶点的度都是 2，所以度数之和是 2+2+2 = 6 = 2 × 3（边数）。握手引理精确成立。
常见误区
这里的「图」不是函数 y=f(x) 的曲线。这里没有坐标轴，也没有曲线——只有由点和连接它们的线组成的网络。同一个词，完全不同的对象。
用在哪里
谷歌的搜索排名（PageRank）、GPS 最短路径、社交网络分析、电路设计、调度与着色问题、疫情传播模型——凡是「事物之间彼此相连」的问题，都是图。
从何而来
1736 年，欧拉解决了「能否不重复地一次走遍哥尼斯堡七座桥」这个谜题，开启了图论与拓扑学的大门（答案是：不可能）。
前置概念
小测验
根据握手引理，一个有 5 条边的图，所有顶点度数之和是多少？
- 5
- 10✓
- 25
- 2.5
练习
求一个有 4 条边的图中，所有顶点度数之和。
答案: 8
- 握手引理：度数之和 = 2 × 边数
- = 2 × 4 = 8
要点: 每条边给总度数贡献 2。
求完全图 K₄（4 个顶点，两两相连）的边数。
答案: 6
- 从 4 个顶点中选 2 个的方法数，C(4,2)
- = (4·3)/2 = 6
要点: 完全图 Kₙ 有 n(n−1)/2 条边。
一个图的顶点度数是 3、3、2、2。求它的边数。
答案: 5
- 度数之和 = 3+3+2+2 = 10
- 边数 = 10 / 2 = 5
要点: 边数是度数之和的一半。
用度数来解释，为什么没有一条路径能恰好一次走遍哥尼斯堡的七座桥。
答案: undefined
- 这样的路径（欧拉路径）需要有 0 个或 2 个奇度顶点
- 在哥尼斯堡，全部四块陆地的度数都是奇数
- 四个奇度顶点（超过 2 个）使这条路径不可能存在
要点: 有三个或更多奇度顶点，就不存在欧拉路径。