Graphs and Networks

欢迎来到图论与网络的世界！

在本章中，我们将暂时放下大家从中学（GCSE）以来熟悉的 \(y = f(x)\) 函数图表。取而代之的是，我们将以图（Graphs）作为模拟现实世界的工具。试想一下地铁路线图、社交媒体上的好友圈，或是手机内部的电路板——这些全都是网络！我们利用离散数学（Discrete Mathematics）来研究事物之间如何连接、如何寻找最佳路径，以及如何将复杂的系统简单化。如果起初觉得有很多新术语，别担心；一旦你掌握了当中的规律，你会发现这其实是进阶数学（Further Maths）中最具视觉感且逻辑分明的一部分。

1. 基础积木：术语与符号

在解决复杂问题之前，我们需要一套共同语言。一个“图”本质上就是由“点”与“线”组成的集合。

关键术语：

• 顶点（Vertex 或 Node）：图中的“点”。它们代表实体（如城市、人或电脑）。复数形式为 vertices。
• 弧（Arc 或 Edge）：连接顶点的“线”。它们代表实体之间的关系或路线。
• 顶点的度数（Degree 或 Valency）：连接在该顶点上的弧的数量。你可以把它想像成这个顶点有多少个“朋友”。
• 关联（Incident）：如果一条弧物理上连接到一个顶点，我们称这条弧与该顶点“关联”。
• 邻接（Adjacent）：如果两个顶点之间有弧直接相连，则称这两个顶点“邻接”。同样地，如果两条弧共用一个顶点，则称它们“邻接”。

小贴士：在任何图中，所有顶点的度数之和永远等于弧数量的两倍。这是因为每一条弧都有两个端点！这通常被称为握手引理（Handshaking Lemma）。

重点总结：顶点是“位置”，而弧是“连接方式”。

2. 描述图的特性

并非所有的图都长得一样。我们使用特定的名称来描述它们的“连接程度”或“复杂性”。

图的种类：

• 简单图（Simple Graph）：没有自环（loop）（即起点和终点在同一个顶点的弧）且没有多重弧（multiple arcs）（即两个顶点之间有多于一条弧）的图。
• 连通图（Connected Graph）：你可以通过路径从任何一个顶点到达其他任何一个顶点。图中没有“与世隔绝”的孤岛。
• 简单连通（Simply Connected）：在离散数学中，这通常指一个连通且没有圈（cycle）的图（例如树状图）。
• 树（Tree）：一个连通且没有圈的图。类比：就像家谱一样，没有任何“环”让你绕回起点。

你知道吗？一个有 \(n\) 个顶点的树，必定刚好有 \(n - 1\) 条弧。如果你再加一条弧，就会构成一个圈！

3. 路径、轨迹与圈

我们如何在图中移动？课程大纲区分了几种不同的“旅程”。如果觉得容易混淆也不用担心，只要记住移动的“层次”即可：

• 行走（Walk）：最基础的移动方式。你可以重复经过任何顶点或弧。
• 轨迹（Trail）：一种不会重复使用弧的行走。（但你可以多次经过同一个顶点！）
• 路径（Path）：最“严格”的路线。一种不会重复经过顶点的轨迹。
• 圈（Cycle）：一个“封闭的路径”。从某个顶点出发，最后回到该顶点，过程中不重复经过任何其他顶点或弧。
• 路线（Route）：一个通用术语，可以指上述任何一种情况。

常见错误：学生经常混淆路径（Path）与轨迹（Trail）。请记住：Path（路径）= 不重复 People（顶点/人）；Trail（轨迹）= 不重复 Tracks（弧/轨迹）。

4. 特殊图族

有些图具有非常具体的结构，我们将其作为离散数学中的基准。

完全图（Complete Graphs，\(K_n\)）

这是一种每一个顶点都与其他所有顶点相连的图。我们用 \(K_n\) 来表示，其中 \(n\) 为顶点数量。

重要公式：完全图 \(K_n\) 中的弧数量为： \( \frac{1}{2}n(n-1) \)。

二分图（Bipartite Graphs，\(K_{m,n}\)）

在二分图中，顶点被分成两个独立的集合。弧只连接一个集合中的顶点与另一个集合中的顶点，同一集合内的顶点之间没有连接。

