欢迎来到决策数学（Decision Mathematics）的世界！
欢迎来到决策数学 1 (试卷 3D) 的领域。如果你曾好奇 GPS 是如何找出最快路线、仓库如何有效率地堆叠货物，或是社交网络如何将朋友连接起来，那么你来对地方了！这一章节——算法与图论 (Algorithms and Graph Theory)，正是这一切的基础。
如果有些术语起初听起来有点“科技感”，请不用担心。你可以把算法 (algorithm) 想象成一个非常精确的食谱，而图论 (graph theory) 则是绘制地图来解开谜题的方法。让我们马上开始吧！
1. 算法：数学食谱
算法是一系列用于解决特定问题的指令。在考试中，这些指令可能会以流程图 (flow chart) 或一系列文字指令的形式呈现。
算法的“阶” (Order)
并非所有算法都是一样的！有些很快，但有些会随着问题规模变大而耗费很长时间。算法的阶（通常称为复杂度）告诉我们当问题的规模 (\(n\)) 增加时，执行时间是如何增加的。
快速回顾：常见的阶
1. 线性 (Linear)： \(O(n)\) — 如果清单长度加倍，执行时间也会加倍。
2. 二次方 (Quadratic)： \(O(n^2)\) — 如果清单长度加倍，执行时间会变为四倍！（在排序中很常见）。
3. 三次方 (Cubic)： \(O(n^3)\) — 如果清单长度加倍，执行时间会增加为 8 倍。
类比：如果你要在电话簿中寻找一个名字，线性搜索意味着要检查每一页。一个更有效率的算法会快得多！
关键重点：
问题的规模通常是指项目的数量或顶点的数量。效率是指操作次数相对于规模的增长方式。
2. 排序：冒泡排序法与快速排序法
为了处理数据，我们经常需要将其排列顺序。你需要掌握两种主要方法。
冒泡排序法 (Bubble Sort)
在冒泡排序法中，你会比较相邻的项目。如果它们的顺序错误，就将其交换。你不断地遍历清单，直到某一次遍历中完全没有发生任何交换为止。
常见错误：学生经常忘记最后必须执行一次“检查遍历”来证明清单已排好序，即使看起来已经完成了也要做！
快速排序法 (Quick Sort)
这是一种“分治法 (divide and conquer)”算法。对于大型清单，它通常比冒泡排序法快得多。
步骤指南：
1. 选择一个枢轴 (pivot)。重要规则：对于 Edexcel，请务必选择清单的中间项目。（如果清单有 \(n\) 个项目，当 \(n\) 为奇数时，枢轴位于 \([\frac{1}{2}(n+1)]\) 的位置；若 \(n\) 为偶数，则位于 \([\frac{1}{2}(n+2)]\) 的位置）。
2. 建立两个子清单：比枢轴小的项目和比枢轴大的项目。
3. 对每个子清单重复上述过程，直到每个项目都成为过枢轴为止。
记忆小撇步：Bubble sort (冒泡排序) 是 Basic (基础) 且缓慢的。Quick sort (快速排序) 当然就是... Quick (快速) 的！
3. 装箱问题 (Bin Packing)：如何塞进去
我们如何将不同大小的项目放入最少数量的箱子中？
首次适应法 (First-Fit Algorithm)
依照给定的顺序拿取每个项目，将其放入第一个有剩余空间的箱子中。这个方法很简单，但并不总是最高效率的。
首次适应递减法 (First-Fit Decreasing Algorithm)
1. 先将项目按降序（从大到小）排列。
2. 应用“首次适应法”。
为什么要这样做？ 通常，通过先放入“大”项目，小项目稍后就能更有效地“填补空隙”。
快速回顾：若要找出下界 (lower bound)（即所需的最少箱子数量），请将所有项目大小相加并除以箱子容量。结果务必无条件进位至整数！
4. 图论基础 (Graph Theory)
图 (graph) 只是由顶点 (vertices)（点，也称为节点）和边 (edges)（连接它们的线，也称为弧）组成的集合。
重要术语：
- 权重 (Weight)：与边相关联的数值（如距离或成本）。
- 度数 (Degree 或 Valency)：连接到某个顶点的边的数量。
- 路径 (Path)：一系列的边，且路径中不重复经过同一个顶点。
- 回路 (Cycle)：起点与终点为同一个顶点的路径。
- 树 (Tree)：一个连通且无回路的图。
- 生成树 (Spanning Tree)：包含图中所有顶点的树。
你知道吗？顶点的“度数”就像是那个顶点握了多少只手！
5. 特殊类型的图
教学大纲要求你识别一些特定的图类型：
完全图 (Complete Graphs, \(K_n\))
一种每个顶点都与其他所有顶点相连的图。我们使用符号 \(K_n\) 表示，其中 \(n\) 是顶点的数量。
同构图 (Isomorphic Graphs)
这些图展示了相同的资讯，但绘制方式不同。即使它们看起来形状不同，它们仍具有相同数量的顶点和相同的连接关系。
平面图 (Planar Graphs)
一种可以绘制成没有任何边交叉的图。
平面性算法：要检查一个图是否为平面图，试着找出一个哈密顿回路 (Hamiltonian cycle) 并将其画成一个圆。然后，将剩余的边放在圆的内部或外部，看看是否能避免交叉。
6. 欧拉图与哈密顿图
这些以两位著名数学家命名，重点在于图的“巡回”。
欧拉图 (Eulerian Graphs，边巡回)
一个欧拉回路 (Eulerian cycle) 会经过每一条边恰好一次，并回到起点。
- 欧拉图：所有顶点的度数均为偶数。
- 半欧拉图 (Semi-Eulerian)：恰好有两个顶点的度数为奇数（其余均为偶数）。你可以从一个奇数度数顶点出发，在另一个结束。
哈密顿回路 (Hamiltonian Cycles，顶点巡回)
一个哈密顿回路会经过每一个顶点恰好一次，并回到起点。与欧拉图不同，没有关于度数的简单规则来寻找它们——你必须亲自观察找出来！
关键重点：
Eulerian (欧拉) = Every Edge (每一条边)。
Hamiltonian (哈密顿) = Every Head (每一个顶点)。
总结检查清单
- 你能确定算法的阶吗？(\(n, n^2, n^3\))
- 你能使用中间项目作为枢轴执行快速排序法 (Quick Sort) 吗？
- 你知道首次适应法 (First-Fit) 和首次适应递减法 (First-Fit Decreasing) 的区别吗？
- 你能通过检查节点的度数来识别图是否为欧拉图吗？
- 你明白同构图只是绘制方式不同的“孪生图”吗？
如果这看起来定义很多，请别担心！只要你多练习绘制图形和排序步骤，一切都会变得自然顺手。你一定能做到的！