Networks

欢迎来到网络的世界！

你好！欢迎来到进阶数学（Further Mathematics）中最实用且与“现实世界”最贴近的章节之一。你有没有想过 Google Maps 是如何找到前往朋友家最快的路线，或是像 Amazon 这样的物流公司如何决定送货司机该走哪条路才能节省燃油？这正是网络（Networks）这门学问的精髓所在！

在本章中，我们将学习如何将现实生活中的地图与连接转化为数学图表。如果一开始看起来像是密密麻麻的线条和圆圈，请别担心——我们会逐步拆解，让你彻底掌握其中的逻辑。

1. 网络的语言 (DB1)

在解决复杂问题之前，我们需要先学会它的语言。一个网络（Network）（也称为加权图，Weighted Graph）只是一组由线条连接起来的点。

你需要知道的关键术语：
• 节点 (Nodes) 或 顶点 (Vertices)： 这些就是网络中的“点”。你可以把它们想象成城市、住家或计算机服务器。
• 弧 (Arcs) 或 边 (Edges)： 这些是连接节点的“线”。把它们想象成道路、电缆或飞行航线。
• 权重 (Weight)： 这是附在弧上的数字。它代表了一种“成本”，例如距离（公里）、时间（分钟）或金钱（英镑）。如果节点 A 和节点 B 之间的弧权重为 5，这可能意味着往返它们之间需要 5 分钟。

快速回顾：
一个网络就是一个线条上带有数字（权重）的图（Graph）。如果你看到一个包含圆圈和线条的图表，你看到的其实就是一个网络！

2. 网络优化：生成树 (Spanning Trees) (DB2)

想象你是电缆公司的工程师，你需要连接 5 户人家，确保它们都有网络。你不需要在每户人家之间都铺设道路，只需要足够的电缆，让每户都能连接到主中心即可。这就是生成树（Spanning Trees）发挥作用的地方。

什么是生成树？
一个树（Tree）是指没有循环（没有回路！）的图。一个生成树则是连接网络中所有节点的树。我们的目标通常是找出最小生成树（Minimum Spanning Tree, MST）——即所有弧的权重总和为最小的那个树。

如何寻找 MST：
你会用到两种主要的“食谱”（算法）：
1. 克鲁斯克尔算法 (Kruskal’s Algorithm)： 观察整个网络中的所有弧，始终挑选权重最小的一条，只要它不会形成封闭回路即可。
2. 普林算法 (Prim’s Algorithm)： 从一个节点开始，借由挑选连接“已访问节点”与“未访问节点”之间最短的弧，不断“扩张”你的树。

比喻：
克鲁斯克尔算法就像一个精打细算的购物狂，查看整个目录并优先挑选最便宜的路线。普林算法则像是一个探险家，从家出发，永远选择通往一个全新未知领域的最短路径。

关键总结：
要找到最小生成树，你的最终答案必须使用 \(n - 1\) 条弧连接所有节点（其中 \(n\) 为节点数量），且过程中绝不能形成回路。

3. 路线检查：邮差问题 (Route Inspection) (DB3)

现在，想象你是一名邮差。你必须走遍邻里内的每一条街道去派递邮件，然后返回分拣办公室。你希望在走最短距离的情况下完成任务。

目标：
经过每一条弧至少一次，并回到起点。

逻辑：
如果每个节点都有偶数度数（Even Degree）（即从该点发出的线条数量为偶数），你就可以轻松做到而不必重复走任何路！这称为欧拉电路（Eulerian circuit）。
如果有奇数节点（Odd nodes）（线条数量为奇数的节点），你必须重复走某些路。在 AQA 教学大纲中，你通常会处理拥有两个或四个奇数节点的网络。

2 个奇数节点的步骤：
1. 找出两个度数为奇数的节点。
2. 找出这两个节点之间的最短路径。
3. 总距离将等于网络中所有权重的总和 + 这两个奇数节点之间的最短路径。

常见错误：
学生常忘记将“重复”的路径加到网络的总权重中。请务必先计算“所有弧的总权重”！

4. 旅行推销员问题 (TSP) (DB4)

这听起来像邮差问题，但其实不同！推销员不需要走过每一条道路；他们只需要拜访每一个城市（节点）一次，然后回到起点。

对于计算机来说，要找到 TSP 的绝对完美路线非常困难。因此，我们利用上限 (Upper Bounds) 和 下限 (Lower Bounds) 来缩小答案范围。

上限 (Upper Bounds)（“足够好”的路线）

上限是一个我们已知可以实现的距离。找到它的一种常见方法是最近邻算法 (Nearest Neighbour Algorithm)：
1. 从一个节点开始。
2. 前往最近且未访问过的节点。
3. 重复此步骤，直到所有节点都被访问过。
4. 别忘了：你必须加上返回起点的距离！

下限 (Lower Bounds)（“完美世界”的最小值）

下限是最佳路线不可能短于的数值。我们使用删除节点法 (Deleted Node Method) 来找到它：
1. 选定一个节点并将其“删除”（忽略它以及与其连接的所有弧）。
2. 为剩余的节点找出最小生成树 (MST)。
3. 找出与被删除节点相连的两条最短弧。
4. 下限 = MST 的权重 + 两条最短弧的权重。

你知道吗？
最佳解 (Optimal Solution)（即可能的最短路线）永远会落在你的下限与上限之间。\(Lower Bound \le Optimal \le Upper Bound\)。

5. 评估与优化模型 (DB5)

数学并不总是完美的。在现实世界中，如果发生交通堵塞，10 分钟的“权重”可能会变动。优化模型 (Refining a model) 意味着调整你的网络，使其更符合现实。

什么可能会改变？
• 单行道： 弧可能只能单向通行（有向弧，Directed Arcs）。
• 道路封闭： 如果道路封锁，弧的权重可能会变成“无限大”。
• 可变成本： 燃料价格或过路费可能会将“权重”从距离转变为成本。

快速回顾框：
• 生成树： 以最小成本连接所有节点（无回路）。
• 路线检查： 涵盖所有弧（邮差问题）。
• TSP： 拜访所有节点并回到起点（推销员问题）。
• 上限： 我们找到的一条路线（通常使用最近邻算法）。
• 下限： 理论上的最小值（使用删除节点法 + MST）。

如果这些算法起初让你觉得枯燥，别担心。练习在图表上多描几次，它们就会变得自然而然！你一定可以做到的！