一、什么是决策数学？D1在A-Level进阶数学中的位置 | What Is Decision Maths? D1’s Place in A-Level Further Maths
决策数学（Decision Mathematics）是Edexcel考试局A-Level进阶数学（Further Mathematics）课程中的一个独特模块，编号为D1。与纯数学（Pure Mathematics）关注代数与微积分、力学（Mechanics）关注运动与力、统计学（Statistics）关注数据与概率不同，决策数学研究的是”如何做最优决策” – 即在有限资源和约束条件下找到最佳方案的科学。D1模块涵盖了排序算法、图论、关键路径分析和线性规划等主题，这些内容在计算机科学、运筹学、物流管理和工程设计中有广泛应用。
Decision Mathematics is a distinctive module within the Edexcel A-Level Further Mathematics syllabus, designated as D1. Unlike Pure Mathematics (algebra and calculus), Mechanics (motion and forces), and Statistics (data and probability), Decision Mathematics studies “how to make optimal decisions” – the science of finding the best solutions under limited resources and constraints. The D1 module covers sorting algorithms, graph theory, critical path analysis, and linear programming, all of which have wide-ranging applications in computer science, operations research, logistics management, and engineering design.
在Edexcel的A-Level进阶数学体系中，学生通常需要选择两个应用模块（Applied Modules）。D1是最受欢迎的选项之一，因为它的思维方式与其他数学分支截然不同 – 它更接近”计算思维”（Computational Thinking），要求学生按照明确的步骤（算法）系统地解决问题。这种结构化的思维方式对有志于学习计算机科学、工程管理或经济学的大学生尤其有帮助。
Within Edexcel’s A-Level Further Mathematics framework, students typically choose two Applied Modules. D1 is one of the most popular options because its way of thinking is fundamentally different from other branches of mathematics – it is closer to “computational thinking,” requiring students to follow explicit steps (algorithms) to solve problems systematically. This structured approach to problem-solving is especially valuable for students planning to study computer science, engineering management, or economics at university.
D1模块主要涵盖四大领域 | The Four Main Areas of D1
Edexcel D1模块的内容可以归纳为以下四大主题领域：
The content of the Edexcel D1 module can be grouped into the following four major topic areas:
1. 算法与排序（Algorithms & Sorting）：包括冒泡排序（Bubble Sort）、快速排序（Quick Sort）以及装箱算法（Bin Packing），如First-Fit、First-Fit Decreasing和Full-Bin算法。学生需要理解算法效率的概念，能够追踪（trace）算法的执行过程，并比较不同算法的优劣。
1. Algorithms & Sorting: Includes Bubble Sort, Quick Sort, and Bin Packing algorithms such as First-Fit, First-Fit Decreasing, and Full-Bin. Students need to understand the concept of algorithm efficiency, be able to trace algorithm execution, and compare the strengths and weaknesses of different algorithms.
2. 图论（Graph Theory）：涵盖图的基本概念（顶点、边、度数）、最小生成树（Kruskal算法和Prim算法）以及最短路径问题（Dijkstra算法）。图论是D1中占比最大的部分，也是考试中最常出现的题型。
2. Graph Theory: Covers basic graph concepts (vertices, edges, degree), minimum spanning trees (Kruskal’s and Prim’s algorithms), and shortest path problems (Dijkstra’s algorithm). Graph theory is the largest section of D1 and the most frequently tested topic in exams.
3. 关键路径分析（Critical Path Analysis）：通过构建活动网络图（Activity Network）来确定项目完成的最短时间，识别关键活动和非关键活动的浮动时间（Float）。这是项目管理中的核心技术。
3. Critical Path Analysis: Uses activity network diagrams to determine the minimum project completion time, identifying critical activities and the float (slack) of non-critical activities. This is a core technique in project management.
4. 线性规划（Linear Programming）：在给定线性约束条件下，通过图解法找到目标函数的最大值或最小值。这是运筹学中最基础也是最经典的优化方法。
4. Linear Programming: Finding the maximum or minimum value of an objective function under given linear constraints, solved graphically. This is the most fundamental and classic optimization method in operations research.
二、冒泡排序与快速排序：两种经典排序算法的对比与追踪 | Bubble Sort vs. Quick Sort: Comparing and Tracing Two Classic Sorting Algorithms
排序（Sorting）是D1模块中最基础的主题。Edexcel考试要求学生掌握两种排序算法：冒泡排序（Bubble Sort）和快速排序（Quick Sort）。两种算法都能将无序列表按升序排列，但它们的效率和实现方式有显著差异。
Sorting is the most fundamental topic in the D1 module. Edexcel exams require students to master two sorting algorithms: Bubble Sort and Quick Sort. Both algorithms can arrange an unordered list into ascending order, but they differ significantly in efficiency and implementation approach.
冒泡排序的完整追踪过程 | Tracing the Bubble Sort Algorithm Step by Step
冒泡排序的核心思想是：对列表进行多次遍历（pass），在每次遍历中依次比较相邻的两个元素，如果它们的顺序错误（前一个大于后一个），就交换它们的位置。每一轮遍历结束后，最大的未排序元素会”冒泡”到正确的位置。当一整轮遍历中没有任何交换发生时，排序完成。
The core idea of Bubble Sort is to make multiple passes through the list, comparing adjacent elements in each pass and swapping them if they are in the wrong order (the earlier one is larger than the later one). After each pass, the largest unsorted element “bubbles” to its correct position. Sorting is complete when a full pass occurs with no swaps.
示例：对列表 [8, 3, 6, 1, 5] 进行冒泡排序
Example: Sorting the list [8, 3, 6, 1, 5] using Bubble Sort
第一轮（Pass 1）：比较8和3→交换，得到[3, 8, 6, 1, 5]；比较8和6→交换，得到[3, 6, 8, 1, 5]；比较8和1→交换，得到[3, 6, 1, 8, 5]；比较8和5→交换，得到[3, 6, 1, 5, 8]。第一轮结束，最大值8到达正确位置。本轮有交换发生，继续下一轮。
Pass 1: Compare 8 and 3 → swap, giving [3, 8, 6, 1, 5]; compare 8 and 6 → swap, giving [3, 6, 8, 1, 5]; compare 8 and 1 → swap, giving [3, 6, 1, 8, 5]; compare 8 and 5 → swap, giving [3, 6, 1, 5, 8]. Pass 1 ends, the maximum value 8 is in its correct position. Swaps occurred, so continue to the next pass.
第二轮（Pass 2）：比较3和6→不交换；比较6和1→交换，得到[3, 1, 6, 5, 8]；比较6和5→交换，得到[3, 1, 5, 6, 8]。6到达正确位置。本轮有交换，继续。
Pass 2: Compare 3 and 6 → no swap; compare 6 and 1 → swap, giving [3, 1, 6, 5, 8]; compare 6 and 5 → swap, giving [3, 1, 5, 6, 8]. 6 is now in its correct position. Swaps occurred, continue.
第三轮（Pass 3）：比较3和1→交换，得到[1, 3, 5, 6, 8]；比较3和5→不交换；比较5和6→不交换（已排好序）。本轮有交换，继续。
Pass 3: Compare 3 and 1 → swap, giving [1, 3, 5, 6, 8]; compare 3 and 5 → no swap; compare 5 and 6 → no swap. Swaps occurred, continue.
第四轮（Pass 4）：比较1和3→不交换；比较3和5→不交换；比较5和6→不交换。本轮无任何交换，排序结束。最终排好序的列表：[1, 3, 5, 6, 8]。
Pass 4: Compare 1 and 3 → no swap; compare 3 and 5 → no swap; compare 5 and 6 → no swap. No swaps in this pass, sorting is complete. Final sorted list: [1, 3, 5, 6, 8].
效率分析：冒泡排序在最坏情况下（完全逆序）需要进行n−1轮遍历，每轮进行n−1次比较，总比较次数约为n²/2。对于n个元素的列表，冒泡排序的最大比较次数为n(n−1)/2，最大交换次数也为n(n−1)/2。因此，冒泡排序的时间复杂度为O(n²)。虽然效率不高，但冒泡排序易于理解和实现，是学习算法思想的良好起点。
Efficiency Analysis: In the worst case (completely reversed list), Bubble Sort requires n−1 passes, each with n−1 comparisons, giving approximately n²/2 total comparisons. For a list of n elements, the maximum number of comparisons is n(n−1)/2, and the maximum number of swaps is also n(n−1)/2. Thus, Bubble Sort has a time complexity of O(n²). While not the most efficient, Bubble Sort is easy to understand and implement, making it an excellent starting point for learning algorithmic thinking.
快速排序的分治策略与枢轴选择 | Quick Sort’s Divide-and-Conquer Strategy and Pivot Selection
快速排序（Quick Sort）采用分治策略（Divide and Conquer），其效率通常远高于冒泡排序。快速排序的核心步骤是：(1) 选择一个元素作为枢轴（pivot）；(2) 将所有小于枢轴的元素放到枢轴左边，大于枢轴的放到右边（这一步称为分区，partitioning）；(3) 对左右两个子列表递归应用相同的步骤。
Quick Sort employs a divide-and-conquer strategy and is generally much more efficient than Bubble Sort. The core steps are: (1) choose an element as the pivot; (2) place all elements smaller than the pivot to its left and all larger elements to its right (this step is called partitioning); (3) recursively apply the same steps to the left and right sublists.
Edexcel考试中的快速排序：Edexcel要求学生使用列表的第一个元素作为枢轴，并采用一种特定的分区方法 – 从列表两端向中间扫描。具体做法是：使用两个指针（或索引），左指针从枢轴的下一个位置向右移动，寻找大于枢轴的元素；右指针从列表末尾向左移动，寻找小于枢轴的元素。当两个指针找到符合条件的元素后，交换它们。当指针交叉时，分区完成，将枢轴放到正确位置。
Quick Sort in Edexcel Exams: Edexcel requires students to use the first element of the list as the pivot and a specific partitioning method – scanning inward from both ends. Specifically: use two pointers (or indices), the left pointer moves right from the position after the pivot looking for elements greater than the pivot; the right pointer moves left from the end looking for elements smaller than the pivot. When both find qualifying elements, swap them. When the pointers cross, partitioning is complete – place the pivot in its correct position.
示例：对 [9, 4, 7, 2, 6, 1, 5] 进行快速排序
Example: Sorting [9, 4, 7, 2, 6, 1, 5] using Quick Sort
选择9为枢轴。左指针从4开始寻找>9的元素（找不到），右指针从5向左寻找<9的元素，找到5、1、6、2、7、4均小于9。右指针一直移到索引1处（元素4），此时左指针在索引7（已超出列表），指针交叉。将枢轴9与右指针位置的元素（4）交换→[4, 9, 7, 2, 6, 1, 5]不对，因为右指针已经在枢轴左边了...实际上，当右指针移到枢轴位置左侧时，不需要交换，因为枢轴已经在正确位置...等等，让我们严格按照Edexcel的方法重新追踪。
Select 9 as the pivot. The left pointer starts from 4 looking for >9 (none found), the right pointer moves left from 5 looking for <9, finding 5, 1, 6, 2, 7, 4 are all smaller than 9. The right pointer moves all the way to index 1 (element 4), at which point the left pointer is at index 7 (beyond the list), pointers cross. Swap pivot 9 with the element at the right pointer (4) → [4, 9, 7, 2, 6, 1, 5] - this is incorrect because the right pointer is already left of the pivot. Actually, when the right pointer has moved past the pivot position to the left, no swap is needed since the pivot is already in the correct position. Let me re-trace strictly following the Edexcel method.
正确追踪（Edexcel方法）：枢轴=9（第一个元素）。从左向右找>9的元素（指针从4开始）→到末尾也没找到，左指针停在列表末尾后。从右向左找<9的元素（指针从5开始）→5<9，右指针停在5处。指针未交叉，交换当前元素（没有左元素可交换，因为左指针已出界），将枢轴9与右指针位置的5交换→得到[5, 4, 7, 2, 6, 1, 9]。两个子列表：[5, 4, 7, 2, 6, 1]和[]（空）。对左子列表递归：枢轴=5，左指针从4找>5→找到7；右指针从1找<5→找到1；交换7和1→[5, 4, 1, 2, 6, 7]。继续，左指针从2找>5→找到6；右指针从6找<5→找到2（在左指针已经经过的位置）；指针交叉。交换枢轴5与右指针的2→[2, 4, 1, 5, 6, 7, 9]。子列表：[2, 4, 1]和[6, 7]。继续递归直到全部有序。
Correct Trace (Edexcel Method): Pivot = 9 (first element). Scan left to right for >9 (pointer starts at 4) → reaches the end without finding any, left pointer stops beyond the list. Scan right to left for <9 (pointer starts at 5) → 5 < 9, right pointer stops at 5. Pointers haven't crossed; swap pivot 9 with the element at the right pointer position (5) → [5, 4, 7, 2, 6, 1, 9]. Two sublists: [5, 4, 7, 2, 6, 1] and [] (empty). Recurse on left sublist: pivot = 5, left pointer from 4 looking for >5 → finds 7; right pointer from 1 looking for <5 → finds 1; swap 7 and 1 → [5, 4, 1, 2, 6, 7]. Continue, left pointer from 2 looking for >5 → finds 6; right pointer from 6 looking for <5 → finds 2 (already to the left of left pointer); pointers cross. Swap pivot 5 with right pointer's 2 → [2, 4, 1, 5, 6, 7, 9]. Sublists: [2, 4, 1] and [6, 7]. Continue recursively until fully sorted.
效率对比：快速排序的平均时间复杂度为O(n log n)，远优于冒泡排序的O(n²)。但在最坏情况下（例如已经排好序的列表，且每次都选第一个元素作为枢轴），快速排序的性能会退化到O(n²)。不过，这种情况在实际应用中可以通过随机选择枢轴来避免。在Edexcel考试中，学生需要能够在笔试条件下完整追踪快速排序的每一轮分区过程。
Efficiency Comparison: Quick Sort has an average time complexity of O(n log n), far superior to Bubble Sort’s O(n²). However, in the worst case (e.g., an already-sorted list with the first element always chosen as the pivot), Quick Sort degrades to O(n²). In practice, this can be avoided by choosing the pivot randomly. In Edexcel exams, students need to be able to fully trace each round of Quick Sort partitioning under written exam conditions.
三、装箱算法：First-Fit、First-Fit Decreasing 与 Full-Bin 策略 | Bin Packing Algorithms: First-Fit, First-Fit Decreasing, and Full-Bin Strategies
装箱问题（Bin Packing Problem）是决策数学中另一类重要的算法问题。问题的核心是：给定一组具有不同”大小”（重量、长度、时间等）的物品和一个固定容量的箱子（bin），如何用最少的箱子装下所有物品？D1模块要求掌握三种装箱算法。
The Bin Packing Problem is another important algorithmic problem in Decision Mathematics. The core question is: given a set of items with different “sizes” (weights, lengths, times, etc.) and bins of fixed capacity, how can we pack all items using the minimum number of bins? The D1 module requires mastery of three bin packing algorithms.
First-Fit 算法：按顺序放入第一个能装的箱子 | The First-Fit Algorithm: Sequential Placement
First-Fit是最直观的装箱策略：按照物品给定的顺序，依次将每个物品放入第一个有足够剩余空间的箱子中。如果当前所有箱子都装不下该物品，则打开一个新箱子。
First-Fit is the most intuitive packing strategy: following the given order of items, place each item into the first bin that has sufficient remaining capacity. If no existing bin can accommodate the item, open a new bin.
示例：箱子容量=10，物品为 [6, 4, 5, 2, 7, 3, 2]
Example: Bin capacity = 10, items = [6, 4, 5, 2, 7, 3, 2]
物品6→箱子1放入（剩余4）。物品4→箱子1还有4，正好放入（剩余0）。物品5→箱子1满了，箱子2为空，放入箱子2（剩余5）。物品2→箱子2剩余5≥2，放入箱子2（剩余3）。物品7→箱子2剩余3不够，箱子3为空，放入箱子3（剩余3）。物品3→箱子1满了，箱子2剩余3≥3，放入箱子2（剩余0）。物品2→箱子1、2满了，箱子3剩余3≥2，放入箱子3（剩余1）。结果：使用3个箱子。
Item 6 → placed in Bin 1 (remaining 4). Item 4 → Bin 1 has 4 left, fits perfectly (remaining 0). Item 5 → Bin 1 full, Bin 2 empty, placed in Bin 2 (remaining 5). Item 2 → Bin 2 has 5 ≥ 2, placed in Bin 2 (remaining 3). Item 7 → Bin 2 has only 3, not enough. Bin 3 empty, placed in Bin 3 (remaining 3). Item 3 → Bins 1 and 2 full, Bin 3 has 3 ≥ 3, placed in Bin 3 (remaining 0). Item 2 → Bins 1, 2, 3 all full. Open Bin 4, placed in Bin 4 (remaining 8). Result: 4 bins used.
等等，让我重新算。箱子3放进3后剩余0，最后一个物品2放不进已满的箱子，打开箱子4。结果是4个箱子：箱子1=[6,4]，箱子2=[5,2]，箱子3=[7,3]，箱子4=[2]。总共用了4个箱子。
Wait, let me recalculate. After placing item 3 in Bin 3, Bin 3 has 0 remaining. The last item 2 cannot fit in any full bin, so open Bin 4. Result: 4 bins – Bin 1 = [6,4], Bin 2 = [5,2], Bin 3 = [7,3], Bin 4 = [2]. Total: 4 bins used.
First-Fit Decreasing：先排序再装箱的改进策略 | First-Fit Decreasing: Sort First, Then Pack
First-Fit Decreasing (FFD) 是对First-Fit的简单但有效的改进：先将所有物品按大小降序排列，然后对排序后的列表应用First-Fit算法。
First-Fit Decreasing (FFD) is a simple but effective improvement on First-Fit: first sort all items in descending order of size, then apply the First-Fit algorithm to the sorted list.
对同一示例应用FFD：降序排列→[7, 6, 5, 4, 3, 2, 2]。7→箱1（剩3）；6→箱1装不下，箱2（剩4）；5→箱2装不下，箱3（剩5）；4→箱2剩4正好（剩0）；3→箱1剩3正好（剩0）；2→箱3剩5≥2（剩3）；2→箱3剩3≥2（剩1）。结果：3个箱子 – 箱1=[7,3]，箱2=[6,4]，箱3=[5,2,2]。FFD用了3个箱子，比First-Fit的4个更优。
Applying FFD to the same example: Sort descending → [7, 6, 5, 4, 3, 2, 2]. 7 → Bin 1 (remaining 3); 6 → Bin 1 can’t fit, Bin 2 (remaining 4); 5 → Bin 2 can’t fit, Bin 3 (remaining 5); 4 → Bin 2 has 4, fits perfectly (remaining 0); 3 → Bin 1 has 3, fits perfectly (remaining 0); 2 → Bin 3 has 5 ≥ 2 (remaining 3); 2 → Bin 3 has 3 ≥ 2 (remaining 1). Result: 3 bins – Bin 1 = [7,3], Bin 2 = [6,4], Bin 3 = [5,2,2]. FFD uses 3 bins, better than First-Fit’s 4.
Full-Bin 算法：寻找刚好装满的组合 | The Full-Bin Algorithm: Finding Perfect-Fit Combinations
Full-Bin算法采用了一种不同的思路：通过目测（inspection）寻找能够刚好装满一个箱子的物品组合（即物品之和等于箱子容量），优先使用这些”满箱”组合，然后对剩余物品应用First-Fit。虽然Full-Bin并非总是产生最优解，但它通常在物品大小分布均匀时表现良好。
The Full-Bin algorithm takes a different approach: by inspection, find combinations of items that exactly fill a bin (i.e., items summing to the bin capacity), use these “full-bin” combinations first, then apply First-Fit to the remaining items. While Full-Bin does not always produce the optimal solution, it generally performs well when item sizes are evenly distributed.
对同一示例应用Full-Bin：目测发现[6,4]是一个满箱组合（6+4=10），[7,3]也是一个满箱组合（7+3=10）。先使用这两个组合（占用2个箱子），剩余物品为[5, 2, 2]。对剩余物品应用First-Fit：5→箱3（剩5），2→箱3（剩3），2→箱3（剩1）。结果：3个箱子。注意，Full-Bin和FFD在这个例子中产生了相同的结果，但在其他例子中可能不同。
Applying Full-Bin to the same example: By inspection, [6,4] is a full-bin combination (6+4=10), and [7,3] is also a full-bin combination (7+3=10). Use these two combinations first (2 bins), remaining items: [5, 2, 2]. Apply First-Fit: 5 → Bin 3 (remaining 5), 2 → Bin 3 (remaining 3), 2 → Bin 3 (remaining 1). Result: 3 bins. Note that Full-Bin and FFD produce the same result in this example but may differ in others.
考试提示：Edexcel D1考试中的装箱问题通常会要求考生依次应用三种算法并比较结果。记住要清晰展示每一步的装箱过程，包括每个箱子放入物品后的剩余容量。在比较算法时，FFD通常（但不总是）优于First-Fit，而Full-Bin的效果取决于能否找到足够多的”满箱”组合。
Exam Tips: Bin packing questions in Edexcel D1 exams typically require candidates to apply all three algorithms in sequence and compare results. Remember to clearly show the packing process for each step, including the remaining capacity after each item is placed. When comparing algorithms, FFD is usually (but not always) better than First-Fit, while Full-Bin’s effectiveness depends on how many full-bin combinations can be found.
四、图论基础：顶点、边、度数以及图在D1中的表示方法 | Graph Theory Fundamentals: Vertices, Edges, Degree, and Representations in D1
图论（Graph Theory）是D1模块中篇幅最大、考试权重最高的主题。图（graph）由顶点（vertices/nodes）和连接顶点的边（edges/arcs）组成。图论提供了一种强大的数学语言来描述和分析网络结构 – 无论是交通网络、通信网络还是社交网络。
Graph Theory is the largest and most heavily weighted topic in the D1 module. A graph consists of vertices (nodes) and edges (arcs) connecting them. Graph theory provides a powerful mathematical language for describing and analyzing network structures – whether transportation networks, communication networks, or social networks.
图的基本概念与术语 | Basic Concepts and Terminology of Graphs
顶点（Vertex/Node）：图中的基本元素，通常用字母或数字表示（如A, B, C, D）。在D1考试中，顶点通常代表地点、任务或状态。
Vertex (Node): The basic element of a graph, typically denoted by letters or numbers (e.g., A, B, C, D). In D1 exams, vertices usually represent locations, tasks, or states.
边（Edge/Arc）：连接两个顶点的线段。边可以带权重（weight），表示距离、时间或成本。如果边有方向（从一个顶点指向另一个顶点），则称为有向边（directed edge/arc），对应的图称为有向图（digraph）。
Edge (Arc): A line segment connecting two vertices. Edges can have weights representing distance, time, or cost. If an edge has a direction (pointing from one vertex to another), it is called a directed edge (arc), and the corresponding graph is a digraph (directed graph).
度数（Degree/Valency/Order）：一个顶点的度数是与该顶点相连的边的数量。在D1考试中，”度”（degree）、”价”（valency）和”阶”（order）这三个术语是等价的，可以互换使用。一个图中所有顶点的度数之和等于边数的两倍（握手引理，Handshaking Lemma）。
Degree (Valency/Order): The degree of a vertex is the number of edges connected to it. In D1 exams, “degree,” “valency,” and “order” are equivalent terms and can be used interchangeably. The sum of the degrees of all vertices in a graph equals twice the number of edges (the Handshaking Lemma).
路径（Path）：从一个顶点到另一个顶点的一系列连续的边，不重复经过任何顶点。
Path: A sequence of consecutive edges from one vertex to another, without revisiting any vertex.
回路（Cycle/Circuit）：起点和终点相同的路径，且路径中不重复经过其他顶点。
Cycle (Circuit): A path that starts and ends at the same vertex, with no other vertex repeated in the path.
树（Tree）：不包含任何回路的连通图。树在D1中非常重要，因为它是最小生成树和关键路径分析的基础。
Tree: A connected graph that contains no cycles. Trees are crucial in D1 as they form the foundation of minimum spanning trees and critical path analysis.
图的矩阵表示：距离矩阵与邻接矩阵 | Matrix Representations: Distance Matrix and Adjacency Matrix
在D1考试中，图通常以两种矩阵形式呈现：(1) 距离矩阵（Distance Matrix），其中每个元素表示两个顶点之间的边的权重（如果没有直接连接，通常用”–“表示）；(2) 邻接矩阵（Adjacency Matrix），其中元素为0或1表示两个顶点之间是否存在边。距离矩阵用于Prim算法和Dijkstra算法，邻接矩阵用于分析图的连通性和度数。
In D1 exams, graphs are typically presented in two matrix forms: (1) Distance Matrix, where each element represents the weight of the edge between two vertices (with “-” typically indicating no direct connection); (2) Adjacency Matrix, where elements are 0 or 1 indicating whether an edge exists between two vertices. Distance matrices are used in Prim’s and Dijkstra’s algorithms, while adjacency matrices are used for analyzing connectivity and degrees.
五、最小生成树：Kruskal算法与Prim算法的对比与应用 | Minimum Spanning Trees: Kruskal’s vs. Prim’s Algorithm — Comparison and Application
最小生成树（Minimum Spanning Tree, MST）是D1图论部分的核心考点。一个连通加权图的最小生成树是一个包含所有顶点的树（无回路的连通子图），且所有边的权重之和最小。D1要求学生掌握两种构建MST的算法：Kruskal算法和Prim算法。
The Minimum Spanning Tree (MST) is a core examination topic in D1 graph theory. An MST of a connected weighted graph is a tree (a connected subgraph with no cycles) that includes all vertices and has the minimum possible total edge weight. D1 requires students to master two algorithms for constructing an MST: Kruskal’s algorithm and Prim’s algorithm.
Kruskal算法：按权重排序选边 | Kruskal’s Algorithm: Selecting Edges by Weight
Kruskal算法的步骤非常直观：(1) 将所有边按权重从小到大排序；(2) 从最小权重的边开始，依次选择不会形成回路的边加入生成树；(3) 当已经选择了V−1条边时（V为顶点数），最小生成树构建完成。
Kruskal’s algorithm steps are straightforward: (1) Sort all edges by weight in ascending order; (2) Starting from the smallest weight, select edges that do not form a cycle and add them to the spanning tree; (3) When V−1 edges have been selected (where V is the number of vertices), the MST is complete.
Kruskal算法的关键技巧 – 检测回路：在笔试中，判断一条新边是否会形成回路的方法是：检查该边的两个端点是否都已经通过已选边连接到了生成树中。如果两个端点已经连通（即它们属于同一个连通分量），则加入这条边会形成回路，应该跳过。
Key Technique for Kruskal’s – Detecting Cycles: In written exams, determine whether a new edge would form a cycle by checking if both endpoints are already connected to the spanning tree through previously selected edges. If both endpoints are already connected (i.e., they belong to the same connected component), adding this edge would form a cycle – skip it.
Prim算法：从起点逐步生长 | Prim’s Algorithm: Growing from a Starting Vertex
Prim算法采用”生长”策略：(1) 从任意一个顶点开始（题目通常会指定起点）；(2) 在每一步中，从已连接到当前树的顶点出发，选择一条权重最小且连接到树外顶点的边；(3) 将该边和新的顶点加入树中；(4) 重复直到所有顶点都在树中。
Prim’s algorithm uses a “growth” strategy: (1) Start from any vertex (exams usually specify a starting vertex); (2) At each step, from vertices already connected to the current tree, select the edge with the smallest weight that connects to a vertex outside the tree; (3) Add that edge and the new vertex to the tree; (4) Repeat until all vertices are in the tree.
Prim算法的两种实现形式：在Edexcel D1考试中，Prim算法可以通过两种方式呈现：(a) 图形式（Graphical Form） – 直接在图上标注和连线，适合顶点较少的图；(b) 矩阵形式（Matrix/Table Form） – 使用距离矩阵，依次删除已选顶点的列并标注新顶点所在行的最小值。矩阵形式在顶点较多时更清晰，也是考试中最常见的出题方式。
Two Forms of Prim’s Algorithm: In Edexcel D1 exams, Prim’s algorithm can be presented in two ways: (a) Graphical Form – directly annotating and connecting on the graph, suitable for graphs with few vertices; (b) Matrix/Table Form – using the distance matrix, sequentially deleting columns of selected vertices and marking minimum values in the new vertex’s row. The matrix form is clearer for graphs with many vertices and is the most common exam format.
Kruskal vs. Prim对比：Kruskal算法的优势在于直观 – 只需要排序和避免回路；但需要频繁检查连通性。Prim算法在边密集的图中效率更高，且矩阵形式便于追踪和检查。两种算法在同一个图上总是产生相同的总权重（当所有边权重互不相同时，MST是唯一的），但选择的边的顺序可能不同。
Kruskal vs. Prim Comparison: Kruskal’s advantage is its simplicity – just sort and avoid cycles – but requires frequent connectivity checks. Prim’s is more efficient in dense graphs, and the matrix form is easy to trace and verify. Both algorithms always produce the same total weight on the same graph (when all edge weights are distinct, the MST is unique), but the order of edge selection may differ.
六、Dijkstra最短路径算法：从单源点到所有顶点的最优路线 | Dijkstra’s Shortest Path Algorithm: Optimal Routes from a Single Source to All Vertices
Dijkstra算法是D1图论部分的另一核心算法，用于在加权图中找到从一个指定起点到所有其他顶点的最短路径。这个算法由荷兰计算机科学家Edsger Dijkstra于1956年提出，至今仍然是路径规划（如GPS导航系统）中最重要的基础算法之一。
Dijkstra’s algorithm is another core algorithm in the D1 graph theory section, used to find the shortest path from a specified starting vertex to all other vertices in a weighted graph. Proposed by Dutch computer scientist Edsger Dijkstra in 1956, it remains one of the most important foundational algorithms in route planning today (e.g., GPS navigation systems).
Dijkstra算法的完整步骤 | Complete Steps of Dijkstra’s Algorithm
Dijkstra算法通过在顶点上标注”工作值”（working values）来逐步确定最短距离。每个顶点的标注包括：(1) 从起点到该顶点的当前最短距离；(2) 该距离来自哪个前驱顶点。其中永久性标注（permanent label）表示该最短距离已确认，临时性标注（temporary label）表示仍在更新中。
Dijkstra’s algorithm progressively determines shortest distances by assigning “working values” to vertices. Each vertex’s label includes: (1) the current shortest distance from the start to that vertex; (2) which predecessor vertex that distance comes from. Permanent labels indicate confirmed shortest distances, while temporary labels are still subject to update.
算法步骤：
Algorithm Steps:
步骤1：给起点永久性标注0（距离为0，无前驱）。所有其他顶点标注临时距离∞。
Step 1: Give the start vertex a permanent label of 0 (distance 0, no predecessor). Label all other vertices with temporary distance ∞.
步骤2：从最新获得永久标注的顶点出发，更新其所有相邻顶点的临时距离：新距离 = 当前永久标注顶点的距离 + 边的权重。如果新距离小于该顶点当前的临时距离，则更新标注（同时更新前驱顶点）。
Step 2: From the most recently permanently labelled vertex, update the temporary distances of all its adjacent vertices: new distance = distance of current permanent vertex + edge weight. If the new distance is smaller than the vertex’s current temporary distance, update the label (and predecessor).
步骤3：在所有临时标注的顶点中，选择距离最小的那个，将其标注变为永久性。
Step 3: Among all temporarily labelled vertices, select the one with the smallest distance and make its label permanent.
步骤4：重复步骤2和3，直到所有顶点都获得永久标注。从终点回溯前驱顶点即可得到最短路径。
Step 4: Repeat Steps 2 and 3 until all vertices have permanent labels. Trace back from the destination through predecessors to obtain the shortest path.
重要注意事项：Dijkstra算法要求所有边的权重必须为非负数。如果图中存在负权重边，需要使用其他算法（如Bellman-Ford算法）。此外，在Edexcel D1考试中，算法追踪通常以表格形式呈现 – 每一行代表处理一个顶点，列包括：顶点、从起点的最短距离、前驱顶点、以及是否已永久标注。
Important Note: Dijkstra’s algorithm requires all edge weights to be non-negative. If the graph contains negative-weight edges, other algorithms (such as Bellman-Ford) must be used. Additionally, in Edexcel D1 exams, algorithm traces are typically presented in table form – each row represents processing one vertex, with columns for: vertex, shortest distance from start, predecessor vertex, and whether it is permanently labelled.
七、关键路径分析：活动网络图、最早开始时间与浮动时间 | Critical Path Analysis: Activity Networks, Earliest Start Times, and Float
关键路径分析（Critical Path Analysis, CPA）是D1中最具实际应用价值的主题之一。它用于项目规划和管理，帮助确定一个项目完成的最短时间，并识别哪些活动的延迟会影响整体项目完成时间（关键活动），哪些活动有一定的灵活空间（浮动时间）。
Critical Path Analysis (CPA) is one of the most practically valuable topics in D1. It is used in project planning and management to determine the minimum time to complete a project and identify which activities, if delayed, would affect the overall project completion time (critical activities) and which activities have some flexibility (float).
活动网络图的构建 | Constructing Activity Network Diagrams
活动网络图（Activity Network / Precedence Network）由节点和边组成。在D1考试中，通常使用”节点表示活动”（Activity-on-Node）的表示方法。每个活动用一个节点表示，节点内标注活动名称（或编号）和持续时间。边（箭头）表示活动之间的先后依赖关系（precedence）。
An activity network (also called a precedence network) consists of nodes and edges. In D1 exams, the “Activity-on-Node” representation is typically used. Each activity is represented by a node containing the activity name (or number) and its duration. Edges (arrows) represent precedence relationships between activities.
每个活动节点需要计算和标注两个关键时间值：
Each activity node requires the calculation and annotation of two key time values:
最早开始时间（Earliest Start Time, EST）：在不违反前置活动约束的前提下，一个活动可以开始的最早时间。对于没有前置活动的起始活动，EST = 0。对于有前置活动的活动，EST = 所有前置活动最早完成时间的最大值。
Earliest Start Time (EST): The earliest time an activity can begin without violating the precedence constraints of preceding activities. For a starting activity with no predecessors, EST = 0. For activities with predecessors, EST = the maximum of all predecessors’ earliest finish times.
最晚完成时间（Latest Finish Time, LFT）：在不延迟整个项目的前提下，一个活动必须完成的最晚时间。对于项目的最后一个活动（终点活动），LFT = 项目的最短完成时间（即该活动的EFT）。对于其他活动，LFT = 所有后继活动最晚开始时间的最小值。
Latest Finish Time (LFT): The latest time an activity must finish without delaying the entire project. For the final activity (end activity), LFT = the project’s minimum completion time (i.e., the activity’s EFT). For other activities, LFT = the minimum of all successors’ latest start times.
浮动时间：总浮动与自由浮动 | Float: Total Float and Free Float
总浮动时间（Total Float）：一个活动可以延迟的最大时间，而不会延迟整个项目的完成时间。计算公式：总浮动 = LFT − EFT（或 = LST − EST）。总浮动为0的活动构成关键路径。
Total Float: The maximum amount of time an activity can be delayed without delaying the overall project completion time. Formula: Total Float = LFT − EFT (or = LST − EST). Activities with total float of 0 form the critical path.
关键路径（Critical Path）：网络中总浮动时间为0的活动序列。关键路径决定了项目的最短完成时间，任何一个关键活动的延迟都会直接导致整个项目的延迟。一个项目可能有多条关键路径。
Critical Path: The sequence of activities in the network with total float of 0. The critical path determines the minimum project completion time – any delay in a critical activity directly delays the entire project. A project may have multiple critical paths.
考试中的关键路径分析：Edexcel D1考试中的CPA题目通常包括：根据前置关系表构建活动网络图、正向计算EST和EFT、反向计算LFT和LST、计算每个活动的总浮动时间、识别关键路径。在答题时，务必清晰标注算法步骤 – 即使最终答案正确，缺少中间步骤也会失分。
CPA in Exams: Edexcel D1 exam questions on CPA typically include: constructing the activity network from a precedence table, forward pass to calculate EST and EFT, backward pass to calculate LFT and LST, calculating total float for each activity, and identifying the critical path(s). When answering, always show working clearly – even if the final answer is correct, missing intermediate steps will lose marks.
资源直方图与资源平滑 | Resource Histograms and Resource Levelling
在更复杂的D1问题中，还需要考虑资源约束 – 即某些活动需要共享有限的资源（如工人、机器）。资源直方图（Resource Histogram / Gantt Chart）展示了在每个时间单位内各项活动对资源的需求量。当资源需求超过供给时，需要对非关键活动进行调度 – 利用浮动时间推迟某些活动，使资源需求在时间上分布更均匀。这个过程称为资源平滑（Resource Levelling）。
In more complex D1 problems, resource constraints must also be considered – certain activities share limited resources (e.g., workers, machines). A resource histogram (Gantt chart) shows the resource demand of each activity per time unit. When demand exceeds supply, non-critical activities must be rescheduled – using float to delay some activities so resource demand is more evenly distributed over time. This process is called resource levelling.
调度（Scheduling）与甘特图（Gantt Chart）：甘特图（或称级联图，Cascade Chart）是D1中展示项目调度的标准工具。横轴表示时间，纵轴列出活动（通常按照EST排序）。每个活动用一个水平条形表示，条形的长度代表持续时间。甘特图能够直观地显示活动的时间安排、资源使用情况以及浮动时间。
Scheduling and Gantt Charts (Cascade Charts): Gantt charts (also called cascade charts in D1) are the standard tool for displaying project schedules. The horizontal axis represents time, and the vertical axis lists activities (usually sorted by EST). Each activity is shown as a horizontal bar whose length represents its duration. Gantt charts visually display activity timing, resource usage, and float.
八、线性规划：约束条件下的最优决策与图解法 | Linear Programming: Optimal Decisions Under Constraints via Graphical Methods
线性规划（Linear Programming, LP）是D1的最后一个重要主题，也是运筹学中最基础的优化工具。线性规划问题通常涉及在多个线性约束条件下，最大化或最小化一个线性目标函数。在D1级别，学生只需要掌握二元变量的图解法。
Linear Programming (LP) is the final major topic in D1 and the most fundamental optimization tool in operations research. An LP problem typically involves maximizing or minimizing a linear objective function subject to multiple linear constraints. At the D1 level, students only need to master the graphical method for two-variable problems.
线性规划的标准形式与图解法步骤 | Standard Form and Graphical Solution Steps
一个典型的D1线性规划问题包含以下要素：
A typical D1 linear programming problem includes the following elements:
决策变量（Decision Variables）：需要确定其最优值的变量。在Edexcel D1中，通常用x和y表示两种产品的生产数量或其他可以连续变化的量。
Decision Variables: The variables whose optimal values need to be determined. In Edexcel D1, x and y typically represent the production quantities of two products or other continuously variable quantities.
目标函数（Objective Function）：需要最大化或最小化的线性表达式，如”最大化利润 P = 3x + 2y”。
Objective Function: The linear expression to be maximized or minimized, e.g., “Maximize profit P = 3x + 2y.”
约束条件（Constraints）：决策变量必须满足的线性不等式组。通常包括资源限制（如时间、原材料）、需求限制和非负约束（x ≥ 0, y ≥ 0）。
Constraints: The system of linear inequalities the decision variables must satisfy. Typically includes resource limitations (e.g., time, raw materials), demand constraints, and non-negativity constraints (x ≥ 0, y ≥ 0).
图解法的完整步骤：
Complete Steps of the Graphical Method:
步骤1：将每个约束不等式画在坐标平面上。将不等式替换为等式，画出对应的直线，然后根据不等号方向确定区域（通常用箭头或阴影标注可行侧）。
Step 1: Draw each constraint inequality on the coordinate plane. Replace the inequality with an equality, draw the corresponding line, then determine the feasible side based on the inequality direction (typically annotating with arrows or shading the feasible side).
步骤2：确定可行域（Feasible Region）。可行域是所有约束条件同时满足的区域，即所有阴影或箭头交集形成的多边形区域。务必清晰地标注可行域（通常标记为大写字母R）。
Step 2: Identify the feasible region. This is the region that satisfies all constraints simultaneously – the polygonal area formed by the intersection of all shaded regions or arrows. Always clearly label the feasible region (typically with a capital R).
步骤3：画出目标函数线。用目标函数绘制一条”目标线”（profit line / objective line），通常选择一条方便计算的值（如令 P = 某个常数值）。目标函数线是一组平行的直线，目标函数值越大（对于最大化问题），直线距离原点越远。
Step 3: Draw the objective function line. Plot a “profit line” (objective line) using the objective function, typically choosing a convenient value (e.g., set P = some constant). The objective function lines form a family of parallel lines – for a maximization problem, the farther the line is from the origin, the larger the objective value.
步骤4：通过平行移动目标函数线找到最优解。将目标线平行移动，保持其在可行域内，直到它刚好经过可行域的最后一个顶点（对于最大化问题）或第一个顶点（对于最小化问题）。这个顶点就是最优解所在位置。
Step 4: Find the optimal solution by sliding the objective line parallel to itself. Keeping it within the feasible region, slide the objective line until it just passes through the last vertex of the feasible region (for maximization) or the first vertex (for minimization). This vertex is the location of the optimal solution.
步骤5：计算最优解。准确读取最优顶点的坐标（如果坐标不是整数，可能需要求解两条约束直线的交点），代入目标函数计算最优值。
Step 5: Calculate the optimal solution. Read the coordinates of the optimal vertex precisely (if coordinates are not integers, solve the intersection of the two constraint lines), then substitute into the objective function to calculate the optimal value.
整数解与目标函数系数的解释 | Integer Solutions and Interpreting Objective Function Coefficients
整数约束：在D1考试中，题目可能要求决策变量为整数（例如不能生产半台机器）。如果线性规划的最优解是非整数，而问题要求整数解，则需要测试最优顶点附近的整数点（使用”尝试法”检验所有在可行域内的整数坐标对）。
Integer Constraints: In D1 exams, questions may require decision variables to be integers (e.g., you can’t produce half a machine). If the LP’s optimal solution is non-integer and the problem requires integer solutions, test integer points near the optimal vertex (use “trial and error” to check all integer coordinate pairs within the feasible region).
目标函数系数的意义：目标函数中的系数反映了各决策变量对总目标的贡献。例如，如果P = 3x + 2y，那么每增加一单位x，P增加3；每增加一单位y，P增加2。理解这些系数对于在考试中解释最优解的经济意义非常重要。
Meaning of Objective Function Coefficients: The coefficients in the objective function reflect each decision variable’s contribution to the overall objective. For example, if P = 3x + 2y, then increasing x by one unit increases P by 3; increasing y by one unit increases P by 2. Understanding these coefficients is important for interpreting the economic significance of the optimal solution in exam questions.
常见考试陷阱：(1) 忘记画非负约束x ≥ 0和y ≥ 0的边界；(2) 目标函数线画得太粗略以至于无法精确判断最优顶点；(3) 在整数解问题中忽略了位于可行域内部但目标值更高的整数点。这三个陷阱是Edexcel D1线性规划题目中失分最常见的原因。
Common Exam Pitfalls: (1) Forgetting to draw the boundaries for non-negativity constraints x ≥ 0 and y ≥ 0; (2) Drawing the objective function line too roughly to accurately identify the optimal vertex; (3) In integer solution problems, overlooking integer points inside the feasible region that yield a higher objective value. These three pitfalls are the most common causes of lost marks in Edexcel D1 linear programming questions.
九、D1考试策略与常见题型分析 | D1 Exam Strategy and Common Question-Type Analysis
Edexcel D1考试的时间一般为1小时30分钟，满分75分。题目形式通常是6到8道问题，涵盖上述所有主要主题。以下是取得高分的关键策略：
The Edexcel D1 exam is typically 1 hour 30 minutes, worth 75 marks. Questions usually number 6 to 8, covering all the major topics above. Here are key strategies for achieving a high score:
1. 算法追踪务必展示完整步骤：D1的评分标准非常注重过程。对于排序、装箱、图论和线性规划问题，务必按步骤清晰展示算法执行过程。追踪表格（trace table）是展示过程的最佳方式。
1. Always Show Full Algorithm Traces: D1 mark schemes heavily reward process. For sorting, bin packing, graph theory, and linear programming problems, always show each step of the algorithm execution clearly. Trace tables are the best way to present the process.
2. 使用正确的术语：D1有其独特的术语体系。使用”顶点”而非”点”，”边”而非”线”，”度数/价/阶”而非”连接数”。在关键路径分析中使用EST、LFT、总浮动等标准缩写。这些术语的准确使用在评分中是隐形加分项。
2. Use Correct Terminology: D1 has its own terminology system. Use “vertex” not “point,” “edge” not “line,” “degree/valency/order” not “number of connections.” Use standard abbreviations like EST, LFT, and total float in critical path analysis. Accurate use of these terms is an implicit scoring advantage.
3. Kruskal vs. Prim的选择策略：如果题目没有指定使用哪种算法，且图是矩阵形式给出的，优先选择Prim算法（矩阵形式），因为它更不容易出错。如果图是以列表形式给出边及其权重，则Kruskal算法更方便。
3. Choosing Between Kruskal and Prim: If the question doesn’t specify which algorithm to use and the graph is given in matrix form, prefer Prim’s algorithm (matrix form) as it is less error-prone. If the graph is given as a list of edges with weights, Kruskal’s is more convenient.
4. 线性规划的画图精度：在画约束直线和可行域时，使用清晰的坐标系和标签。即使画图不是100%精确，清晰的标注（R表示可行域、箭头指示可行侧、顶点坐标标注）能够帮助考官理解你的思路。在最优解附近画一条清晰的目标函数线并标注其值。
4. Drawing Precision in Linear Programming: Use clear axes and labels when drawing constraint lines and feasible regions. Even if the drawing isn’t 100% precise, clear annotations (R for feasible region, arrows indicating the feasible side, vertex coordinate labels) help examiners follow your reasoning. Draw a clean objective function line near the optimal solution and label its value.
5. 时间管理：D1题目的难度通常是递增的。前几题（排序、装箱算法）相对简单，应该快速完成以留出时间给最后几题（Dijkstra、CPA线性规划）。建议的时间分配：排序与装箱（15分钟），最小生成树（15分钟），Dijkstra最短路径（20分钟），关键路径分析（20分钟），线性规划（20分钟）。
5. Time Management: D1 questions typically increase in difficulty. The early questions (sorting, bin packing) are relatively straightforward and should be completed quickly to leave time for the later questions (Dijkstra, CPA, linear programming). Suggested time allocation: Sorting and Bin Packing (15 min), Minimum Spanning Tree (15 min), Dijkstra’s Shortest Path (20 min), Critical Path Analysis (20 min), Linear Programming (20 min).
Summary | 总结
Edexcel D1 Decision Mathematics 1是一门独特而富有实用价值的A-Level进阶数学模块。它与纯数学、力学和统计学形成鲜明互补，培养学生的计算思维和结构化问题解决能力。D1涵盖的四大主题 – 排序与装箱算法、图论（最小生成树与最短路径）、关键路径分析和线性规划 – 构成了运筹学和计算机科学的基础。掌握这些主题不仅有助于在A-Level考试中取得高分，也为大学阶段的计算机科学、工程管理和经济学学习奠定了坚实的基础。D1的核心思想 – 在约束条件下寻找最优解 – 是一种适用于所有学科和职业的普适思维方式。
Edexcel D1 Decision Mathematics 1 is a unique and practically valuable A-Level Further Mathematics module. It complements Pure Mathematics, Mechanics, and Statistics, cultivating students’ computational thinking and structured problem-solving abilities. The four major topic areas covered in D1 – sorting and bin packing algorithms, graph theory (minimum spanning trees and shortest paths), critical path analysis, and linear programming – form the foundations of operations research and computer science. Mastering these topics not only helps achieve high scores in A-Level exams but also establishes a solid foundation for university-level studies in computer science, engineering management, and economics. The core idea of D1 – finding optimal solutions under constraints – is a universal mindset applicable across all disciplines and careers.
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导