• 完全二分图（Complete Bipartite Graph，\(K_{m,n}\)）：第一个集合（大小为 \(m\)）中的每个顶点都与第二个集合（大小为 \(n\)）中的每个顶点相连。
• 弧的数量：对于 \(K_{m,n}\)，弧的数量简单地等于 \( m \times n \)。

快速检视：如何证明一个图是二分图？试试染色法（Colouring Argument）。如果你能将每个顶点涂上红色或蓝色，使得没有两个相同颜色的顶点相连，那么这个图就是二分图！

5. 可遍历性：欧拉图与哈密顿图

这是考试中的经典考点，主要问的是：“我们可以一次过走完所有东西吗？”

欧拉图（侧重于“弧”）

欧拉图（Eulerian graph）是指能够找到一条路径，能够遍历每一条弧且仅限一次，并回到起点的图。

• 欧拉图：所有顶点的度数均为偶数。
• 半欧拉图（Semi-Eulerian）：恰好有两个顶点的度数为奇数。你可以遍历所有弧，但必须从其中一个奇数度顶点出发，并在另一个奇数度顶点结束。

哈密顿图（侧重于“顶点”）

哈密顿圈（Hamiltonian Cycle）是一个能够恰好经过每个顶点一次（并回到起点）的圈。

• 奥尔定理（Ore's Theorem）：对于一个有 \(n \ge 3\) 个顶点的简单图，如果对于每一对不邻接的顶点 \(v\) 和 \(w\)，都有 \( \text{deg } v + \text{deg } w \ge n \)，则该图是哈密顿图。
• 注意：奥尔定理是哈密顿图的充分条件，但不是必要条件。如果条件不满足，该图仍然可能是哈密顿图！

重点总结：欧拉图看“弧”。哈密顿图看“顶点”。

6. 有向图与同构

有向图（Digraphs）

在有向图中，弧是有箭头的！它们是单行道。我们不再只用“度”，而是使用：

• 入度（Indegree）：指向该顶点的弧的数量。
• 出度（Outdegree）：从该顶点向外指出的弧的数量。

同构（Isomorphism）

如果两个图在结构上本质相同，即使画法不同，我们也称它们为同构。它们必须拥有相同数量的顶点、相同数量的弧，以及相同的度数序列（按顺序排列的度数列表）。

警告：拥有相同的度数序列是同构的必要条件，但不是充分条件。你必须检查实际的连接方式是否完全相同！

7. 平面图：保持平面

如果一个图可以画出来而没有任何弧交叉，则该图是平面图（planar）。

关键概念：

• 细分（Subdivision）：在现有的弧上增加一个度数为 2 的新顶点（就像在绳子上加一颗珠子）。
• 收缩（Contraction）：将一条弧缩短，直到两端的顶点合并为一个。
• 欧拉公式（Euler’s Formula）：对于任何连通平面图： \( V + R = E + 2 \)，其中 \(V\) 是顶点，\(R\) 是区域（包括图外无限大的区域），\(E\) 是边（弧）。
• 库拉托夫斯基定理（Kuratowski's Theorem）：一个图是平面图的充要条件是它不包含任何 \(K_5\) 或 \(K_{3,3}\) 的细分图。（这两个就是“禁忌”的非平面图形！）
• 厚度（Thickness）：“覆盖”一个非平面图的所有边所需的最少平面图数量。（在你的课程中，我们主要探讨厚度为 1 或 2 的情况）。

8. 网络与矩阵

网络其实就是弧具有权重（weights）（代表距离、成本或时间的数值）的图。

以数值表示图：

• 邻接矩阵（Adjacency Matrix）：一个表，行和列代表顶点。数字 '1' 表示它们相连；'0' 表示不相连。对于有向图，这还能显示方向。
• 权重矩阵（Weighted Matrix）：类似于邻接矩阵，但我们不写 '1'，而是写出弧的权重。如果没有连接，我们通常用短横线（\(-\)）或无穷大符号（\(\infty\)）表示。

快速复习箱：
- 顶点：点。
- 弧：线。
- 树：没有圈。
- 欧拉图：每条边只走一次（度数皆为偶数）。
- 哈密顿图：每个顶点只走一次。
- 欧拉公式： \( V + R = E + 2 \)。

最后的鼓励

离散数学往往需要你多与图表“互动”。如果某个概念感觉很抽象，试着把它画出来！在二分图上使用不同颜色，或者用手指在欧拉轨迹上比划。你一定可以做到的！