Networks

欢迎来到网络的世界！

你好！在本章中，我们将探索网络 (Networks)，这是算法建模 (Modelling with Algorithms) 单元的核心部分。你可能每天都在使用网络却不自知——每当使用 GPS 寻找回家的最快路径，或是快递公司规划如何将包裹送到你手中时，他们所使用的正是我们即将学习的算法。如果一开始觉得这些概念有点抽象也不用担心，我们会把它们拆解成简单的步骤，并与日常生活联系起来！

1. 图论与网络的语言

在我们解决问题之前，必须先学会当中的“语言”。图 (Graph) 只是一组点和线的集合。当我们为这些线加上“权重”（例如距离或成本）时，它就成了网络 (Network)。

你需要知道的关键术语：

• 节点 (Node 或 Vertex)： 图上的点，通常代表一个位置（例如城市）。
• 弧 (Arc 或 Edge)： 连接两个节点的线，代表路径或链接。
• 权重 (Weight)： 分配给弧的数值，代表成本、时间或距离。
• 节点的阶 (Order 或 Degree)： 连接到该节点的弧的数量。
• 简单图 (Simple Graph)： 没有环（即没有连接节点自身的弧），且两个节点之间没有多条弧的图。
• 连通图 (Connected Graph)： 可以通过弧从任何一个节点到达另一个节点。
• 二分图 (Bipartite Graph)： 一种图，其节点被分为两个集合，且弧只连接不同集合中的节点（可以想象成“工人”和“工作”）。
• 有向图 (Digraph)： “Directed Graph”的简称——弧带有箭头，表示你只能单向行进。

记忆小贴士：用“社交媒体”作类比

想象节点是人，弧是“友谊”。在简单图中，你们要么是朋友，要么不是。在有向图中，这就像 Instagram 上的“关注”功能——你可能会关注某人（箭头指向他们），但他们不一定会关注你！

快速回顾： 关联矩阵 (Incidence Matrix) 只是一张显示哪些节点相连的表格。如果节点 A 和节点 B 被一条权重为 5 的弧连接，你就在 A 行和 B 列的交点处填入 '5'。

重点总结： 图是骨架；网络是附加了数据（权重）的骨架。

2. 最短连接问题 (MST)

想象你要铺设光纤电缆连接五个村庄。你希望每个人都能连上网络，但电缆很昂贵，所以你希望电缆的总长度尽可能短。这就是最小生成树 (Minimum Spanning Tree, MST) 问题。

Kruskal 算法（图形化操作）

这是一种“边优先”的方法。你不需要在意从哪里开始！
第一步： 将所有弧按长度从短到长排序。
第二步： 选择最短的弧。
第三步： 选择下一条最短的弧。注意： 如果选择某条弧会产生回路 (Cycle)（封闭的环），则跳过它！
第四步： 重复上述步骤，直到所有节点都连接起来。

Prim 算法（图形或列表操作）

这是一种“节点优先”的方法。它像树一样从起点开始生长。
第一步： 选择任何一个起始节点。
第二步： 查看所有连接到你已经“获取”的节点的弧。选择其中连接到一个新节点的最短弧。
第三步： 重复步骤，直到所有节点都被纳入你的树中。

你知道吗？ Kruskal 和 Prim 算法的复杂度均为二次方 \(O(n^2)\)。这意味着如果你将边的数量增加一倍，电脑求解所需的时间大约会增加为原来的四倍！

重点总结： Kruskal = 随处挑选最短的边。Prim = 从起点向外生长。只需记住：绝不产生回路！

3. 最短路径：Dijkstra 算法

这是“Google Maps”背后的算法。它能找出从一个特定的起始节点到网络中所有其他节点的最短距离。

步骤拆解：

1. 将起始节点标记为距离 0，并将其设为“永久 (permanent)”。
2. 更新所有连接到刚变为永久节点的节点的“工作值 (working values)”。
3. 查看整个网络中所有工作值。选择具有最小工作值的节点，将其变为下一个永久节点。
4. 重复此过程，直到你的目的地节点变为永久。

常见错误： 学生往往只查看当前节点连接的节点。你必须查看整个网络，找到下一个最小值，才能将其设为永久！

重点总结： Dijkstra 是贪婪的——它总是选择下一个最近的“未访问”节点。它在顶点数量上同样具有二次方复杂度。

4. 关键路径分析 (CPA)

这用于项目管理，例如建造房屋。有些工作必须等其他工作完成后才能开始。我们使用弧上作业 (Activity-on-Arc) 图，其中弧是作业，节点是“事件”（时间点）。

两个运算过程：

• 前向传递 (Forward Pass)： 计算最早开始时间 (Earliest Event Time, EET)。当多条路径汇合到一个节点时，取最大值。（想象：“在墙壁和脚手架都完成之前，我无法开始盖屋顶”）。
• 后向传递 (Backward Pass)： 计算最晚结束时间 (Latest Event Time, LET)。当向后推算时，取最小值。（想象：“我必须在星期二之前开始这项工作，否则整个项目都会延误”）。

理解浮动时间 (Float)：

浮动时间是活动的“缓冲空间”。如果一个活动在关键路径 (Critical Path) 上，它的浮动时间就是零。如果它延误了，整个项目都会延误！
\(Total Float = LET_{end} - EET_{start} - Duration\)

重点总结： 关键路径是网络中最长的路径。它决定了完成项目所需的最短时间。

5. 网络流 (Network Flows)

这模拟了如水管中的水流或道路上的车流。你有一个源点 (Source, S) 作为起点，以及一个汇点 (Sink, T) 作为终点。

流量规则：

1. 容量 (Capacity)： 通过弧的流量不能超过其容量。
2. 守恒 (Conservation)： 对于每个节点（S 和 T 除外），流入量 = 流出量。

最大流最小割定理 (Max-Flow Min-Cut Theorem)：

割 (Cut) 是一条将源点与汇点完全分开的线。割的容量是其穿过的所有弧的容量之和（仅计算从 S 侧指向 T 侧的弧）。
重要规则： 网络中的最大流量等于最小割 (Minimum Cut) 的容量。

类比： 想象一系列水管。输送到你家的水量受限于“瓶颈”——即整个系统中 最细的那段水管。那个瓶颈就是你的最小割！

重点总结： 要找到最大流量，请寻找“瓶颈”（最小割）。流入接点的总量必须始终等于流出量。

6. 线性规划建模 (LP)

虽然我们可以手动解决这些问题，但电脑会使用线性规划 (Linear Programming) 来处理大型网络。你为每一条弧定义变量（例如，令 \(x_{AB}\) 为从 A 到 B 的流量）。
• 对于最短路径： 你最小化（距离 \(\times\) 变量）的总和。
• 对于最大流： 在满足容量限制的前提下，最大化从源点流出的总流量。

重点总结： 复杂的网络问题可以转换为方程式，让软件（如 Excel Solver）瞬间求解！

最后的鼓励

网络刚开始看起来可能只是一堆方块和线条，但它们本质上就是逻辑谜题。练习画出这些图表——当你的图形整洁清晰时，要看出“最小割”或“关键路径”会容易得多！你可以做到的！