图论基础 — 顶点、边与结构
图论是研究"顶点"和"边"之间关系的数学分支，从七桥问题到社交网络分析，无处不在。
一、图的定义
先看一个问题
问题：有 4 个城市 A、B、C、D，它们之间的直达航线如下：A↔B、A↔C、B↔D、C↔D。如何用数学方式来描述这个交通网络？
思考：我们把每个城市看作一个点，把每条直达航线看作连接两个点的线。这样就形成了图论中最基础的结构——一个图。
图的定义
一个图 G 定义为一个有序对 G = (V, E)，其中：
- V（Vertex Set）：顶点集，图中的所有顶点（也叫节点）的集合。
- E（Edge Set）：边集，连接顶点的所有边的集合。
G = (V, E) V 是顶点集，E 是边集
例：上面城市航线的例子中，V = {A, B, C, D}，E = {AB, AC, BD, CD}。
无向图与有向图
- 无向图（Undirected Graph）：边没有方向。边 AB 和 BA 表示同一条边，即 A 和 B 之间是双向连接。
- 有向图（Directed Graph / Digraph）：边有方向。用箭头表示，从起点指向终点，记作 A→B。
例：社交网络中的"好友关系"是无向图（A 是 B 的好友 = B 是 A 的好友）；而"关注关系"是有向图（A 关注 B 并不意味着 B 关注 A）。
简单图与完全图
- 简单图（Simple Graph）：没有重边（两条顶点间最多一条边），也没有自环（顶点不能有边连向自己）。
- 完全图 Kn（Complete Graph）：任意两个不同顶点之间都有且仅有一条边的简单图，记作 Kn。Kn 的边数为 C(n, 2) = n(n−1)/2。
边数公式：完全图 Kn 的边数为
|E| = C(n, 2) = n(n − 1) / 2
二、度数
先看一个问题
问题：在一个有 5 位同学的群聊中，如果每两个人之间恰好发过一次私信，那么总共发了多少条私信？所有同学收发私信的总次数是多少？
思考：把每位同学看作顶点，一次私信看作连接两个顶点的一条边。5 个顶点两两相连，就是完全图 K₅，共有 C(5,2) = 10 条边（10 条私信）。
每位同学与另外 4 位都发过私信，所以每位同学的"度数"是 4。所有同学的度数之和 = 5 × 4 = 20，恰好等于边数 10 的两倍。
顶点的度数
在无向图中，一个顶点的度数（degree）是指与该顶点关联的边的数目，记作 d(v)。
若图含有自环，按约定一条自环对该顶点的度数贡献 2。
握手引理（Handshaking Lemma）：在任何无向图中，所有顶点的度数之和等于边数的两倍。
∑v∈V d(v) = 2 × |E|
例：下图是一个有 5 个顶点的图，计算各顶点的度数和总边数。
d(v₁) = 2（连 v₂ 和 v₃）
d(v₂) = 3（连 v₁、v₄、v₅）
d(v₃) = 2（连 v₁、v₄）
d(v₄) = 3（连 v₂、v₃、v₅）
d(v₅) = 2（连 v₂、v₄）
度数之和 = 2 + 3 + 2 + 3 + 2 = 12，边数 = 6，验证：12 = 2 × 6 ✓
三、路径与连通
基本概念
- 途径（Walk）：一个顶点序列 v₁, v₂, ..., vk，其中相邻顶点之间都有边连接；顶点和边都可以重复。
- 边迹（Trail）：不重复经过边的途径，顶点可以重复。欧拉通路属于边迹。
- 路径（Path）：顶点互不相同的途径。路径的长度是其中边的数目。
- 回路（Cycle）：首尾顶点相同、除首尾外其他顶点互不相同的闭合途径。
- 连通图（Connected Graph）：图中任意两个顶点之间都存在一条路径。
例：在下图中，从 v₁ 到 v₄ 有一条路径：v₁ → v₂ → v₃ → v₄（长度为 3）。图中还有一个回路：v₁ → v₂ → v₃ → v₁（长度为 3 的三角形回路）。
连通分量：非连通图可以分成若干个连通的"部分"，每个部分称为一个连通分量。右图有两个连通分量：{a, b, c} 和 {d}。
例：社交网络中，"朋友圈"就是连通分量——一个朋友圈内的人可以通过好友关系链相互联系，而不同朋友圈之间则没有联系。
四、树
先看一个问题
问题：一个公司有 6 个部门，需要铺设网络线缆将它们连接起来。要求任意两个部门之间都能通信（直接或间接），先忽略各条线缆长度的差异，最少需要多少条线缆？
思考：如果 6 个部门两两相连，需要 C(6,2) = 15 条线缆，但很多是多余的。实际上，我们只需要 5 条线缆，将它们连接成一种特殊的图——树。
树的定义
树（Tree）：一个连通且无回路的无向图称为树。树是最简单的连通图结构——用最少的边保持连通。
树的重要性质：一棵有 n 个顶点的树，恰好有 n − 1 条边。
树：|V| = n ⇒ |E| = n − 1
例：一棵有 7 个顶点的树，必然有 6 条边。下面是一棵树的结构：
生成树
给定一个连通图 G，如果 G 的某个子图 T 是树，且包含 G 的所有顶点，则称 T 是 G 的一个生成树（Spanning Tree）。
例：一个连通图通常有多个不同的生成树。找生成树就是在图中"剪掉"多余的边，保留下 n−1 条边使之不再有回路。
五、欧拉图
七桥问题——图论的起源
问题（哥尼斯堡七桥）：18 世纪的哥尼斯堡城中有七座桥，连接着两座岛和两岸。问题是：能否从某处出发，恰好每座桥走一次且不重复，最后回到起点？
1736 年，欧拉（Euler）用图论的方法证明：这是不可能的。这个问题的解决标志着图论的诞生。
七桥模型允许同一对顶点之间有多条边，因此它是多重图；边的重复表示不同的桥。
欧拉图的概念
- 欧拉通路（Eulerian Trail）：经过图中每条边恰好一次的边迹；允许在途中重复经过顶点，但不能重复经过边。
- 欧拉回路（Eulerian Circuit）：经过图中每条边恰好一次且回到起点的闭边迹。
- 欧拉图（Eulerian Graph）：具有欧拉回路的图。
欧拉定理：对于一个连通图（更一般地，忽略孤立顶点后连通的图），
图有欧拉回路 ⇔ 所有顶点的度数都是偶数
图有欧拉通路（但不是回路） ⇔ 恰好有两个顶点的度数为奇数
例：七桥问题中四个顶点的度数分别为 3、5、3、3，全是奇数，所以既没有欧拉回路也没有欧拉通路——不可能不重复地走完所有桥。
六、二分图
先看一个问题
问题：有 3 名工人和 4 项任务，每名工人只能做其中的某些任务。如何用图来表示这种"谁可以做哪项任务"的关系？
思考：我们把工人放在一边，任务放在另一边，如果工人能做某项任务，就连一条边。这样得到的图，顶点天然被分成了两组——二分图。
二分图的定义
二分图（Bipartite Graph）：一个图的顶点集 V 可以分成两个不相交的非空子集 U 和 W，使得每一条边都连接 U 中的一个顶点和 W 中的一个顶点（即边不连接同一子集内的顶点）。
判定定理
二分图判定定理：一个图是二分图当且仅当它不含奇环（即回路的长度为奇数）。
例：正方形（4 个顶点回路）是二分图，但三角形（3 个顶点回路）不是。任何树都是二分图（因为树没有回路）。
染色法判定：给每个顶点染两种颜色之一，要求相邻顶点颜色不同。如果能完成染色，就是二分图。三角形无法用两种颜色给三个顶点正确染色（因为每两两相邻），所以不是二分图。
七、染色原理
先看一个问题
问题：在一张地图上给各个区域涂色，要求相邻区域（有共同边界）的颜色不同。最少需要几种颜色？
思考：我们把每个区域看作一个顶点，相邻区域之间连一条边。问题就变成了：给图的每个顶点涂色，使得相邻顶点颜色不同。最少需要的颜色数就是图的色数。
图的顶点染色问题
图的顶点染色（Vertex Coloring）：给图的每个顶点分配一种颜色，使得任意两个相邻顶点颜色不同。
色数 χ(G)（Chromatic Number）：给图 G 染色所需的最少颜色种数。
四色定理（Four Color Theorem）：任何平面地图都可以用最多 4 种颜色给区域染色，使共享一段边界的区域颜色不同（只在一点接触不算相邻）。等价地，任何平面图的顶点都可以用至多 4 种颜色正常染色。
这是数学史上著名的定理——1852 年提出，直到 1976 年才首次由计算机辅助证明，也是第一个借助计算机证明的重要数学定理。
例：计算以下图的色数。
图中 A、B、D 两两相连（形成一个三角形），因此至少需要 3 种颜色（A=红, B=蓝, D=绿）。
3 种颜色可以完成整张图的染色：例如 A=橙、B=蓝、D=绿；C=绿（与 D 不相邻），E=橙（与 A 不相邻）。
所以色数 χ(G) = 3。
| 图的结构 | 色数 | 说明 |
|---|---|---|
| 空图（无边） | 1 | 所有顶点可涂同色 |
| 二分图（含边） | 2 | 两部分各涂一色；无边图的色数为 1 |
| 奇环（如 C₅） | 3 | 奇数长度回路需要 3 色 |
| 完全图 Kn | n | 每个顶点必须颜色不同 |
| 平面图 | ≤ 4 | 四色定理保证 |