欢迎来到网络世界！
欢迎来到进阶数学（Further Mathematics）中最实用的章节之一！在这一节中，我们将探索网络（Networks）。如果你曾经使用 GPS 寻找回家的最快路线，好奇过像 Amazon 这样的物流公司是如何规划配送路线，又或者想了解互联网是如何保持连接的，那么你其实已经接触过网络的强大之处了。
学完这些笔记后，你将能掌握网络的“语言”，找出连接各个地点最高效的方法，并解决关于在不同点之间行进的复杂难题。别担心一开始会看到很多术语——我们会一步步拆解，让你轻松上手！
1. 网络的语言
在解决问题之前，我们需要先了解所面对的对象。网络（有时被称为权重图，weighted graph）其实就是一系列由线条连接的点，而这些线条上标有数值。
必须掌握的关键术语：
- 节点 (Nodes 或 Vertices)： 这是网络中的“点”。你可以把它们想象成地图上的城市或房间里的电脑。
- 弧 (Arcs 或 Edges)： 这是连接节点的“线”。你可以把它们想象成道路或电缆。
- 权重 (Weight)： 这是分配给每条弧的数值，代表现实世界中的具体度量，例如距离、时间或成本。
现实生活中的类比： 想象一下你所在区域的地图。节点是商店，弧是连接它们的路径，而权重则是走过每条路径所需的时间（分钟）。
快速复习：
- 节点 (Node)： 一个点。
- 弧 (Arc)： 一条线。
- 权重 (Weight)： 这条线的“代价”。
2. 生成树与优化
有时候，我们想要用最小的总权重连接网络中的每一个节点。这被称为最小生成树 (Minimum Spanning Tree, MST)。
什么是生成树？
树 (Tree) 是一种没有“环”（cycles）且所有部分都连通的图。而生成树 (Spanning Tree) 则是包含网络中每一个节点的树。我们在“优化”过程中的目标，通常就是找到达成此目的最“省钱”（即权重最小）的方法。
为什么这很有用？
想象你是一家电缆公司，想要为村里的 10 户人家提供光纤宽带。你希望在确保每户人家都连入网络的前提下，使用最少量的电缆。这就是典型的 MST 问题！
重点总结：
生成树连接所有节点且没有环。为了进行优化，我们要寻找总权重最小的弧集合。
3. 路径检查问题 (Route Inspection Problems)
你有没有看过邮差走遍社区的每一条街道？他们解决的其实就是路径检查问题（也被称为中国邮差问题，Chinese Postman Problem）。
目标：
找出最短路径，该路径必须经过每一条弧至少一次，并最终回到起点。
解题步骤：
- 检查度数 (Degrees)： 查看每个节点并计算连接到它的弧的数量，这就是度数。
- 找出奇数节点： 如果所有节点的度数都是偶数，则该网络是欧拉图 (Eulerian)。你可以不重复地走过每一条弧！
- 配对奇数节点： 如果存在度数为奇数的节点（奇数节点的总数一定是偶数！），你必须重复连接它们之间的最短路径，使它们变为“偶数”。
- 计算总权重： 总权重 = (所有弧的总和) + (重复的最短路径权重)。
常见错误： 同学们经常忘记寻找奇数节点之间最短的路径。如果你有两个奇数节点 A 和 B，最短路径可能并非直接连接它们的弧，而是经过节点 C 的路径！
4. 旅行推销员问题 (The Travelling Salesperson Problem, TSP)
这是一个经典问题！推销员需要造访网络中的每一个节点并回到起点，但同时希望总距离越短越好。
上限与下限
TSP 对于大型网络来说，要找到完美解非常困难。因此，我们通常会找出一个数值范围，让答案落于其中。
1. 上限 (寻找“足够好”的路线)
我们使用最近邻算法 (Nearest Neighbour Algorithm)：
步骤 1： 从任意节点开始。
步骤 2： 前往最近且尚未造访过的节点。
步骤 3： 重复上述步骤直到造访所有节点，最后回到起点。
注意： 这给出了最佳路线的一个最大可能值。真正的最佳路线长度将等于或小于此值。
2. 下限 (寻找“底线”)
为了找到下限，我们使用删除节点法 (Deleted Node Method)：
步骤 1： 删除一个节点及所有连接到它的弧。
步骤 2： 为剩余的节点找出最小生成树 (MST)。
步骤 3： 加上刚刚被删除的节点所连接的两条最短弧的权重。
注意： 真正的最佳路线长度将等于或大于此数值。
记忆小撇步：
- 上限 (Upper Bound)： 把它看作“天花板”。我们知道答案不会比这更糟。
- 下限 (Lower Bound)： 把它看作“地板”。我们知道答案不可能比这更好。
5. 评估与完善模型
在进阶数学中，我们不只是“做算术”，更要思考这些数学模型在现实世界中是否合理。
修改模型：
别担心这看起来很复杂；这主要取决于常识！ 当我们要用网络来代表现实时，可能需要进行调整，因为：
- 单行道： 弧可能只能单向通行（有向弧）。
- 交通/施工： 权重（时间）可能会根据一天中的不同时段而改变。
- 实用性： 数学上的最短路径可能会包含大型货车无法转弯的路口。
你知道吗？ 完善模型是一个循环。你建立模型、检验它是否有效、找出缺陷，然后更新权重或弧以使其更准确。
章节总结：
DB1： 节点是点，弧是线，权重是数值。
DB2： 生成树在没有环的情况下连接所有点。
DB3： 路径检查覆盖每一条弧（邮差问题）。
DB4： TSP 覆盖每一个节点（推销员问题）。使用最近邻法求上限，删除节点法求下限。
DB5： 务必检查你的网络模型是否符合现实生活中的限制条件。