欢迎来到网络世界！

你好！欢迎来到进阶数学（Further Mathematics）中最实用且直观的章节之一：网络 (Networks)。本章属于运算建模 (Modelling with Algorithms) 的一部分。你将学习如何将现实生活中的问题——例如寻找回家的最快路线或管理管道中的水流——转化为图表，并透过逻辑步骤（即算法）来解决。

如果起初觉得有点抽象，别担心。你可以将网络想像成一张地图，我们剔除了不必要的细节，只专注于连接 (connections) 和成本 (costs)。让我们开始吧！

1. 图论的语言

在我们解决问题之前，必须先学会当中的“语言”。在数学中，“图”(graph) 并不是指带有 x 轴的图表，而是一组点与线的集合。

关键术语

  • 节点 (Node 或 Vertex)： 图表中的“点”。它们通常代表地点（如城市或电脑服务器）。
  • 弧 (Arc 或 Edge)： 连接节点的“线”。它们代表节点之间的路径。
  • 节点的阶 (Order 或 Degree)： 连接到该特定节点的弧的数量。
  • 树 (Tree)： 一个没有回路 (cycles) 的连通图。可以想像成家谱——没有任何路径会绕成一个圆圈！
  • 有向图 (Digraph)： “Directed Graph”的简称。在这种图中，弧具有方向箭头，表示你只能沿特定方向移动。

图的特殊类型

  • 简单图 (Simple Graph)： 没有环（连接节点到自身的弧），且同一对节点之间没有多条弧。
  • 完全图 (Complete Graph)： 每一个节点都与其他所有节点相连。
  • 连通图 (Connected Graph)： 你可以沿着弧从任何一个节点到达其他任何节点。
  • 二分图 (Bipartite Graph)： 节点被分成两组，弧只连接不同组中的节点。类比：想像一张“工人”清单和一张“工作”清单。你只会在工人与工作之间连线，绝不会在两个工人之间连线。

关联矩阵 (Incidence Matrix)

有时候，绘制图表会很混乱。关联矩阵是一个表格，显示哪些节点由哪些弧连接。这是让电脑在没有图形的情况下“看见”图表的一种方式。

重点小结： 节点是“在哪里”，弧是“怎么走”，而树是一种没有圆圈的简单路径。

2. 权重与网络

在现实世界中，并非所有路径都是平等的。有些道路较长，有些管道较宽。

网络 (Network) 其实就是一个每个弧都被赋予权重 (weight)（一个数值）的图。这些权重可以代表距离、时间、成本或容量。

你知道吗？ 每当你要求导航寻找“最快路线”时，你的 GPS 就在使用权重网络。而权重就是每条道路的预估行车时间！

3. 最小连接问题

想像你正在铺设光纤电缆以连接五个村庄。你希望每个人都能连接起来，但电缆很昂贵，所以你想要总长度最小。这就是最小生成树 (Minimum Spanning Tree, MST)。

克鲁斯克尔算法 (Kruskal’s Algorithm，即“贪婪”策略)

Kruskal’s 算法很简单：永远选择当下最便宜的选项！

  1. 将网络中所有的弧按权重从小到大排序。
  2. 选择权重最小的弧并将其添加到树中。
  3. 选择下一个最小的弧。关键规则： 如果选定的弧会构成回路 (cycle)（封闭回圈），则不能选择它。
  4. 重复上述步骤，直到所有节点都已连通。

普林算法 (Prim’s Algorithm，即“扩张”策略)

Prim’s 算法像植物生长根系一样，每次增加一个节点来构建树。

  1. 从任何一个节点开始（通常题目会指定）。
  2. 查看所有与你已到达的节点相连的弧。
  3. 选择连接到一个新节点且权重最小的弧。
  4. 重复此步骤，直到每个节点都包含在树中。

记忆小撇步：Prim’s 从 Point（点）开始；Kruskal’s 从弧的 Kosts（成本/权重）开始。

重点小结： 两种算法都会给你相同的最小总权重。Kruskal’s 会检视整个弧列表；Prim’s 则是从起始节点向外扩张。

4. 戴克斯特拉算法 (Dijkstra’s Algorithm，最短路径)

这用于寻找从特定起点到终点的最短路径。与 MST 不同，我们只在乎距离起点有多远。

逻辑步骤：

  1. 设定起始节点的距离为 0，所有其他节点的距离为“无限大”。
  2. 从当前节点出发，更新到所有相邻节点的距离。（新距离 = 到当前节点的距离 + 弧的权重）。
  3. 如果新计算的距离比旧的短，就记下来！
  4. 一旦检查完所有邻居，将当前节点标记为“已访问”。以后不再回到该节点。
  5. 选择未访问且具有最小暂时距离的节点，将其设为新的当前节点。
  6. 重复此过程，直到到达终点。

常见错误： 学生经常选择权重最小的那个弧。请记住，Dijkstra’s 关注的是从起点开始的总距离，而不仅仅是下一步的距离！

5. 算法复杂度

在进阶数学 (MEI) 中，我们关心电脑处理问题的“难度”，这称为复杂度 (Complexity)。

  • Kruskal’s 与 Prim’s： 具有二次复杂度 (quadratic complexity)，记作 \(O(n^2)\)，其中 \(n\) 是边的数量。
  • Dijkstra’s： 同样具有二次复杂度 \(O(n^2)\)，但它是关于顶点 (vertices) 数量的函数。

什么是 \(O(n^2)\)？ 如果网络规模翻倍 (\(2n\))，解决问题所需的时间大约会变成原来的四倍 (\(2^2 = 4\))。

6. 网络流 (Network Flows)

现在，想像弧是管道，权重是容量 (capacities)（流过其中的水或数据的最大总量）。

源头与汇点

  • 源点 (Source, S)： 流动开始的地方。
  • 汇点 (Sink, T)： 流动结束的地方。
  • 规则： 对于其他任何节点，流入量必须等于流出量。（中间不会有东西卡住！）

截集与容量

截集 (Cut) 是一条能将源点与汇点完全分开的线。截集的容量是所有从 S 侧流向 T 侧的弧的容量总和。

注意： 如果一条弧从 T 侧流回 S 侧，我们在计算截集值时会忽略它的容量（即视为 0）。

最大流/最小截集定理 (Max Flow / Min Cut Theorem)

这是网络中的“黄金法则”：网络中的最大可能流量等于最小截集的容量。

如果你找到一个流量为 20 的流，且同时找到一个容量为 20 的截集，你就证明了 20 就是绝对的最大流量！

重点小结： 最大流量受到系统中“瓶颈”（即最小截集）的限制。

7. 使用科技解决网络问题

在现实世界中，网络拥有成千上万个节点。我们透过将其转化为线性规划 (Linear Programming, LP) 问题来解决。

对于最短路径问题，我们通常会设立方程，其中：

  • 目标是最小化 (Minimise) 总距离。
  • 变量代表弧是否被使用（1 代表使用，0 代表不使用）。
  • 约束条件确保我们正确地进入和离开节点。

不用担心要亲手解这些复杂方程；课程大纲重点在于你能否构建 (formulate) 方程，以及解释 (interpret) Excel 或 Simplex 解算器等软件输出的结果。

最后的鼓励

网络问题就像拼图。一旦你掌握了 Dijkstra’s 或 Prim’s 的“节奏”，解题会变得非常有成就感。务必清楚绘制图表、反复检查加法，并记住：算法不过是数学的食谱罢了！