Algorithms and graph theory

欢迎来到决策数学（Decision Mathematics）的世界！

欢迎来到决策数学 1 (Decision Mathematics 1) 的世界。这门数学分支并非探讨复杂的微积分或抽象的几何，而是关于效率 (efficiency) 的科学。你可以把它看作是“现实世界的数学”。无论是 GPS 导航规划最快路径、仓库员工整理货物，还是电脑排列你的播放列表，背后运作的都是算法 (algorithms)。在这一章中，我们将学习如何逐步执行这些指令，并理解那些被称为图 (graphs) 的“地图式”结构。

如果起初觉得某些术语听起来有点生涩，别担心——我们会把所有内容拆解成简单易懂的小单元！

1. 算法：数学的“食谱”

算法 (algorithm) 其实就是一系列用来解决特定问题的精确指令。其实你每天都在使用它们！烘焙蛋糕的食谱或是组装乐高积木的说明书，都是算法的一种。

效率与阶数 (Efficiency and Order)

在进阶数学 (Further Maths) 中，我们不只在意算法是否有效，更在意它有多快。这就是所谓的效率 (efficiency)。我们通过观察算法的阶数 (order) 来衡量效率。

问题规模 (\(n\))： 通常指列表中的项目数量或图中的顶点数量。
阶数： 用来衡量“执行时间”（运算次数）随着问题规模增加而如何增长。如果你将项目数量增加一倍，而执行时间增加为原来的四倍，那么该算法很可能是二次阶 (quadratic order) \(O(n^2)\)。

快速复习：常见阶数
• 线性阶 \(O(n)\)： 时间增长速度与列表长度相同。
• 二次阶 \(O(n^2)\)： 时间与规模的平方成正比（在排序问题中很常见）。
• 三次阶 \(O(n^3)\)： 时间与规模的立方成正比。

重点提示： 对于大规模问题而言，阶数越低，算法就越“有效率”！

2. 排序与装箱 (Sorting and Packing)

想象你有一堆杂乱的书，你需要按字母顺序排列。你会如何系统化地处理？这就是排序算法 (sorting algorithms) 的用武之地。

气泡排序法 (Bubble Sort)

气泡排序法 (Bubble Sort) 是最简单的排序方式。你比较相邻的项目，如果顺序错误就将它们交换。最大的项目会像气泡一样“浮”到列表末端。

逐步流程：
1. 从列表开头开始。
2. 比较前两个项目。如果第一个比第二个大，就进行交换。
3. 移动到下一对并重复此步骤，直到抵达列表末端（这称为一轮扫描 (pass)）。
4. 重复扫描，直到某次扫描过程中没有任何交换发生为止。

快速排序法 (Quick Sort)

对于大型列表，快速排序法 (Quick Sort) 的效率高得多。它利用一个枢轴点 (pivot) 将列表分成两个较小的列表（一个放较小的项目，一个放较大的项目）。

Edexcel 对于枢轴点的规则： 若要找出 \(N\) 个项目列表中的中间项（枢轴点）：
• 如果 \(N\) 是奇数，使用位置 \( \frac{1}{2}(N+1) \)。
• 如果 \(N\) 是偶数，使用位置 \( \frac{1}{2}(N+2) \)。

例子： 在 6 个项目的列表中，枢轴点是第 4 个；在 9 个项目的列表中，枢轴点是第 5 个。

装箱问题 (Bin Packing)

我们如何将物品装入最少数量的“箱子”(bins) 中？
• 首次适应法 (First-Fit)： 将每个物品放入第一个有空间的箱子中。
• 首次适应递减法 (First-Fit Decreasing)： 先将物品按降序排列，再执行首次适应法。这通常效率更高！
• 全满装箱法 (Full-Bin)： 寻找能刚好填满箱子的物品组合。

常见错误： 在使用“首次适应法”时，记得对于每一个物品，都要检查箱子 1、箱子 2、箱子 3……不要只停留在当前的箱子！

3. 图论基础 (Graph Theory)

图 (graph) 是一组点的集合，称为顶点 (vertices)（或节点 nodes），并由称为边 (edges)（或弧 arcs）的线连接。

关键术语：

• 权重 (Weight)： 与边相关联的数值（如距离、成本或时间）。带有权重的图称为网络 (network)。
• 度数 (Degree/Valency)： 在一个顶点处汇集的边的数量。如果一个顶点连接了 3 条边，它的度数就是 3（奇数）。
• 路径 (Path)： 一组边的序列，且路径中不会重复访问同一个顶点。
• 圈 (Cycle)： 起点和终点相同的路径。
• 连通 (Connected)： 若图中任意两点之间皆可互通，则为连通图。
• 树 (Tree)： 没有圈的连通图。
• 生成树 (Spanning Tree)： 包含原图中所有顶点的一棵树。

你知道吗？ 握手引理 (Handshaking Lemma) 指出：所有顶点的度数之和等于边数的两倍。这意味着度数之和永远是偶数！

4. 图的类型

有些图具有特殊属性，处理起来会更简单：

• 完全图 (Complete Graph, \(K_n\))： 每个顶点都与其他所有顶点恰好有一条边连接。拥有 5 个顶点的完全图记为 \(K_5\)。
• 同构图 (Isomorphic Graphs)： 两张图看起来不同，但拥有相同数量的顶点和相同的连接关系。它们在本质上是“伪装”成不同外表的同一张图。
• 平面图 (Planar Graph)： 一种可以画出来且没有任何边交叉（顶点处除外）的图。
• 子图 (Subgraph)： 原图中的一部分。

重点提示： 识别图的类型能帮助你选择最正确的算法来解题！

5. 可遍历性 (Traversability)：我们能画出来吗？

你能在不提笔或不重复画同一条线的情况下画出一张图吗？这就是欧拉图 (Eulerian graphs) 的研究范畴。

欧拉图 (Eulerian Graph)： 每个顶点的度数皆为偶数。你可以从任意点出发，走遍每一条边后回到起点。
半欧拉图 (Semi-Eulerian Graph)： 恰好有两个顶点的度数是奇数。你可以走遍每一条边，但必须从其中一个奇数度顶点出发，并在另一个奇数度顶点结束。
皆非 (Neither)： 如果图中有超过两个顶点的度数为奇数，则该图无法一次画完。

记忆小撇步：
偶 (Even) 数度数 = 欧拉 (Eulerian)（起点/终点在同一处）。
有些 (Some/Two) 奇数度数 = 半欧拉 (Semi-Eulerian)（起点/终点在不同处）。

快速复习：
1. 计算每个顶点的度数。
2. 全为偶数 -> 欧拉图。
3. 恰好两个奇数 -> 半欧拉图。
4. 超过两个奇数 -> 不可遍历。

总结：成功小撇步

• 仔细读题： 在快速排序问题中，题目要求的是升序还是降序排列？
• 系统化： 在算法中不要跳步。考官很喜欢看到完整的“扫描”或“迭代”过程。
• 检查计算： 在装箱问题中，将所有物品总和除以箱子容量，即可得出下界 (lower bound)（理论上最少需要的箱子数）。这是检查答案是否合理的绝佳方法！
• 不要慌张： 本章的核心在于遵循规则。只要严格执行算法步骤，每次都能得到正确答案！