Blog

  • Locating the Optimal Point | 定位最优点

    📚 Locating the Optimal Point | 定位最优点

    In Edexcel A-Level Decision Mathematics, linear programming is used to find the best possible outcome, such as maximum profit or minimum cost, when resources are limited. ‘Locating the optimal point’ means identifying the exact coordinates in the feasible region where the objective function takes its optimum value. This article explains both the objective line sliding method and the vertex testing method, with worked examples and exam tips.

    在 Edexcel A-Level 决策数学中,线性规划用于在资源受限时寻找最佳结果,例如最大利润或最小成本。’定位最优点’是指在可行域中确定目标函数取得最优值的准确坐标。本文介绍目标线平移法和顶点检验法,并提供例题与考试技巧。

    1. The Linear Programming Problem | 线性规划问题

    A linear programming problem involves decision variables, an objective function, and a set of linear constraints. The objective function is the expression we aim to maximise or minimise, such as profit P = 3x + 2y. The constraints are linear inequalities that represent limited resources, and non-negativity restrictions x ≥ 0, y ≥ 0 are usually assumed.

    线性规划问题包含决策变量、目标函数和一组线性约束条件。目标函数是我们要最大化或最小化的表达式,例如利润 P = 3x + 2y。约束条件表示有限资源的线性不等式,通常还假设非负限制 x ≥ 0, y ≥ 0。

    In Edexcel questions, the variables often stand for numbers of products or amounts of materials, so the final answer must make practical sense. You may be asked to find the optimal point, state the optimal value, or adjust the objective function to test different scenarios.

    在 Edexcel 考题中,变量通常代表产品数量或材料用量,因此最终答案必须符合实际意义。你可能需要求最优点、写出最优值,或调整目标函数来测试不同情景。


    2. Feasible Region and Constraints | 可行域与约束条件

    Each linear constraint defines a half-plane. For example, x + y ≤ 10 includes every point on one side of the line x + y = 10. The feasible region is the intersection of all these half-planes. It is the set of all points that satisfy every constraint simultaneously.

    每个线性约束定义了一个半平面。例如,x + y ≤ 10 包含直线 x + y = 10 一侧的所有点。可行域是所有半平面的交集,即同时满足所有约束条件的点的集合。

    When drawing the feasible region, shade out excluded areas or clearly label the allowed side. In a well-posed problem, the feasible region is a convex polygon. Its vertices, also called corner points, are essential because the optimal value is found at one of them for a linear objective function.

    绘制可行域时,应涂掉不满足的区域或清楚标出允许的一侧。在良好的问题中,可行域是一个凸多边形。其顶点(也称角点)非常关键,因为线性目标函数的最优值总是出现在某个顶点处。


    3. Objective Function and Objective Line | 目标函数与目标线

    Suppose the objective is to maximise P = ax + by. For a fixed value c, the line ax + by = c is called an objective line or profit line. Every point on this line gives the same value P = c. Different values of c produce parallel objective lines with the same gradient.

    假设目标是最大化 P = ax + by。对于某个固定值 c,直线 ax + by = c 称为目标线或利润线。该线上每个点都给出相同的 P = c 值。不同的 c 值产生平行且梯度相同的目标线。

    Objective line: ax + by = c

    目标线:ax + by = c

    The gradient of the objective line is -a/b (provided b ≠ 0). This gradient controls the direction in which the line slides as the objective value increases or decreases.

    目标线的梯度为 -a/b(假设 b ≠ 0)。该梯度决定了随着目标值增大或减小,直线平移的方向。


    4. The Vertex Theorem | 顶点定理

    If the feasible region is bounded, the fundamental theorem of linear programming states that the maximum and minimum values

    Published by TutorHao | A-Level Revision Series | aleveler.com

    更多咨询请联系16621398022(同微信)

  • Chapter Review 6: Circles | 第6章复习:圆

    📚 Chapter Review 6: Circles | 第6章复习:圆

    In Edexcel A-Level Pure Mathematics, Chapter 6 covers circles in the coordinate plane. You are expected to find the centre and radius, write equations in standard and general form, and solve problems involving tangents, chords, and intersections with lines or other circles.

    在 Edexcel A-Level 纯数学中,第6章研究坐标平面中的圆。你需要掌握求圆心和半径、写出标准式和一般式,以及解决涉及切线、弦以及与直线或另一个圆相交的问题。

    1. Standard Equation of a Circle | 圆的标准方程

    The equation of a circle with centre (a, b) and radius r is:

    圆心在 (a, b)、半径为 r 的圆的方程是:

    (x – a)² + (y – b)² = r²

    If the circle is centred at the origin, this simplifies to x² + y² = r². The radius must be positive, and the right-hand side is r², so the left-hand side cannot be negative for points on the circle.

    如果圆心在原点,方程简化为 x² + y² = r²。半径必须为正数,右边是 r²,因此圆上的点满足左边不能为负。

    You should be able to write the standard equation directly when given the centre and radius. For example, a circle with centre (-2, 5) and radius 4 has equation (x + 2)² + (y – 5)² = 16.

    你应该能够根据给出的圆心和半径直接写出标准方程。例如,圆心为 (-2, 5)、半径为 4 的圆,其方程为 (x + 2)² + (y – 5)² = 16。


    2. General Form and Identifying Centre and Radius | 一般式与识别圆心和半径

    The expanded general form of a circle is:

    圆的一般式展开为:

    x² + y² + 2gx + 2fy + c = 0

    Comparing with the standard form (x – a)² + (y – b)² = r² gives centre (-g, -f) and radius √(g² + f² – c). The expression g² + f² – c must be positive for a real circle; if it equals zero, the circle degenerates to a point.

    与标准式 (x – a)² + (y – b)² = r² 比较,可得圆心为 (-g, -f),半径为 √(g² + f² – c)。要使圆为实圆,g² + f² – c 必须大于零;如果等于零,该圆退化成一个点。

    Example: x² + y² – 6x + 8y – 11 = 0 has centre (3, -4) and radius √(9 + 16 + 11) = √36 = 6.

    例如:x² + y² – 6x + 8y – 11 = 0 的圆心为 (3, -4),半径为 √(9 + 16 + 11) = √36 = 6。


    3. Completing the Square | 配方法

    To convert a general circle equation into standard form, complete the square for the x terms and the y terms separately. This is the most reliable way to find the centre and radius from a general form.

    要把一般式转化为标准式,需要对 x 项和 y 项分别配方。这是从一般式求圆心和半径最可靠的方法。

    Example: x² + y² + 10x – 4y + 20 = 0 becomes (x + 5)² – 25 + (y – 2)² – 4 + 20 = 0, so (x + 5)² + (y – 2)² = 9, giving centre (-5, 2) and radius 3.

    例如:x² + y² + 10x – 4y + 20 = 0 变为 (x + 5)² – 25 + (y – 2)² – 4 + 20 = 0,因此 (x + 5)² + (y – 2)² = 9,圆心为 (-5, 2),半径为 3。

    Be careful: the constant term moves to the right-hand side, and you must add the same values within the brackets to both sides of the equation to keep it balanced.

    注意:常数项移到右边,配方时在括号内加上的值必须同时加到方程两边以保持平衡。


    4. Intersections with a Line | 与直线的交点

    To find where a line intersects a circle, substitute the line equation y = mx + c into the circle equation. This produces a quadratic in x, which can be solved using factorisation, the quadratic formula, or the discriminant.

    要求直线与圆的交点,将直线方程 y = mx + c 代入圆的方程,得到关于 x 的一元二次方程。可以使用因式分解、求根公式或判别式求解。

    If the discriminant is positive, there are two intersections; if it is zero, the line is a tangent; if it is negative, the line misses the circle. This discriminant test is often used to show tangency.

    如果判别式大于零,则有两个交点;如果等于零,直线为切线;如果小于零,直线与圆不相交。这个判别式检验常用于证明直线与圆相切。

    Example: Determine whether y = x + 1 intersects x² + y² = 5. Substitute: x² + (x + 1)² = 5 → 2x² + 2x – 4 = 0 → x² + x – 2 = 0, so x = 1 or x = -2, giving two points of intersection.

    例如:判断 y = x + 1 是否与 x² + y² = 5 相交。代入得 x² + (x + 1)² = 5 → 2x² + 2x – 4 = 0 → x² + x – 2 = 0,所以 x = 1 或 x = -2,得到两个交点。


    5. Tangents to a Circle | 圆的切线

    A tangent to a circle touches the circle at exactly one point. The tangent is perpendicular to the radius at the point of contact. This perpendicular relationship is central to most tangent questions.

    圆的切线在圆上恰好接触一点。切线在切点处垂直于半径。这个垂直关系是大多数切线问题的核心。

    If the gradient of the radius to point P is m_r, then the gradient of the tangent at P is m_t = -1/m_r, provided m_r ≠ 0. If the radius is vertical, the tangent is horizontal.

    如果半径到点 P 的斜率为 m_r,那么 P 点切线的斜率为 m_t = -1/m_r,前提是 m_r ≠ 0。如果半径是竖直的,切线就是水平的。

    To find the tangent equation, use the point-slope form y – y₁ = m_t(x – x₁). You may also need to prove a line is tangent by showing the perpendicular distance from the centre equals the radius, or by showing the discriminant is zero.

    求切线方程时,使用点斜式 y – y₁ = m_t(x – x₁)。你可能还需要通过证明圆心到直线的垂直距离等于半径,或证明判别式为零,来证明一条直线是切线。


    6. Chord and Perpendicular Bisector | 弦与垂直平分线

    A chord is a line segment joining two points on a circle. The perpendicular bisector of any chord passes through the centre of the circle. This property is extremely useful for locating the centre when only a chord is known.

    弦是圆上两点之间的线段。任何弦的垂直平分线都经过圆心。这个性质在已知一条弦而求圆心时非常有用。

    If you know the midpoint of a chord and its gradient, the line through the centre is perpendicular to the chord. You can use this to find the centre or to write an equation the centre must satisfy.

    如果已知弦的中点及其斜率,经过圆心的直线与该弦垂直。你可以用这个条件求出圆心,或者写出圆心必须满足的方程。

    The shortest distance from the centre to a chord is the perpendicular distance, and this distance d, the chord length L, and the radius r are related by r² = d² + (L/2)². This is Pythagoras applied to half of the chord.

    圆心到弦的最短距离是垂直距离,该距离 d、弦长 L 和半径 r 满足 r² = d² + (L/2)²。这就是把勾股定理应用于半弦得到的。


    7. Equation of a Chord and Circle Problems | 弦与圆问题

    To find the equation of a chord given two points on the circle, use the midpoint and gradient formula. Alternatively, if the chord is defined by an intersection, solve the line and circle equations simultaneously.

    如果已知圆上两点,求弦的方程可以使用中点和斜率公式。如果弦由交点定义,则联立直线与圆的方程求解。

    Example: The chord through A(1, 2) and B(5, 6) has midpoint (3, 4) and gradient (6 – 2)/(5 – 1) = 1. Its perpendicular bisector has gradient -1 and passes through (3, 4), so its equation is y – 4 = -1(x – 3).

    例如:经过 A(1, 2) 和 B(5, 6) 的弦,其中点为 (3, 4),斜率为 (6 – 2)/(5 – 1) = 1。其垂直平分线斜率为 -1,且经过 (3, 4),所以方程为 y – 4 = -1(x – 3)。

    If this chord belongs to a circle, the centre must lie on the line y = -x + 7. This is often the key step in finding the circle’s equation from a chord and one other condition.

    如果这条弦属于某个圆,圆心必定在直线 y = -x + 7 上。这往往是已知一条弦和另一个条件求圆的方程时的关键步骤。


    8. Intersection of Two Circles | 两圆的交点

    To find the common points of two circles, subtract one equation from the other to eliminate the x² and y² terms. This gives a linear equation, which often represents the common chord, also called the radical axis.

    要求两圆的公共交点,将两个方程相减以消去 x² 和 y² 项,得到一条直线方程,这条直线通常表示公共弦,也叫根轴。

    Then solve this line with one of the circle equations to find the intersection points, if any exist. If the distance between centres is greater than the sum of radii, the circles do not intersect.

    然后将该直线与其中一个圆的方程联立求解,得到交点(如果有)。如果圆心距大于半径之和,两个圆不相交。

    Example: Circle C₁: x² + y² = 25 and C₂: (x – 4)² + y² = 9. Subtract: (x – 4)² – x² = -16 → -8x + 16 = -16 → x = 4. Then y² = 25 – 16 = 9, so points (4, 3) and (4, -3).

    例如:圆 C₁: x² + y² = 25 与 C₂: (x – 4)² + y² = 9 相减:(x – 4)² – x² = -16 → -8x + 16 = -16 → x = 4。然后 y² =

    Published by TutorHao | A-Level Revision Series | aleveler.com

    更多咨询请联系16621398022(同微信)

  • Linear Programming Problems | 线性规划问题

    📚 Linear Programming Problems | 线性规划问题

    Linear programming (LP) is a mathematical technique used to find the best outcome, such as maximum profit or minimum cost, in a model whose requirements are represented by linear relationships. In A-Level Computer Science, LP appears as an optimisation problem that can be solved algorithmically, often using graphical methods for two variables or more general iterative methods such as the simplex algorithm.

    线性规划是一种数学技术,用于在由线性关系表示需求的模型中寻找最佳结果,例如最大利润或最小成本。在 A-Level 计算机科学中,线性规划作为一种优化问题出现,可以通过算法求解,通常对两个变量使用图解法,或对更一般的问题使用单纯形法等迭代方法。


    1. What is linear programming? | 什么是线性规划?

    Linear programming deals with optimising a linear objective function subject to a set of linear constraints. The key components are decision variables, an objective function, constraints, and non-negativity restrictions.

    线性规划处理的是在一组线性约束条件下优化一个线性目标函数的问题。关键组成部分包括决策变量、目标函数、约束条件和非负限制。

    Decision variables are the quantities we control, such as the number of units to produce or the amount of a resource to use.

    决策变量是我们控制的量,例如要生产的单位数量或要使用的资源数量。

    The objective function is the expression to maximise or minimise, such as total profit or total cost.

    目标函数是要最大化或最小化的表达式,例如总利润或总成本。

    Constraints are linear inequalities or equalities that limit the values of the variables. Non-negativity means that variables cannot be negative in most real-world problems.

    约束条件是限制变量取值的线性不等式或等式。非负性表示在大多数实际问题中变量不能为负。


    2. Formulating an LP problem | 建立线性规划问题模型

    To formulate an LP problem, first identify the decision variables, then write the objective function, and finally express each constraint as a linear inequality or equation.

    要建立线性规划模型,首先确定决策变量,然后写出目标函数,最后将每个约束表示为线性不等式或方程。

    For example, a company makes two products X and Y. Product X earns £3 profit per unit and product Y earns £2 per unit. Machine time limits production: each X needs 2 hours, each Y needs 1 hour, and only 16 hours are available. Packaging requires 1 hour for X and 2 hours for Y, with only 16 hours available.

    例如,一家公司生产两种产品 X 和 Y。产品 X 每单位赚取 3 英镑利润,产品 Y 每单位赚取 2 英镑。机器时间限制生产:每个 X 需要 2 小时,每个 Y 需要 1 小时,只有 16 小时可用。包装需要 X 1 小时,Y 2 小时,只有 16 小时可用。

    Let x be the number of units of X and y be the number of units of Y. The model is written as:

    设 x 为 X 的单位数量,y 为 Y 的单位数量。模型写为:

    Maximise P = 3x + 2y
    Subject to:
    2x + y ≤ 16
    x + 2y ≤ 16
    x ≥ 0, y ≥ 0

    Here P is the total profit, and the inequalities represent the machine and packaging time limits.

    这里 P 是总利润,不等式表示机器和包装时间限制。


    3. Graphical method for two variables | 两变量图解法

    For two decision variables, the constraints can be drawn as straight lines on a coordinate plane. The region that satisfies all constraints is called the feasible region.

    对于两个决策变量,约束可以在坐标平面上画成直线。满足所有约束的区域称为可行域。

    To draw the feasible region, first draw each constraint line. Then determine which side of each line satisfies the inequality by testing a point such as (0, 0). Shade the region that satisfies all inequalities simultaneously.

    要绘制可行域,首先绘制每条约束直线。然后通过测试点(如 (0, 0))确定每条直线的哪一侧满足不等式。对同时满足所有不等式的区域进行着色。

    The corner points of the feasible region are critical because the optimal solution will occur at one of these vertices. Label the axes and the constraint lines clearly.

    可行域的角点非常关键,因为最优解将出现在其中一个顶点处。需要清楚地标记坐标轴和约束直线。


    4. Feasible region and optimal solution | 可行域与最优解

    The optimal solution, if it exists, lies at a vertex of the feasible region. To find it, evaluate the objective function at each vertex and select the maximum or minimum value.

    如果存在最优解,它位于可行域的顶点。为了找到它,在每个顶点处计算目标函数值,并选择最大值或最小值。

    For the model above, the feasible region has vertices at (0, 0), (8, 0), (0, 8), and (16/3, 16/3). The objective values are shown in the table:

    对于上述模型,可行域的顶点为 (0, 0)、(8, 0)、(0, 8) 和 (16/3, 16/3)。目标函数值如下表所示:

    Vertex (x, y) P = 3x + 2y
    (0, 0) 0
    (8, 0) 24
    (0, 8) 16
    (16/3, 16/3) 80/3 ≈ 26.67

    The maximum profit is 80/3, achieved at x = 16/3 and y = 16/3. If the problem requires integer answers, rounding is not enough because the solution must remain feasible.

    最大利润为 80/3,在 x = 16/3 和 y = 16/3 处取得。如果问题要求整数答案,仅四舍五入是不够的,因为解必须保持可行。


    5. Standard form and slack variables | 标准形式与松弛变量

    To solve larger LP problems computationally, inequalities are converted into equations by adding slack variables. A slack variable represents unused resources.

    为了用计算机求解更大的线性规划问题,通过添加松弛变量将不等式转换为方程。松弛变量表示未使用的资源。

    For example, the constraint 2x + y ≤ 16 becomes 2x + y + s₁ = 16, where s₁ ≥ 0. Likewise, x + 2y ≤ 16 becomes x + 2y + s₂ = 16, where s₂ ≥ 0.

    例如,约束 2x + y ≤ 16 变成 2x + y + s₁ = 16,其中 s₁ ≥ 0。同样,x + 2y ≤ 16 变成 x + 2y + s₂ = 16,其中 s₂ ≥ 0。

    2x + y + s₁ = 16
    x + 2y + s₂ = 16
    P – 3x – 2y = 0

    Introducing slack variables transforms the problem into a set of linear equations, which is easier for algorithms such as the simplex method to process.

    引入松弛变量将问题转化为一组线性方程,这更容易被单纯形法等算法处理。


    6. Introduction to the simplex method | 单纯形法简介

    The simplex method is an iterative algorithm that moves from one vertex of the feasible region to an adjacent vertex, improving the objective value until the optimum is reached.

    单纯形法是一种迭代算法,从可行域的一个顶点移动到相邻顶点,不断改进目标值,直到达到最优。

    The method starts by creating an initial simplex tableau. It then identifies a pivot column from the most negative indicator in the bottom row for a maximisation problem. The pivot row is chosen using the minimum ratio test, and row operations are performed to update the tableau.

    该方法首先创建初始单纯形表。然后从最大化问题底部行中最负的指示数中识别主元列。使用最小比值检验选择主元行,并执行行变换以更新单纯形表。

    These steps repeat until all entries in the bottom row are non-negative. At that point, the basic variables give the optimal solution.

    重复这些步骤,直到底部行中所有条目均为非负。此时,基变量给出最优解。


    7. Computational thinking and algorithms | 计算思维与算法实现

    In computer science, LP problems are solved by encoding the model into a program. Key computational thinking skills include abstraction, decomposition, pattern recognition, and algorithm design.

    在计算机科学中,线性规划问题通过将模型编码到程序中来解决。关键的计算思维技能包括抽象、分解、模式识别和算法设计。

    Abstraction removes unnecessary detail and keeps only the objective function, constraints, and variables. Decomposition breaks the problem into smaller parts such as entering variable selection, leaving variable selection, and pivoting.

    抽象去除不必要的细节,只保留目标函数、约束和变量。分解将问题分解为更小的部分,例如选择进入变量、选择离开变量和主元变换。

    The core loop of a simplex-based solver can be described as:

    基于单纯形法的求解器的核心循环可以描述为:

    WHILE optimal not reached
    SELECT entering variable
    SELECT leaving variable by minimum ratio test
    PIVOT
    END WHILE

    This algorithmic view shows that linear programming is not only a mathematical tool but also a computational problem that can be implemented efficiently.

    这种算法视角表明,线性规划不仅是一种数学工具,而且是一个可以有效实现的计算问题。


    8. Using Python to solve LP | 使用 Python 求解线性规划

    Libraries such as SciPy provide linprog for solving linear programming problems. A typical implementation defines the coefficients of the objective function, the constraint matrix, and the bounds of the variables.

    SciPy 等库提供了 linprog 用于求解线性规划问题。典型实现定义目标函数的系数、约束矩阵和变量的边界。

    The linprog function minimises c·x subject to A_ub x ≤ b_ub and x ≥ bounds. For a maximisation problem, we must convert it by negating the objective function, because linprog minimises

    Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com

    更多咨询请联系16621398022(同微信)

  • Early and Late Event Times | 最早与最晚事件时间

    📚 Early and Late Event Times | 最早与最晚事件时间

    In Edexcel A Level Decision Mathematics, early and late event times are central to critical path analysis. They allow you to determine how soon each stage of a project can begin and how late it can be left without delaying the whole project.

    在 Edexcel A Level 决策数学中,最早与最晚事件时间是关键路径分析的核心。它们帮助你确定项目每个阶段最早可以何时开始,以及最晚可以推迟到何时而不延误整个项目。

    1. Activity Networks: Events and Activities | 活动网络:事件与活动

    In an activity-on-arc network, every node represents an event: a point in time when one or more activities finish and the next ones may begin. Arcs represent activities with fixed durations. The event at the tail of an arc must occur before that activity can start; the event at the head occurs only when all incoming activities are complete.

    在“活动在弧上”的网络中,每个节点代表一个事件:即一项或多项活动完成、后续活动可以开始的时间点。弧表示具有固定工期的活动。弧尾的事件必须先发生,该活动才能开始;弧头的事件只有在所有指向该节点的活动都完成后才会发生。


    2. Early vs Late Event Times | 最早与最晚事件时间

    The earliest event time (EET) is the soonest possible time at which an event can be reached, given the durations and dependencies. The latest event time (LET) is the latest time an event can occur without delaying the overall project. Neither is a duration; both are clock times measured from the project start.

    最早事件时间(EET)是考虑工期和依赖关系后,事件能够到达的最早时间。最晚事件时间(LET)是不延误整个项目的前提下,事件可以发生的最晚时间。二者都不是持续时长,而是从项目开始起计的时钟时间。


    3. Earliest Event Time: Forward Pass | 最早事件时间:正向推进

    The forward pass starts at the source node with EET = 0. For any other node j, consider every activity (i, j) entering j. Add its duration d(i,j) to EET(i). The earliest time for j is the maximum of these sums, because j cannot occur until all incoming activities have finished.

    正向计算从源节点开始,令 EET = 0。对于任何其他节点 j,考虑所有进入 j 的活动 (i, j),将 EET(i) 加上该活动工期 d(i,j)。节点 j 的最早时间是这些和的最大值,因为只有所有进入活动都完成后,j 才能发生。

    EET(j) = max { EET(i) + d(i,j) : (i,j) enters j }


    4. Latest Event Time: Backward Pass | 最晚事件时间:逆向推进

    The backward pass starts at the sink node. Set its LET equal to the project duration, normally the EET of the sink. For any node i, consider every activity (i, j) leaving i. Subtract its duration from LET(j). The latest time for i is the minimum of these differences, because if i occurs any later, at least one following activity will overrun.

    逆向计算从汇节点开始。将汇节点的 LET 设为项目总工期,通常等于该节点的 EET。对于任何节点 i,考虑所有离开 i 的活动 (i, j),用 LET(j) 减去活动工期。节点 i 的最晚时间是这些差值的最小值,因为如果 i 再晚发生,至少一个后续活动会超期。

    LET(i) = min { LET(j) − d(i,j) : (i,j) leaves i }

    If a question imposes a later target completion time, set LET(sink) equal to that target time instead of the earliest project duration. This changes the floats but not the forward pass values.

    如果题目规定了更晚的目标完成时间,则将 LET(汇节点) 设为该目标时间,而不是最早项目工期。这会改变浮动时间,但不会改变正向计算值。


    5. Notation, Source, Sink and Dummy Activities | 符号、源节点、汇节点与虚活动

    Edexcel questions often number events 1, 2, 3, … with the source as the lowest number and the sink as the highest. A dummy activity has zero duration and is shown as a dashed arc; it represents a logical dependency only. In forward and backward passes, dummies are treated like any other activity with d = 0.

    Edexcel 题目通常将事件编号为 1、2、3……,源节点编号最小,汇节点编号最大。虚活动的工期为 0,用虚线弧表示;它只表示逻辑依赖关系。在正向和逆向计算中,虚活动与 d = 0 的普通活动一样处理。


    6. Worked Example: Activity Data | 示例:活动数据

    The table below gives a small project. We will build the network, compute EETs, LETs, and identify the critical path. Activities are labelled A to F, with durations and immediate predecessors.

    下表给出一个小型项目。我们将构建网络,计算 EET 和 LET,并确定关键路径。活动用 A 到 F 标注,并给出工期和紧前活动。

    <

    Published by TutorHao | A-Level Revision Series | aleveler.com

    更多咨询请联系16621398022(同微信)

  • The Float of an Activity | 活动的浮动时间

    📚 The Float of an Activity | 活动的浮动时间

    In critical path analysis, the float of an activity measures how much the activity can be delayed without affecting the project completion time or the start of subsequent activities. Understanding float is essential for identifying the critical path and for efficient resource scheduling.

    在关键路径分析中,活动的浮动时间衡量该活动可以延迟多久而不影响项目完成时间或后续活动的开始。理解浮动时间对于识别关键路径和高效安排资源至关重要。


    1. What is Float? | 什么是浮动时间?

    Float, sometimes called slack, is the amount of time by which an activity can be delayed beyond its earliest start time without causing a delay to the project or to dependent activities.

    浮动时间(有时称为时差)是指活动可以比其最早开始时间延迟多久,而不会导致项目或依赖活动延迟。

    There are three types of float: total float, free float and independent float. Each gives a different level of flexibility.

    浮动时间有三种类型:总时差、自由时差和独立时差。每种类型给出不同层次的灵活性。

    An activity with zero total float lies on the critical path.

    总时差为零的活动位于关键路径上。


    2. Key Times in Critical Path Analysis | 关键路径分析中的关键时间

    To calculate float, you must first find the earliest start time (EST), earliest finish time (EFT), latest start time (LST) and latest finish time (LFT) for each activity.

    要计算浮动时间,必须首先求出每项活动的最早开始时间(EST)、最早完成时间(EFT)、最晚开始时间(LST)和最晚完成时间(LFT)。

    EST is the soonest an activity can begin once all predecessors are complete. EFT = EST + duration.

    EST 是所有前置活动完成后该活动可以开始的最早时间。EFT = EST + 持续时间。

    LFT is the latest an activity can finish without delaying the project. LST = LFT − duration.

    LFT 是在不延迟项目的前提下该活动可以完成的最晚时间。LST = LFT − 持续时间。

    These four times are obtained from a forward pass and a backward pass through the activity network.

    这四个时间通过对活动网络进行正推和逆推得到。


    3. Total Float: Definition and Formula | 总时差:定义与公式

    Total float is the maximum amount of time an activity can be delayed without delaying the whole project.

    总时差是活动可以延迟的最大时间量,而不会延迟整个项目。

    It is calculated using: Total Float = LFT − EFT, or equivalently Total Float = LST − EST.

    计算公式为:总时差 = LFT − EFT,或等价地总时差 = LST − EST。

    Both expressions always give the same value because EFT = EST + duration and LFT = LST + duration.

    两种表达式总是给出相同的结果,因为 EFT = EST + 持续时间,LFT = LST + 持续时间。

    If an activity has total float of 5 days, it can be delayed by up to 5 days without affecting the project finish date.

    如果一项活动的总时差为5天,那么它可以延迟最多5天而不影响项目完成日期。


    4. Interpreting Total Float | 解释总时差

    Total float is shared with other activities on the same non-critical chain. Using all the float on one activity may reduce the float available for later activities.

    总时差在同一非关键链上的其他活动之间是共享的。在一项活动上用掉全部时差,可能会减少后续活动可用的时差。

    A positive total float means the activity is not on the critical path. A zero total float means the activity is critical.

    总时差为正意味着该活动不在关键路径上。总时差为零意味着该活动是关键活动。

    In some exam questions, total float can be negative if a deadline is earlier than the current earliest finish; however, for standard project networks it is usually zero or positive.

    在某些考题中,如果截止日期早于当前最早完成时间,总时差可能为负;但在标准项目网络中,它通常为零或正数。


    5. Free Float: Definition and Formula | 自由时差:定义与公式

    Free float is the amount of time an activity can be delayed without delaying the earliest start of any immediately following activity.

    自由时差是指活动可以延迟的时间量,而不延迟任何紧后活动的最早开始时间。

    Free float is calculated as: Free Float = EST(next activity) − EFT(activity).

    自由时差的计算公式为:自由时差 = 紧后活动的 EST − 本活动的 EFT。

    Unlike total float, free float belongs to the activity itself and is not shared with other activities.

    与总时差不同,自由时差属于活动本身,不与其他活动共享。

    Free float can never exceed total float; it is often zero even when total float is positive.

    自由时差永远不超过总时差;即使总时差为正,自由时差也常常为零。


    6. Independent Float: Definition and Formula | 独立时差:定义与公式

    Independent float is the amount of time an activity can be delayed regardless of the timing of preceding and following activities.

    独立时差是指无论前置活动和后续活动的时间安排如何,活动都可以延迟的时间量。

    It is calculated using: Independent Float = EST(next activity) − LFT(previous activity) − duration.

    计算公式为:独立时差 = 紧后活动的 EST − 紧前活动的 LFT − 持续时间。

    If this expression is negative, the independent float is taken as zero, because negative float has no practical meaning for a single activity.

    如果该表达式为负,独立时差取为零,因为负时差对单个活动没有实际意义。

    Independent float is the most conservative measure and is rarely used in basic scheduling decisions, but exam boards may ask for it.

    独立时差是最保守的度量,在基本调度决策中很少使用,但考试局可能会要求计算它。


    7. Calculating Float from a Precedence Table | 从优先关系表计算时差

    A precedence table lists activities, their durations and immediate predecessors. Use it to build the activity network, then carry out forward and backward passes.

    优先关系表列出活动、持续时间及紧前活动。用它构建活动网络,然后进行正推和逆推。

    Record EST, EFT, LST, LFT in a table. Then apply the float formulas to each activity.

    在表格中记录 EST、EFT、LST、LFT。然后对每项活动应用时差公式。

    For example, if activity B has duration 4, EST 6, EFT 10, LST 9, LFT 13, then total float = 13 − 10 = 3 days.

    例如,若活动 B 持续时间为4,EST 为6,EFT 为10,LST 为9,LFT 为13,则总时差 = 13 − 10 = 3 天。

    Always show your workings clearly, as method marks are awarded in Edexcel Decision Mathematics.

    务必清晰展示计算步骤,因为 Edexcel 决策数学中会给予方法分。


    8. Float and the Critical Path | 时差与关键路径

    The critical path is the longest path through the network. All activities on this path have zero total float.

    关键路径是穿过网络的最长路径。该路径上的所有活动总时差为零。

    Therefore, total float is a quick way to confirm the critical activities: if total float = 0, the activity is critical.

    因此,总时差是确认关键活动的快捷方法:如果总时差为零,该活动就是关键活动。

    A critical path can be identified by listing all activities with zero total float and checking that they form a continuous chain from start to finish.

    关键路径可以通过列出所有总时差为零的活动并检查它们是否形成从开始到结束的连续链来识别。


    9. Using Cascade (Gantt) Charts to Show Float | 使用级联图(甘特图)表示时差

    A cascade chart, or Gantt chart, displays each activity as a block starting at its earliest start time, with its total float shown as a dotted extension.

    级联图(或甘特图)将每项活动显示为从最早开始时间开始的方块,并用虚线延伸表示总时差。

    The solid block represents the activity duration, while the dotted line shows the maximum delay possible before the project is affected.

    实心方块表示活动持续时间,虚线表示在项目受到影响之前可能的最大延迟。

    Exam questions often ask you to draw a cascade chart and shade or label the float clearly.

    考题经常要求绘制级联图,并清楚地标记或涂色表示时差。


    10. Common Misconceptions and Exam Tips | 常见误区与考试技巧

    Misconception 1: total float and free float are the same. They are not; total float may delay the project only when the whole chain is considered, while free float delays only the next activity.

    误区1:总时差和自由时差是相同的。其实不同;总时差只有在考虑整条链时才会延迟项目,而自由时差只影响下一个活动。

    Misconception 2: an activity with zero free float must be critical. This is false; zero free float can happen on non-critical activities if the next activity starts immediately after it.

    误区2:自由时差为零的活动一定是关键活动。这是错误的;如果下一个活动紧随其后开始,非关键活动也可能自由时差为零。

    Exam tip: always calculate all four times first, then apply the float formulas systematically to avoid arithmetic errors.

    考试技巧:始终先计算四个时间,然后系统地应用时差公式,以避免计算错误。


    11. Worked Example | 例题解析

    Activity network: A(3) → B(4) and A(3) → C(2), with B and C both preceding D(5). The project start is at time 0.

    活动网络:A(3) → B(4) 且 A(3) → C(2),B 和 C 都是 D(5) 的紧前活动。项目从时间0开始。

    Forward pass: EST(A)=0, EFT(A)=3. EST(B)=3, EFT(B)=7. EST(C)=3, EFT(C)=5. EST(D)=max(7,5)=7, EFT(D)=12.

    正推:EST(A)=0,EFT(A)=3。EST(B)=3,EFT(B)=7。EST(C)=3,EFT(C)=5。EST(D)=max(7,5)=7,EFT(D)=12。

    Backward pass: LFT(D)=12, LST(D)=7. LFT(B)=7, LST(B)=3. LFT(C)=7, LST(C)=5. LFT(A)=min(LST(B), LST(C)) = min(3,5)=3, LST(A)=0.

    逆推:LFT(D)=12,LST(D)=7。LFT(B)=7,LST(B)=3。LFT(C)=7,LST(C)=5。LFT(A)=min(LST(B), LST(C)) = min(3,5)=3,LST(A)=0。

    Total floats: A: 0; B:

    Published by TutorHao | A-Level Revision Series | aleveler.com

    更多咨询请联系16621398022(同微信)

  • Modelling a Project | 项目建模

    📚 Modelling a Project | 项目建模

    Project modelling is the process of turning a real-world project into a mathematical network of activities, durations, and precedence constraints. It allows decision mathematicians to calculate the shortest possible completion time, identify which activities cannot slip, and schedule resources efficiently.

    项目建模是将现实项目转化为由活动、工期和前置约束组成的数学网络的过程。它使决策数学家能够计算最短完工时间、识别哪些活动不能延误,并高效地安排资源。


    1. What Project Modelling Involves | 项目建模涉及什么

    A project model uses three building blocks: activities, durations, and precedence relations. Activities are tasks that consume time, durations are their lengths, and precedence relations show which tasks must finish before another can start.

    项目模型使用三个基本组件:活动、工期和前置关系。活动是消耗时间的任务,工期是活动长度,前置关系表示哪些任务必须在另一任务开始前完成。

    The main outputs in Edexcel Decision Mathematics are the minimum project completion time, the critical path, and the float for every non-critical activity. These outputs come from a network built from a precedence table.

    在爱德思决策数学中,主要输出结果是最短项目工期、关键路径以及每个非关键活动的浮动时间。这些结果来自根据前置关系表建立的网络图。


    2. Precedence Tables and Immediate Predecessors | 前置关系表与紧前

    Published by TutorHao | A-Level Revision Series | aleveler.com

    更多咨询请联系16621398022(同微信)

  • Using the Nearest Neighbour Algorithm to Find an Upper Bound | 使用最近邻算法求上界

    📚 Using the Nearest Neighbour Algorithm to Find an Upper Bound | 使用最近邻算法求上界

    In many optimisation problems, especially the travelling salesman problem, we need a quick way to estimate the best possible solution without trying every possible route. The nearest neighbour algorithm is a simple greedy heuristic that constructs a complete Hamiltonian cycle and therefore provides an upper bound for the optimal tour length.

    在许多优化问题中,尤其是旅行商问题,我们需要一种快速方法来估计最优解,而不必尝试每一条可能路线。最近邻算法是一种简单的贪心启发式算法,它构造一个完整的哈密顿回路,因此为最优回路长度提供了一个上界。


    1. The Travelling Salesman Problem and Bounds | 旅行商问题与界限

    The travelling salesman problem (TSP) asks for the shortest closed route that visits every vertex exactly once and returns to the starting vertex. This shortest route is called the optimal tour. In a minimisation problem, any feasible route gives an upper bound because the optimal tour cannot be longer than a route we have actually found.

    旅行商问题要求找到一条最短的闭合路线,访问每个顶点恰好一次并返回起点。这条最短路线称为最优回路。在最小化问题中,任意可行路线都给出一个上界,因为最优回路的长度不可能大于我们已经找到的一条路线。

    To narrow the search, we often look for a lower bound and an upper bound. If a lower bound is L and an upper bound is U, the optimal tour length T* satisfies L ≤ T* ≤ U.

    为了缩小搜索范围,我们通常寻找下界和上界。如果下界为 L,上界为 U,则最优回路长度 T* 满足 L ≤ T* ≤ U。


    2. What the Nearest Neighbour Algorithm Does | 最近邻算法做什么

    The nearest neighbour algorithm builds a route by a greedy rule: from the current vertex, move to the nearest unvisited vertex. This is repeated until all vertices have been visited, and then the route returns to the starting vertex.

    最近邻算法通过一条贪心规则构建路线:从当前顶点出发,移动到最近的未访问顶点。重复此过程,直到所有顶点都已访问,然后路线返回起始顶点。

    Because the method always chooses the smallest immediate distance, it is fast and easy to apply by hand or program. However, being greedy does not guarantee the global optimum; it only guarantees a valid Hamiltonian cycle.

    由于该方法总是选择当前最小的距离,因此无论是手工计算还是编程都十分快捷。但它只保证生成一个有效的哈密顿回路,并不保证全局最优。


    3. Why It Produces an Upper Bound | 为什么它给出上界

    Once the nearest neighbour process finishes, the output is a closed cycle that visits every vertex exactly once. This is a feasible solution to the travelling salesman problem. Since the optimal tour is the minimum over all feasible Hamiltonian cycles, its length must be less than or equal to the length of this constructed cycle.

    最近邻过程完成后,输出是一个闭合回路,每个顶点恰好访问一次。这是旅行商问题的一个可行解。由于最优回路是所有可行哈密顿回路中长度最小的,因此最优回路的长度一定小于或等于这个构造出来的回路长度。

    If the nearest neighbour tour has length U, then the optimal tour length T* satisfies T* ≤ U. This is why the result is called an upper bound.

    如果最近邻回路长度为 U,那么最优回路长度 T* 满足 T* ≤ U。这就是该结果被称为上界的原因。

    Do not confuse this with a lower bound: the nearest neighbour does not prove that no shorter route exists; it only gives a known feasible route.

    不要将其与下界混淆:最近邻算法并不能证明不存在更短的路线,它只是给出一个已知的可行路线。


    4. Step-by-Step Procedure | 分步流程

    Use the following steps when applying the nearest neighbour algorithm to a distance table or complete graph.

    在距离表或完全图上应用最近邻算法时,请使用以下步骤。

  • Activity Duration (days) Must follow
    Step 1 | 步骤 1 Choose a starting vertex and mark it as visited. | 选择起始顶点并标记为已访问。
    更多咨询请联系16621398022(同微信)

  • Gantt Charts | 甘特图

    📚 Gantt Charts | 甘特图

    Gantt charts are one of the most widely taught planning tools in the Edexcel A-Level Business specification. They help managers schedule tasks, allocate resources and monitor progress over time. Understanding how to construct, interpret and evaluate a Gantt chart is essential for both coursework and examination questions on operations and project management.

    甘特图是 Edexcel A-Level 商务课程中广泛讲授的计划工具之一。它帮助管理者安排任务、分配资源并监控进度。掌握甘特图的绘制、解读与评价方法,对于运营和项目管理相关的课程作业及考试题目都至关重要。


    1. What Are Gantt Charts? | 什么是甘特图?

    A Gantt chart is a horizontal bar chart that represents a project schedule. Each task or activity is shown as a bar positioned along a time axis; the length of the bar indicates the planned duration of that task. The chart is named after Henry Gantt, an American engineer who popularised this visual planning method in the 1910s.

    甘特图是一种表示项目进度的横向条形图。每项任务或活动都用沿时间轴放置的条形表示,条形的长度代表该任务的计划工期。这种图以美国工程师亨利·甘特命名,他在 1910 年代推广了这一可视化计划方法。

    In A-Level Business, Gantt charts are often used in the operations and project management sections. They show the start and finish dates of activities, making it easier to see whether a project is running on schedule.

    在 A-Level 商务课程中,甘特图通常出现在运营与项目管理部分。它们显示活动的开始和结束日期,便于判断项目是否按计划进行。


    2. Key Features of a Gantt Chart | 甘特图的关键特征

    The main components of a Gantt chart include a task list, a time scale, horizontal task bars, milestones and progress indicators. The task list is usually placed on the left-hand vertical axis, while the time scale runs horizontally across the top or bottom.

    甘特图的主要组成部分包括任务清单、时间刻度、横向任务条、里程碑和进度指示。任务清单通常位于左侧纵轴,时间刻度沿顶部或底部横向排列。

    Task bars show the planned duration of each activity. Milestones are represented by diamond shapes and mark important deadlines or decision points. Progress indicators may shade a portion of the bar to show how much of the task has been completed.

    任务条显示每项活动的计划工期。里程碑用菱形表示,标记重要的截止日期或决策点。进度指示可以给条形的一部分上色,显示该任务已完成的比例。

    Some advanced Gantt charts also show dependencies using arrows between bars. This helps managers see which tasks must finish before others can begin.

    一些高级甘特图还用箭头显示任务之间的依赖关系。这有助于管理者看到哪些任务必须先完成,其他任务才能开始。


    3. How to Construct a Gantt Chart | 如何绘制甘特图

    To construct a Gantt chart, a manager should first list all the activities required to complete the project. The next step is to estimate the duration of each activity and identify the order in which tasks must be completed.

    绘制甘特图时,管理者应首先列出完成项目所需的所有活动。下一步是估算每项活动的持续时间,并确定任务必须完成的先后顺序。

    The manager then draws a horizontal time axis, often divided into days, weeks or months. Each activity is represented by a bar starting at its planned start date and ending at its planned finish date. Bars that overlap in time can indicate activities that may be carried out simultaneously.

    然后管理者绘制一条水平时间轴,通常以天、周或月为单位。每项活动用一条从计划开始日期到计划结束日期的条形表示。时间上重叠的条形表示可以同时进行的活动。

    Finally, milestones can be inserted at key dates, and progress can be shaded as the project develops. For exam answers, a clear, labelled sketch is usually more important than a perfect scale drawing.

    最后,可在关键日期插入里程碑,并随着项目推进为进度上色。在考试答题时,清晰标注的示意图通常比精确的比例图更加重要。


    4. Interpreting Gantt Charts | 解读甘特图

    Interpreting a Gantt chart involves reading the start and finish dates of each bar, identifying which activities run at the same time and noticing any gaps between tasks. A gap between the end of one task and the start of the next may suggest idle time or a scheduling problem.

    解读甘特图需要读取每个条形的开始和结束日期,识别哪些活动同时进行,并注意任务之间是否存在间隔。一个任务结束与下一个任务开始之间的间隔可能表明存在闲置时间或排程问题。

    The chart can also show the overall project duration from the first task to the last. If a task has spare time built in, this is called float or slack; the task could be delayed without delaying the whole project.

    甘特图还可以显示从第一项任务到最后一项任务的整个项目工期。如果某项任务有额外时间,这称为浮动时间或缓冲时间;该任务可以延迟而不会拖累整个项目。

    However, a basic Gantt chart does not automatically show the critical path. To identify the critical path, managers often combine the Gantt chart with network diagram information or use software that calculates dependencies and float.

    然而,基础甘特图不会自动显示关键路径。为了识别关键路径,管理者通常将甘特图与网络图信息结合,或使用能够计算依赖关系和浮动时间的软件。


    5. Advantages of Gantt Charts | 甘特图的优点

    One major advantage of Gantt charts is their visual clarity. The bars make it easy for managers, employees and other stakeholders to understand the project schedule at a glance, even without specialist project management training.

    甘特图的一个主要优点是直观清晰。条形图使管理者、员工和其他利益相关者即使没有专业的项目管理培训,也能一目了然地了解项目进度。

    Gantt charts also support resource planning. By seeing when tasks are scheduled, a manager can identify periods of high workload and move tasks or allocate extra staff to avoid bottlenecks.

    甘特图还有助于资源规划。通过查看任务的排期,管理者可以识别高负荷时期,调整任务或分配额外人员,以避免瓶颈。

    They are useful for monitoring progress. By comparing the shaded portion of each bar with the current date, managers can quickly spot tasks that are behind schedule and take corrective action.

    甘特图有助于监控进度。通过比较每条已上色部分与当前日期,管理者可以迅速发现落后于计划的任务并采取纠正措施。

    In addition, Gantt charts improve communication within teams. They provide a shared visual reference for deadlines, milestones and responsibilities, which can reduce misunderstandings and coordination failures.

    此外,甘特图改善了团队内部沟通。它们为截止日期、里程碑和责任提供了共享的视觉参考,从而减少误解和协调失误。


    6. Limitations of Gantt Charts | 甘特图的局限性

    Despite their benefits, Gantt charts have several limitations. For very large or complex projects with hundreds of tasks, the chart can become extremely long and difficult to read on a single page.

    尽管甘特图有很多优点,但也有若干局限性。对于有数百项任务的超大型或复杂项目,图表会变得非常长,难以在一页内阅读。

    A basic Gantt chart does not clearly show the logical dependencies between tasks unless arrows or links are added. Without this information, managers may not fully understand how a delay in one activity affects related activities.

    基本甘特图不会清晰显示任务之间的逻辑依赖关系,除非添加箭头或链接。没有这些信息,管理者可能无法充分理解一项活动的延迟会如何影响相关活动。

    Gantt charts also require regular updating. If the chart is not revised as actual progress changes, it becomes outdated and may mislead decision-makers into thinking the project is still on track.

    甘特图还需要定期更新。如果实际进度发生变化而图表未作修改,它就会过时,可能误导决策者认为项目仍按计划进行。

    Furthermore, the chart focuses mainly on time and does not directly show costs, quality issues or cash flow implications. Managers therefore need to use it alongside other planning and control tools, such as budgets and critical path analysis.

    此外,甘特图主要关注时间,不能直接显示成本、质量问题或现金流影响。因此,管理者需要将其与预算、关键路径分析等其他计划和控制工具结合使用。


    7. Gantt Charts vs Network Diagrams | 甘特图与网络图对比

    Gantt charts and network diagrams are both project planning tools, but they serve different purposes. A network diagram, such as a critical path analysis diagram, emphasises the logical sequence and dependencies of activities, while a Gantt chart emphasises the time schedule and visual timeline.

    甘特图和网络图都是项目计划工具,但用途不同。网络图(如关键路径分析图)强调活动的逻辑顺序和依赖关系,而甘特图强调时间排程和可视化时间线。

    The table below summarises the key differences:

    下表概括了主要区别:

    Feature 更多咨询请联系16621398022(同微信)

  • Critical Activities in Critical Path Analysis | 关键路径分析中的关键活动

    📚 Critical Activities in Critical Path Analysis | 关键路径分析中的关键活动

    In Edexcel A-Level Decision Mathematics, the concept of ‘critical activities’ lies at the heart of project planning and control. Knowing how to identify these activities allows you to determine the shortest possible completion time for a project and to recognise which tasks cannot be delayed without impacting the overall schedule. This article explains the essential theory, calculation methods, and exam techniques for critical activities in critical path analysis.

    在 Edexcel A-Level 决策数学中,“关键活动”的概念是项目规划与控制的核心。掌握如何识别这些活动,可以帮助你确定项目的最短完成时间,并判断哪些任务不能延迟,否则会影响整体进度。本文阐述关键路径分析中关键活动的基本理论、计算方法和考试技巧。


    1. Activity Networks and Dependencies | 活动网络与依赖关系

    A project is modelled as a network of activities, where each activity is represented by a node (in activity-on-node notation, which Edexcel uses) or by an edge (in activity-on-arrow notation). Activities are connected by directed edges that show precedence constraints: an activity cannot start until all its immediate predecessors have been completed.

    项目被建模为一个活动网络,其中每个活动用节点表示(Edexcel 使用活动节点表示法),或用边表示(活动箭线表示法)。活动之间用有向边连接,以显示先后约束:一个活动必须在其所有直接前导活动完成后才能开始。

    • English: Each node typically contains the activity name and its duration.
    • 中文:每个节点通常包含活动名称及其持续时间。
    • English: A dummy activity may be used in activity-on-arrow networks to represent dependencies, but in activity-on-node notation dummies are not needed.
    • 中文:在活动箭线网络中可能使用虚活动来表示依赖关系,但在活动节点表示法中不需要虚活动。

    Understanding the network structure is the first step in finding critical activities, because the timing calculations depend entirely on the precedence relationships and durations.

    理解网络结构是寻找关键活动的第一步,因为时间计算完全依赖于先后关系和持续时间。


    2. Defining a Critical Activity | 关键活动的定义

    A critical activity is an activity for which any delay in its start or finish will cause a delay in the completion of the entire project. In other words, a critical activity has zero total float. Total float is the amount of time an activity can be delayed without affecting the project’s minimum completion time.

    关键活动是指其开始或完成时间的任何延迟都会导致整个项目完成时间延迟的活动。换句话说,关键活动的总浮动时间为零。总浮动时间是指活动可以延迟而不会影响项目最短完成时间的时间量。

    Mathematically, an activity is critical if and only if its total float is zero. The chain of critical activities from the start node to the end node forms the critical path.

    从数学上讲,一个活动是关键的当且仅当其总浮动时间为零。从起始节点到结束节点的关键活动链构成关键路径。


    3. Forward Pass: Earliest Start and Earliest Finish Times | 前向扫描:最早开始与最早完成时间

    The forward pass calculates the earliest start time (EST) and earliest finish time (EFT) for each activity. The earliest start time of the first activity is usually set to 0. For any other activity, the EST is the maximum of the EFTs of all its immediate predecessors.

    前向扫描计算每个活动的最早开始时间(EST)和最早完成时间(EFT)。第一个活动的最早开始时间通常设为 0。对于任何其他活动,其 EST 是其所有直接前导活动 EFT 的最大值。

    EFT = EST + Duration

    The project’s minimum completion time is the maximum EFT of all terminal activities (those with no successors).

    项目的最短完成时间是所有终止活动(没有后继活动的活动)EFT 的最大值。


    4. Backward Pass: Latest Finish and Latest Start Times | 后向扫描:最晚完成与最晚开始时间

    The backward pass begins at the terminal activity or activities. The latest finish time (LFT) of a terminal activity is set equal to the project’s minimum completion time. For any other activity, the LFT is the minimum of the LSTs of all its immediate successors.

    后向扫描从终止活动开始。终止活动的最晚完成时间(LFT)设为项目的最短完成时间。对于任何其他活动,其 LFT 是其所有直接后继活动 LST 的最小值。

    LST = LFT − Duration

    The latest start time (LST) is therefore the latest time an activity can start without delaying the project.

    因此,最晚开始时间(LST)是活动在不延迟项目的前提下可以开始的最晚时间。


    5. Calculating Total Float | 计算总浮动时间

    Total float (TF) for an activity is the maximum amount of time the activity can be delayed beyond its earliest start without delaying the project completion. It can be calculated in two equivalent ways:

    活动的总浮动时间(TF)是指活动可以比最早开始时间延迟的最大时间量,而不会延迟项目完成。它有两种等价的计算方式:

    Total Float = LST − EST

    Total Float = LFT − EFT

    These two differences are always equal for a valid network. If an activity has zero total float, it is critical.

    对于一个有效的网络,这两个差值总是相等的。如果一个活动的总浮动时间为零,则它是关键活动。


    6. Identifying Critical Activities and the Critical Path | 识别关键活动与关键路径

    Once the forward and backward passes are complete, you can identify critical activities by checking which activities have total float equal to zero. The sequence of critical activities forms one or more continuous paths from the start to the end. Every critical path must have the same total duration, equal to the project’s minimum completion time.

    完成前向和后向扫描后,你可以通过检查哪些活动的总浮动时间为零来识别关键活动。关键活动的序列形成从起点到终点的一条或多条连续路径。每条关键路径的总持续时间必须相同,等于项目的最短完成时间。

    In exam questions, you may be asked to state the critical path and its length. Always write the path as a sequence of activity letters, e.g. A → C → E → G, and give the total duration.

    在考试题目中,你可能被要求说明关键路径及其长度。始终将路径写为活动字母序列,例如 A → C → E → G,并给出总持续时间。


    7. Worked Example: A Simple Project | 示例:一个简单项目

    Consider a project with the following activities and durations (in days):

    考虑一个具有以下活动和持续时间(以天为单位)的项目:

    Activity Duration Predecessors
    A 3
    B 4 A
    C 2 A
    D 5 B, C
    E 1 C
    F 3 D, E

    Perform a forward pass. Set EST(A) = 0, so EFT(A) = 0 + 3 = 3. Then EST(B) = EST(C) = 3. EFT(B) = 3 + 4 = 7; EFT(C) = 3 + 2 = 5. Activity D has predecessors B and C, so EST(D) = max(7,5) = 7, EFT(D) = 7 + 5 = 12. Activity E has predecessor C, so EST(E) = 5, EFT(E) = 5 + 1 = 6. Activity F has predecessors D and E, so EST(F) = max(12,6) = 12, EFT(F) = 12 + 3 = 15. The minimum project completion time is 15 days.

    进行前向扫描。设 EST(A) = 0,则 EFT(A) = 0 + 3 = 3。然后 EST(B) = EST(C) = 3。EFT(B) = 3 + 4 = 7;EFT(C) = 3 + 2 = 5。活动 D 的前导是 B 和 C,因此 EST(D) = max(7,5) = 7,EFT(D) = 7 + 5 = 12。活动 E 的前导是 C,因此 EST(E) = 5,EFT(E) = 5 + 1 = 6。活动 F 的前导是 D 和 E,所以 EST(F) = max(12,6) = 12,EFT(F) = 12 + 3 = 15。项目的最短完成时间为 15 天。

    Now perform a backward pass. Set LFT(F) = 15, so LST(F) = 15 − 3 = 12. Activity D has successor F, so LFT(D) = 12, LST(D) = 12 − 5 = 7. Activity E has successor F, so LFT(E) = 12, LST(E) = 12 − 1 = 11. Activity C has successors D and E, so LFT(C) = min(7,11) = 7, LST(C) = 7 − 2 = 5. Activity B has successor D, so LFT(B) = 7, LST(B) = 7 − 4 = 3. Activity A has successors B and C, so LFT(A) = min(3,5) = 3, LST(A) = 3 − 3 = 0.

    现在进行后向扫描。设 LFT(F) = 15,则 LST(F) = 15 − 3 = 12。活动 D 的后继是 F,所以 LFT(D) = 12,LST(D) = 12 − 5 = 7。活动 E 的后继是 F,所以 LFT(E) = 12,LST(E) = 12 − 1 = 11。活动 C 的后继是 D 和 E,因此 LFT(C) = min(7,11) = 7,LST(C) = 7 − 2 = 5。活动 B 的后继是 D,所以 LFT(B) = 7,LST(B) = 7 − 4 = 3。活动 A 的后继是 B 和 C,因此 LFT(A) = min(3,5) = 3,LST(A) = 3 − 3 = 0。

    Finally, calculate total floats: A: 0 − 0 = 0; B: 3 − 3 = 0; C: 5 − 3 = 2; D: 7 − 7 = 0; E: 11 − 5 = 6; F: 12 − 12 = 0. The critical activities are A, B, D, F. The critical path is A → B → D → F, with length 15 days.

    最后计算总浮动时间:A:0 − 0 = 0;B:3 − 3 = 0;C:5 − 3 = 2;D:7 − 7 = 0;E:11 − 5 = 6;F:12 − 12 = 0。关键活动为 A、B、D、F。关键路径为 A → B → D → F,长度为 15 天。


    8. Properties of the Critical Path | 关键路径的性质

    The critical path is the longest path through the network in terms of total duration. It determines the minimum time needed to complete the project. If any critical activity is delayed by a certain amount of time, the project completion will be delayed by the same amount, unless corrective action is taken.

    关键路径是网络中总持续时间最长的路径。它决定了完成项目所需的最短时间。如果任何关键活动被延迟一定时间,项目完成时间将延迟相同时间,除非采取纠正措施。

    There may be more than one critical path in a network. When multiple critical paths exist, all of them must have the same total duration. Activities that are on at least one critical path are critical; activities that are on no critical path have positive float and are non-critical.

    网络中可能存在多条关键路径。当存在多条关键路径时,它们必须具有相同的总持续时间。位于至少一条关键路径上的活动是关键活动;不在任何关键路径上的活动具有正浮动时间,是非关键活动。


    9. Common Mistakes and Exam Tips | 常见错误与考试提示

    Students often confuse earliest and latest times, especially in the backward pass. Remember that the backward pass works from the end to the start, and you must take the minimum of successors’ LSTs when calculating an activity’s LFT. A common error is to use the maximum instead.

    学生经常混淆最早和最晚时间,尤其是在后向扫描中。请记住,后向扫描是从结束到开始进行的,并且在计算活动的 LFT 时必须取后继活动 LST 的最小值。一个常见错误是使用了最大值。

    Another frequent mistake is forgetting that total float can be calculated either as LST − EST or LFT − EFT. Always check both values; if they are not equal, you have made an arithmetical error.

    另一个常见错误是忘记总浮动时间可以通过 LST − EST 或 LFT − EFT 计算。始终检查两个值;如果它们不相等,则说明存在算术错误。

    When writing the critical path in the exam, always list activities in their correct sequence and include arrows between them. Also, clearly state the total duration, as this is often worth a mark.

    在考试中书写关键路径时,始终按正确顺序列出活动并在它们之间加上箭头。同时,清楚地说明总持续时间,因为这通常值得一个分数。


    10. The Role of Critical Activities in Resource Management | 关键活动在资源管理中的作用

    Identifying critical activities is not only an exam skill; it is also essential for real-world project management. Project managers focus most attention on critical activities because any delay in these tasks directly extends the project deadline. Non-critical activities, with their positive float, can be scheduled flexibly within their float windows, allowing for better resource levelling.

    识别关键活动不仅是一项考试技能,它对现实世界的项目管理也至关重要。项目管理者最关注关键活动,因为这些任务的任何延误都会直接延长项目截止日期。具有正浮动时间的非关键活动可以在其浮动窗口内灵活安排,从而更好地进行资源平衡。

    If resources are over-allocated, a manager may decide to delay a non-critical activity to reduce peak demand. However, delaying a critical activity is never an option without extending the whole project. Understanding this distinction is a key learning outcome in Decision Mathematics.

    如果资源分配过度,管理者可以决定延迟非关键活动以减少峰值需求。然而,延迟关键活动从来不是一个可选项,因为它会延长整个项目。理解这一区别是决策数学中的一个关键学习成果。


    11. Summary and Key Formulae | 总结与关键公式

    To summarise, the steps to find critical activities are:

    总结起来,寻找关键活动的步骤是:

    • English: Draw the activity network using precedence information.
    • 中文:使用先后关系信息绘制活动网络。
    • English: Perform a forward pass to calculate EST and EFT.
    • 中文:执行前向扫描来计算 EST 和 EFT。
    • English: Perform a backward pass to calculate LFT and LST.
    • 中文:执行后向扫描来计算 LFT 和 LST。
    • English: Compute total float for each activity.
    • 中文:计算每个活动的总浮动时间。
    • English: Identify activities with zero total float as critical.
    • 中文:将总浮动时间为零的活动识别为关键活动。
    • English: Trace the critical path(s) along these activities.
    • 中文:沿着这些活动追踪关键路径。

    Total Float = LST − EST = LFT − EFT

    Mastering these calculations unlocks a significant portion of the Edexcel Decision Mathematics examination, and provides a powerful tool for analysing real-life projects.

    掌握这些计算可以解锁 Edexcel 决策数学考试的一个重要部分,并为分析现实生活中的项目提供强大的工具。

    Published by TutorHao | Decision Mathematics 1 Revision Series | aleveler.com

    更多咨询请联系16621398022(同微信)

  • Dummy Activities in Critical Path Analysis | 关键路径分析中的虚拟活动

    📚 Dummy Activities in Critical Path Analysis | 关键路径分析中的虚拟活动

    In Edexcel A-Level Decision Mathematics 1 (D1), critical path analysis is a vital modelling tool for scheduling complex projects. One of the most frequently examined and commonly misunderstood ideas is the dummy activity. A dummy activity has zero duration and uses no resources, but it is essential for preserving logical dependencies in an activity-on-arc network. This article explains what dummy activities are, when to use them, how to draw them correctly, and how to avoid common mistakes.

    在 Edexcel A-Level 决策数学 1(D1)中,关键路径分析是为复杂项目排程的重要建模工具。虚拟活动(dummy activity)是考试中经常出现且常被误解的概念之一。虚拟活动的持续时间为零,也不消耗资源,但它在活动-弧线网络中对保持逻辑依赖关系至关重要。本文将解释什么是虚拟活动、何时使用、如何正确绘制以及如何避免常见错误。


    1. What Is a Dummy Activity? | 什么是虚拟活动?

    In an activity-on-arc network, each real activity is drawn as a solid arrow from one event node to another. A dummy activity is drawn as a dashed arrow and is used only to show a dependency. It has no duration, no cost, and no resource requirement. In Edexcel D1, dummies are mainly needed to ensure that the network correctly represents every precedence relationship without violating the rules of graph drawing.

    在活动-弧线网络中,每个真实活动用从一个事件节点指向另一个事件节点的实线箭头表示。虚拟活动用虚线箭头表示,仅用于显示依赖关系。它的持续时间为零,没有成本,也不需要资源。在 Edexcel D1 中,虚拟活动主要用于确保网络正确表示所有先后关系,同时不违反图形绘制规则。


    2. Why Use Dummy Activities? | 为什么要使用虚拟活动?

    Dummy activities solve two graphical and logical problems. First, if two or more activities share exactly the same start node and end node, the diagram would have parallel edges with the same endpoint pair, which makes the activities impossible to identify uniquely. Second, when an activity depends on two predecessors but another activity depends on only one of those predecessors, a simple arrow cannot express this partial dependency without introducing a false relationship.

    虚拟活动解决两个图形和逻辑问题。第一,如果两个或多个活动具有完全相同的开始节点和结束节点,图中就会出现具有相同端点对的平行边,这使活动无法被唯一标识。第二,当一个活动依赖于两个前置活动,而另一个活动只依赖于其中一个前置活动时,简单的箭头无法表达这种部分依赖关系,否则会引入虚假的逻辑关系。


    3. The Two Classical Cases for Dummies | 使用虚拟活动的两种经典情形

    Case 1: Unique endpoint pair. Suppose activities A and B both start at node 1 and finish at node 2. To separate them, draw A from 1 to 3, draw B from 1 to 2, and insert a dummy from 2 to 3. Now A and B have different end nodes, and the dummy from 2 to 3 means that the event at node 3 depends on B as well; this does not add any time or resource.

    情形一:唯一端点对。假设活动 A 和 B 都从节点 1 开始并在节点 2

    Published by TutorHao | A-Level Revision Series | aleveler.com

    更多咨询请联系16621398022(同微信)

  • Chapter Review 5: Straight Line Graphs | 第五章复习:直线图

    📚 Chapter Review 5: Straight Line Graphs | 第五章复习:直线图

    This revision guide covers the key ideas in Edexcel A-Level Pure Mathematics Chapter Review 5: straight line graphs. You will revise gradient, midpoint, distance, equations of lines, parallel and perpendicular conditions, intersections, and modelling.

    本复习指南涵盖 Edexcel A-Level 纯数学第五章复习:直线图。你将复习斜率、中点、距离、直线方程、平行与垂直条件、交点以及建模。


    1. Gradient and Midpoint | 斜率与中点

    The gradient of a straight line joining two points is found by dividing the change in y by the change in x. Always subtract the coordinates in the same order.

    连接两点的直线斜率用 y 的变化量除以 x 的变化量来计算。两个坐标必须按相同顺序相减。

    m = (y₂ − y₁) / (x₂ − x₁)

    The midpoint is the point exactly halfway between the two endpoints. Its coordinates are the average of the x-coordinates and the average of the y-coordinates.

    中点位于两个端点正中间。它的坐标是 x 坐标的平均值和 y 坐标的平均值。

    M = ((x₁ + x₂)/2, (y₁ + y₂)/2)

    A positive gradient rises from left to right, while a negative gradient falls. Zero gradient gives a horizontal line, and a vertical line has undefined gradient.

    正斜率从左到右上升,负斜率从左到右下降。斜率为零时直线水平,垂直直线的斜率无定义。


    2. Equation of a Straight Line | 直线方程

    The equation y = mx + c uses m for gradient and c for the y-intercept, which is the point where the line crosses the y-axis.

    方程 y = mx + c 中 m 表示斜率,c 表示 y 轴截距,即直线与 y 轴相交的点。

    y = mx + c

    When you know one point and the gradient, use the point-gradient form y − y₁ = m(x − x₁). You can then rearrange it into the required form.

    当已知一个点和斜率时,使用点斜式 y − y₁ = m(x − x₁)。然后可以整理成题目要求的形式。

    y − y₁ = m(x − x₁)

    To find the equation when given two points, first find the gradient, then

    Published by TutorHao | A-Level Revision Series | aleveler.com

    更多咨询请联系16621398022(同微信)

  • Using a Minimum Spanning Tree Method to Find a Lower Bound | 用最小生成树方法求下界

    📚 Using a Minimum Spanning Tree Method to Find a Lower Bound | 用最小生成树方法求下界

    In Edexcel Decision Mathematics 1, the travelling salesperson problem (TSP) asks for the shortest possible tour that visits every vertex exactly once and returns to the start. Finding the exact optimal tour can be time-consuming, so we use upper and lower bounds to narrow down the possible tour length. A lower bound is a value that no valid tour can have a weight below. This article explains how a minimum spanning tree (MST) can be used to construct a reliable lower bound for the TSP.

    在 Edexcel 决策数学 1 中,旅行商问题 (TSP) 要求找到一条访问每个顶点恰好一次并返回起点的最短巡回路线。找到确切的最优巡回路线可能非常耗时,因此我们使用上界和下界来缩小可能的巡回路线长度范围。下界是任何有效巡回路线的权重都不能低于的值。本文解释如何使用最小生成树 (MST) 为 TSP 构造一个可靠的下界。


    1. The Travelling Salesperson Problem and Bounds | 旅行商问题与界限

    The TSP is a classic optimisation problem. A tour must include every vertex once and return to the starting point, so it forms a Hamiltonian cycle. In a complete graph with n vertices, there are (n − 1)! / 2 possible tours, which makes complete enumeration impractical for large n.

    TSP 是一个经典的优化问题。一条巡回路线必须包含每个顶点一次并返回起点,因此它形成一个哈密顿环。在具有 n 个顶点的完全图中,共有 (n − 1)! / 2 条可能的巡回路线,这使得对于较大的 n,完全枚举是不切实际的。

    To solve TSP problems in exam conditions, we usually find an upper bound using a heuristic method such as the nearest neighbour algorithm, and a lower bound using the minimum spanning tree method. If the upper bound and lower bound are equal, then the tour used to find the upper bound is provably optimal.

    在考试条件下解决 TSP 问题时,我们通常使用启发式方法(如最近邻算法)求上界,使用最小生成树方法求下界。如果上界和下界相等,那么用于求上界的巡回路线就是可证明的最优解。


    2. Why a Minimum Spanning Tree Gives a Lower Bound | 为什么最小生成树给出下界

    Consider any optimal TSP tour. If we delete one vertex from the tour, we also delete the two edges that connect that vertex to its two neighbours in the tour. The remaining edges still connect all the other vertices, and because the original tour was a cycle, removing two edges and one vertex leaves behind a path, which is a special type of tree.

    考虑任意最优 TSP 巡回路线。如果我们从巡回路线中删除一个顶点,同时也会删除该顶点与其巡回路线中两个相邻顶点连接的两条边。剩下的边仍然连接所有其他顶点,并且因为原始巡回路线是一个环,删除两条边和一个顶点后会留下一条路径,而路径是一种特殊类型的树。

    This remaining structure is a spanning tree on the vertices that were not deleted. Its total weight must be at least the weight of the minimum spanning tree (MST) on those vertices. The two deleted edges must have total weight at least the sum of the two shortest possible edges that could connect the deleted vertex back to the graph. Adding these two minimum contributions gives a valid lower bound for the whole tour.

    剩余的结构是在未删除顶点上的一棵生成树。它的总权重必须至少是这些顶点上最小生成树 (MST) 的权重。被删除的两条边的总权重必须至少是能够将被删除顶点连接回图的两条最短可能边的权重之和。将这两个最小贡献相加,就得到了整个巡回路线的一个有效下界。


    3. The Vertex-Deletion Technique | 删除顶点技巧

    The standard Edexcel D1 method is to choose one vertex, delete it from the graph, and find the MST of the remaining vertices. Then we add the weights of the two smallest edges that were incident to the deleted vertex. The result is a lower bound for the TSP.

    标准的 Edexcel D1 方法是选择一个顶点,将其从图中删除,然后求剩余顶点的 MST。接着,我们加上与被删除顶点关联的两条最小边的权重。结果就是 TSP 的一个下界。

    This technique works because any TSP tour must enter and leave the deleted vertex exactly once, using two incident edges. The rest of the tour forms a spanning tree on the remaining vertices. Therefore, the tour weight is always greater than or equal to the sum of the MST weight and the two shortest incident edges.

    这种技巧之所以有效,是因为任何 TSP 巡回路线必须恰好进入和离开被删除顶点一次,使用两条关联边。巡回路线的其余部分在剩余顶点上形成一棵生成树。因此,巡回路线权重总是大于或等于 MST 权重与两条最短关联边之和。


    4. Step 1: Choose a Vertex to Delete | 步骤1:选择要删除的顶点

    You can choose any vertex to delete, and the method will still produce a lower bound. However, some vertices give better bounds than others. In an exam question, you may be told which vertex to delete, or you may be asked to try several vertices and select the largest lower bound.

    你可以选择任意顶点删除,该方法仍会产生一个下界。但是,有些顶点比其他顶点给出更好的下界。在考试题中,题目可能会指定要删除哪个顶点,或者可能要求你尝试多个顶点并选择最大的下界。

    Choosing a vertex with relatively large edges to the rest of the graph is often useful because the two shortest edges from it will still be included in the bound. If a vertex has one very small edge, deleting it may produce a weak bound, so repeating the process for other vertices is important.

    选择与图中其他顶点之间边权相对较大的顶点通常很有用,因为从它出发的两条最短边仍会被包含在下界中。如果某个顶点有一条非常小的边,删除它可能会产生较弱的下界,因此对其他顶点重复此过程非常重要。


    5. Step 2: Find the MST of the Remaining Vertices | 步骤2:求剩余顶点的最小生成树

    After deleting the chosen vertex, apply Kruskal’s algorithm or Prim’s algorithm to the remaining vertices. With Kruskal’s algorithm, list all remaining edges in increasing order of weight, then repeatedly add the smallest edge that does not form a cycle until all remaining vertices are connected.

    删除所选顶点后,对剩余顶点应用 Kruskal 算法或 Prim 算法。使用 Kruskal 算法时,按权重递增的顺序列出所有剩余边,然后反复添加不会形成环的最小边,直到所有剩余顶点都连通。

    It is essential to use only the edges that do not involve the deleted vertex. The MST weight is the sum of the selected edge weights. A tree on n vertices needs exactly n − 1 edges, so if five vertices remain after deletion, the MST must contain four edges.

    必须只使用不涉及被删除顶点的边。MST 权重是所选边权重的总和。n 个顶点上的树恰好需要 n − 1 条边,因此如果删除后剩余五个顶点,则 MST 必须包含四条边。


    6. Step 3: Add the Two Shortest Edges to the Deleted Vertex | 步骤3:加上连接到被删除顶点的两条最短边

    From the original graph, identify all edges incident to the deleted vertex. Choose the two with the smallest weights. It does not matter whether these two edges share the same endpoint or not, because they simply represent the cheapest possible way to enter and leave the deleted vertex.

    从原图中找出与被删除顶点关联的所有边。选择权重最小的两条边。这两条边是否共享同一个端点并不重要,因为它们只是代表进入和离开被删除顶点的最便宜方式。

    The lower bound is then calculated as: Lower bound = MST weight of remaining vertices + weight of shortest incident edge + weight of second shortest incident edge.

    Lower bound = MST weight + w₁ + w₂

    其中 w₁ 和 w₂ 是与被删除顶点关联的两条最短边的权重。不要在 MST 中重复计算这些边,因为 MST 只包含剩余顶点之间的边。


    7. Worked Example: Finding a Lower Bound | 例题:求一个下界

    Consider a complete graph on six vertices A, B, C, D, E, F. The edge weights are shown in the table below. We will delete vertex A and find a lower bound for the TSP.

    考虑一个六个顶点 A、B、C、D、E、F 的完全图。边权重如下表所示。我们将删除顶点 A 并求 TSP 的一个下界。

    Edge Weight Edge Weight
    AB 5 BD 6
    AC 7 BE 7
    AD 9 BF 5
    AE 4 CD 4
    AF 6 CE 3
    BC 8 CF 9
    DE 5
    DF 7
    EF 6

    After deleting vertex A, the remaining vertices are B, C, D, E, F. The edges among these vertices in ascending order of weight are: CE = 3, CD = 4, DE = 5, BF = 5, BD = 6, EF = 6, BE = 7, DF = 7, BC = 8, CF = 9.

    删除顶点 A 后,剩余顶点为 B、C、D、E、F。这些顶点之间的边按权重升序排列为:CE = 3、CD = 4、DE = 5、BF = 5、BD = 6、EF = 6、BE = 7、DF = 7、BC = 8、CF = 9。

    Using Kruskal’s algorithm, we select CE = 3 and CD = 4. The next smallest is DE = 5, but adding DE would form the cycle C-D-E, so it is rejected. We then select BF = 5 and BD = 6. At this point we have four edges for five vertices, so the MST is complete. The total MST weight is 3 + 4 + 5 + 6 = 18.

    使用 Kruskal 算法,我们选择 CE = 3 和 CD = 4。下一个最小边是 DE = 5,但添加 DE 会形成环 C-D-E,因此被拒绝。接着我们选择 BF = 5 和 BD = 6。此时五个顶点已有四条边,因此 MST 完成。MST 总权重为 3 + 4 + 5 + 6 = 18。

    The edges incident to deleted vertex A have weights AB = 5, AC = 7, AD = 9, AE = 4, AF = 6. The two shortest are AE = 4 and AB = 5, with total weight 9.

    与被删除顶点 A 关联的边权重为 AB = 5、AC = 7、AD = 9、AE = 4、AF = 6。两条最短边是 AE = 4 和 AB = 5,总权重为 9。

    Therefore, the lower bound for this TSP is MST weight 18 + two shortest incident edge weights 9 = 27.

    Lower bound = 18 + 4 + 5 = 27

    因此,该 TSP 的下界为 MST 权重 18 + 两条最短关联边权重 9 = 27。


    8. Improving the Bound by Trying Different Vertices | 尝试不同顶点改进下界

    Because the lower bound depends on which vertex is deleted, deleting a different vertex may produce a larger lower bound. A larger lower bound is better because it is closer to the true optimal tour length. You should repeat the MST method for several vertices and record each bound.

    由于下界取决于删除哪个顶点,删除不同的顶点可能会产生更大的下界。更大的下界更好,因为它更接近真正的最优巡回路线长度。你应该对多个顶点重复 MST 方法并记录每个下界。

    For example, deleting vertex B would require finding the MST of A, C, D, E, F and adding the two shortest edges incident to B. The procedure is identical, but the resulting value may be higher or lower than 27. The best lower bound is the maximum of all the bounds found.

    例如,删除顶点 B 需要求 A、C、D、E、F 的 MST,并加上与 B 关联的两条最短边。过程完全相同,但得到的值可能高于或低于 27。最佳下界是找到的所有下界中的最大值。


    9. Using the Maximum Lower Bound | 使用最大下界

    If you have also found an upper bound for the same TSP using a heuristic such as the nearest neighbour algorithm, compare the two values. The maximum lower bound and the minimum upper bound give an interval that must contain the optimal tour length.

    如果你还使用最近邻等启发式方法找到了同一 TSP 的上界,请比较这两个值。最大下界和最小上界给出了一个必定包含最优巡回路线长度的区间。

    If the maximum lower bound equals the minimum upper bound, then that common value is the exact optimal tour weight. In exam problems, this equality often confirms that the tour used for the upper bound is optimal.

    如果最大下界等于最小上界,那么这个共同值就是确切的最优巡回路线权重。在考试题中,这种相等通常可以确认用于求上界的巡回路线是最优的。


    10. Common Mistakes and Exam Tips | 常见错误与考试提示

    One common mistake is to include the deleted vertex in the MST calculation. Remember that the MST is found only on the remaining vertices after deletion. Another error is to add only one edge back to the deleted vertex, but a TSP tour must

    Published by TutorHao | A-Level Revision Series | aleveler.com

    更多咨询请联系16621398022(同微信)

  • The Classical and Practical Travelling Salesman Problems | 经典与实用旅行商问题

    📚 The Classical and Practical Travelling Salesman Problems | 经典与实用旅行商问题

    The travelling salesman problem is one of the most important optimisation problems in decision mathematics. It asks for the cheapest closed route that starts at a given point, visits a set of locations, and returns to the starting point. In the Edexcel specification, the problem is studied in two forms: the classical travelling salesman problem, where every vertex must be visited exactly once, and the practical travelling salesman problem, where repeated visits are allowed because the network may not be complete.

    旅行商问题是决策数学中最重要的优化问题之一。它要求找出一条成本最低的闭合路线:从给定点出发,访问一组地点后返回起点。在Edexcel考试大纲中,该问题分为两种形式:经典旅行商问题要求每个顶点恰好访问一次;实用旅行商问题则允许重复访问,因为实际网络可能不是完全图。


    1. What Is the Travelling Salesman Problem? | 什么是旅行商问题?

    The travelling salesman problem, often abbreviated as TSP, is a routing problem in a weighted network. A salesperson must leave a home city, visit a list of cities, and return home. The aim is to make the total distance or cost as small as possible.

    旅行商问题通常缩写为TSP,是加权网络中的路线问题。销售员必须离开出发城市,访问一系列城市后回家。目标是使总距离或总成本尽可能小。

    In Edexcel Decision Mathematics, a solution is called a tour or Hamiltonian cycle if it visits every vertex exactly once and returns to the start. The classical and practical versions differ in how strictly this ‘exactly once’ rule is applied.

    在Edexcel决策数学中,如果一条路线恰好访问每个顶点一次并返回起点,则称为一条回路或哈密顿回路。经典版和实用版在“恰好访问一次”这一规则的严格程度上有所不同。


    2. Classical TSP: Definition and Assumptions | 经典TSP:定义与假设

    The classical travelling salesman problem assumes a complete network. This means there is a direct edge between every pair of vertices. Each edge has a known weight, such as distance, time, or cost, and the network is usually undirected and symmetric.

    经典旅行商问题假设网络是完全的。这意味着任意两个顶点之间都有一条直接的边。每条边都有已知的权重,例如距离、时间或成本,并且网络通常是无向且对称的。

    A valid classical tour is a Hamiltonian cycle. It must visit every vertex exactly once and return to the starting vertex. The objective is to find the Hamiltonian cycle with the smallest total weight.

    一条有效的经典回路是哈密顿回路。它必须恰好访问每个顶点一次并返回起始顶点。目标是找到总权重最小的哈密顿回路。

    For a complete graph with n vertices, there are (n − 1)! / 2 possible Hamiltonian cycles if the graph is undirected. Checking every cycle quickly becomes impractical, so algorithms such as nearest neighbour and minimum spanning tree bounds are used.

    对于有n个顶点的完全无向图,共有(n − 1)! / 2条可能的哈密顿回路。逐条检查很快就会变得不现实,因此通常使用最近邻算法和最小生成树下界等方法。


    3. Practical TSP: When the Network Is Not Complete | 实用TSP:网络不完整时

    In real applications, the network often is not complete. Some pairs of locations may have no direct road or rail link. The practical travelling salesman problem allows the route to travel along any available edges and to visit vertices more than once.

    在实际应用中,网络往往不是完全的。某些地点之间可能没有直接的道路或铁路连接。实用旅行商问题允许路线使用任意可用边,并且可以多次经过顶点。

    The only requirements are that the route must visit every vertex at least once, return to the starting vertex, and have the smallest possible total weight. A practical route is therefore not necessarily a Hamiltonian cycle.

    唯一的要求是路线必须至少访问每个顶点一次,返回起始顶点,并且总权重尽可能小。因此,实用路线不一定是哈密顿回路。


    4. Converting a Practical TSP into a Classical TSP | 将实用TSP转化为经典TSP

    A practical travelling salesman problem can be converted into a classical travelling salesman problem by building a complete shortest-distance table. First, use Dijkstra’s algorithm to find the shortest path between every pair of vertices in the original network.

    实用旅行商问题可以通过构建完全最短距离表转化为经典旅行商问题。首先,使用Dijkstra算法求出原网络中每对顶点之间的最短路径。

    Record these shortest distances in a square table. This table is complete because every pair of vertices now has a value. The shortest distances also satisfy the triangle inequality, which means the direct table value between two vertices is no greater than any indirect route through another vertex.

    将这些最短距离记录在方阵表格中。因为任意两个顶点现在都有一个数值,所以该表格是完全的。最短距离还满足三角不等式,即两个顶点之间的表格值不大于经过其他顶点的任何间接路线。

    Once the complete shortest-distance table is formed, solve it as a classical TSP. Each selected edge in the classical tour corresponds to a shortest path in the original practical network, so the route can be translated back.

    一旦形成完全最短距离表,就可以按经典TSP求解。经典回路中选定的每条边对应原实用网络中的一条最短路径,因此可以将路线翻译回原网络。


    5. Finding an Upper Bound with the Nearest Neighbour Algorithm | 用最近邻算法求上界

    Any valid tour gives an upper bound for the optimal tour length. The nearest neighbour algorithm is a quick constructive method. It starts at a chosen vertex, then repeatedly moves to the nearest unvisited vertex, and finally returns to the start.

    任何有效回路都给出最优回路长度的上界。最近邻算法是一种快速的构造方法。它从选定的顶点出发,然后反复移动到最近的未访问顶点,最后返回起点。

    The total weight of this tour is an upper bound. Starting from different vertices can produce different tours, so it is useful to try several starting points and take the smallest resulting tour as the best upper bound.

    该回路的总权重就是一个上界。从不同顶点出发可能得到不同的回路,因此通常应尝试几个起点,并取所得回路中最小的一个作为最佳上界。

    For a nearest neighbour tour T, we write:

    对于最近邻回路T,可写为:

    Upper bound = total weight of T


    6. Finding a Lower Bound Using a Minimum Spanning Tree | 用最小生成树求下界

    A lower bound can be calculated by deleting one vertex, say A. In any Hamiltonian cycle, the part connecting all vertices except A must contain a spanning tree of those remaining vertices. Therefore its weight is at least the weight of the minimum spanning tree, or MST, on the remaining vertices.

    下界可以通过删除一个顶点(例如A)来计算。在任意哈密顿回路中,连接除A以外所有顶点的部分必然包含这些剩余顶点的一棵生成树。因此,其权重至少等于剩余顶点上最小生成树(MST)的权重。

    The tour must also enter and leave A using two distinct edges. The total weight of these two edges is at least the sum of the two smallest edges incident to A. This gives the formula:

    回路还必须使用两条不同的边进出A。这两条边的总权重至少等于与A关联的两条最小边的权重之和。由此得到公式:

    Lower bound = MST weight on V − {A} + two smallest edge weights from A

    This value is a lower bound for the optimal classical tour length. For practical TSP, the same calculation is applied to the complete shortest-distance table.

    该值是经典最优回路长度的下界。对于实用TSP,同样的计算应用于完全最短距离表。


    7. Choosing the Best Lower Bound | 选择最佳下界

    Since any vertex can be deleted in the lower bound calculation, you should repeat the process for several different vertices. The largest lower bound obtained is the most useful, because it is closest to the optimal value.

    由于在下界计算中可以删除任意顶点,因此应对多个不同顶点重复该过程。所得的最大下界最有用,因为它最接近最优值。

    If an upper bound and a lower bound are equal, the corresponding tour is proven optimal. This is an important technique in exam questions that ask you to justify optimality.

    如果上界与下界相等,则对应的回路被证明是最优的。这是考试题中要求证明最优性的重要技巧。


    8. Worked Example: Classical TSP | 经典TSP例题

    Five vertices A, B, C, D, E have the following symmetric distance table in kilometres:

    五个顶点A、B、C、D、E的对称距离表如下,单位为公里:

    A B C 更多咨询请联系16621398022(同微信)

  • Using a Minimum Spanning Tree Method to Find an Upper Bound | 用最小生成树方法求上界

    📚 Using a Minimum Spanning Tree Method to Find an Upper Bound | 用最小生成树方法求上界

    In the Edexcel A-Level Further Mathematics Decision Mathematics 1 module, the travelling salesman problem requires you to find a short route visiting every vertex exactly once and returning to the start. Since exact methods are often too slow, exam questions ask for upper and lower bounds for the optimal tour length. This article explains how to use a minimum spanning tree method to construct a valid tour and hence obtain an upper bound.

    在 Edexcel A-Level 进阶数学 D1 模块中,旅行商问题要求找到一条访问每个顶点恰好一次并返回起点的最短路线。由于精确方法通常太慢,考试题会要求求出最优路线长度的上界和下界。本文讲解如何使用最小生成树方法构造一条有效路线,从而得到一个上界。


    1. What the Method Is For | 方法用途

    A minimum spanning tree method for an upper bound is used on a complete weighted network, where every pair of vertices is joined by an edge. The goal is to build a Hamiltonian cycle, which is a cycle visiting every vertex exactly once before returning to the start. The total weight of that cycle is an upper bound for the travelling salesman problem because the optimal tour cannot be longer than any feasible tour you find.

    求上界的最小生成树方法用于完全加权网络,即每对顶点之间都有一条边相连。目标是构建一个哈密顿回路,也就是访问每个顶点恰好一次并返回起点的回路。该回路的总权重就是旅行商问题的一个上界,因为最优路线不可能比你找到的任何可行路线更长。


    2. Key Idea: From MST to Hamiltonian Cycle | 核心思想:从最小生成树到哈密顿回路

    First find a minimum spanning tree of the network using Prim’s algorithm or Kruskal’s algorithm. Then traverse this tree in a depth-first search, recording each vertex the first time you visit it. Finally, return directly from the last recorded vertex to the starting vertex. This produces a Hamiltonian cycle using original graph edges, and its length is an upper bound.

    首先使用 Prim 算法或 Kruskal 算法找到网络的最小生成树。然后对这个树进行深度优先搜索,记录每个顶点第一次被访问的顺序。最后从最后一个记录的顶点直接返回起点。这样就得到一条使用原图边权的哈密顿回路,其长度即为一个上界。

    The method works because a minimum spanning tree connects all vertices cheaply. The depth-first traversal converts that cheap connection structure into an ordered vertex list, and the final direct return closes the cycle. It does not always give the optimal tour, but it always gives a feasible tour.

    该方法之所以有效,是因为最小生成树以较低成本连接了所有顶点。深度优先遍历将这个低成本的连接结构转化为一个有序顶点列表,最后的直接返回闭合了回路。它不一定给出最优路线,但总能给出可行路线。


    3. Step 1: Find the Minimum Spanning Tree | 第一步:求最小生成树

    Use Kruskal’s algorithm by sorting all edges in ascending order of weight. Add the shortest edge that does not create a cycle. Continue until all vertices are connected and exactly n − 1 edges have been added, where n is the number of vertices. Alternatively, use Prim’s algorithm from a chosen starting vertex.

    使用 Kruskal 算法时,将所有边按权值从小到大排序。依次加入不形成回路的最短边。继续这一过程,直到所有顶点都被连接并且恰好加入了 n − 1 条边,其中 n 是顶点数。也可以从选定的起点使用 Prim 算法。

    In the worked example below, the vertices are A, B, C, D, E, and the edge weights are shown in the table. Kruskal’s algorithm gives the MST edges BC, AC, CE, CD with total weight 2 + 3 + 3 + 4 = 12.

    在下面的示例中,顶点为 A、B、C、D、E,边权如下表所示。Kruskal 算法得到最小生成树的边为 BC、AC、CE、CD,总权重为 2 + 3 + 3 + 4 = 12。


    4. Step 2: Depth-First Search of the MST | 第二步:对最小生成树进行深度优先搜索

    A depth-first search starts at a chosen vertex and follows one branch of the tree as far as possible before backtracking. When a vertex has unvisited neighbours, go to the next unvisited neighbour. When a dead end is reached, backtrack to the most recent vertex that still has an unvisited neighbour.

    深度优先搜索从选定的顶点开始,沿着树的一个分支尽可能深入,然后再回溯。当一个顶点还有未访问的邻居时,就前往下一个未访问的邻居。当到达死胡同时,回溯到最近一个仍有未访问邻居的顶点。

    At each vertex, the order of neighbour choice may be alphabetical, by increasing edge weight, or as specified in the question. Different choices can produce different tours, so always state the order you are using.

    在每个顶点处,邻居的选择顺序可以是字母顺序、按边权从小到大,或者题目指定的顺序。不同的选择会产生不同的路线,因此务必说明你使用的顺序。


    5. Step 3: List Vertices in First-Visit Order | 第三步:按首次访问顺序列出顶点

    During the depth-first search, write down a vertex only when it is visited for the first time. Do not write it again when backtracking through it. The final list is the order of first visits. This list determines your candidate Hamiltonian cycle.

    在深度优先搜索过程中,仅在顶点第一次被访问时写下它。回溯经过该顶点时不要再次记录。最终列表就是首次访问顺序。该列表决定了候选的哈密顿回路。

    For example, starting at A and using alphabetical order at C, the depth-first search of the MST with edges A–C, C–B, C–D, C–E gives the first-visit order A, C, B, D, E.

    例如,从 A 出发,在 C 处按字母顺序选择,对边为 A–C、C–B、C–D、C–E 的最小生成树进行深度优先搜索,得到首次访问顺序 A、C、B、D、E。


    6. Step 4: Close the Cycle and Calculate Length | 第四步:闭合回路并计算长度

    After listing all vertices, return directly from the last vertex to the first vertex. This direct edge must exist because the network is complete. Then calculate the tour length by adding the weights of the consecutive edges in the cycle.

    列出所有顶点后,从最后一个顶点直接返回到第一个顶点。由于网络是完全的,这条直接边一定存在。然后将回路中相邻边的权值相加,计算路线长度。

    The tour length is an upper bound for the optimal travelling salesman tour. Write the answer as: optimal tour length ≤ tour length found.

    该路线长度是最优旅行商路线的一个上界。答案写作:最优路线长度 ≤ 所求路线长度。


    7. Worked Example: Distance Table | 示例:距离表

    The following complete network has five vertices A, B, C, D, E. Use the minimum spanning tree method to find an upper bound for the optimal tour length.

    以下完全网络有五个顶点 A、B、C、D、E。使用最小生成树方法求最优路线长度的上界。

    Vertex A B C D E
    A 4 3 5 6
    B 4 2 7 5
    C 3 2 4 3
    D 5 7 4 4
    E 6 5 3 4

    Sort edges for Kruskal: BC = 2, AC = 3, CE = 3, AB = 4, CD = 4, DE = 4, AD = 5, BE = 5, AE = 6, BD = 7. Add BC, AC, CE, CD. The MST has total weight 12.

    为 Kruskal 算法排序边:BC = 2、AC = 3、CE = 3、AB = 4、CD = 4、DE = 4、AD = 5、BE = 5、AE = 6、BD = 7。加入 BC、AC、CE、CD。最小生成树总权重为 12。


    8. Worked Example: Depth-First Traversal and Upper Bound | 示例:深度优先遍历与上界

    Start the depth-first search at A. The MST is A–C, C–B, C–D, C–E. At C, use alphabetical order, so visit B first, then D, then E. The first-visit order is A, C, B, D, E.

    从 A 开始深度优先搜索。最小生成树为 A–C、C–B、C–D、C–E。在 C 处按字母顺序,先访问 B,然后 D,再 E。首次访问顺序为 A、C、B、D、E。

    Return from E directly to A to close the cycle. The candidate tour is A–C–B–D–E–A. Its length is calculated as follows.

    从 E 直接返回 A 以闭合回路。候选路线为 A–C–B–D–E–A。其长度计算如下。

    Tour length = d(A,C) + d(C,B) + d(B,D) + d(D,E) + d(E,A) = 3 + 2 + 7 + 4 + 6 = 22

    Therefore the optimal tour length is at most 22, so an upper bound is 22. If the question asks for the best possible upper bound from different depth-first search orderings, you can try all valid orderings and select the smallest tour length found.

    因此最优路线长度最多为 22,所以上界为 22。如果题目要求从不同深度优先搜索顺序中找出最佳上界,你可以尝试所有有效顺序并选择找到的最小路线长度。


    9. Why It Gives an Upper Bound | 为什么它给出上界

    The depth-first search of a minimum spanning tree gives a sequence that visits every vertex at least once, and recording first visits removes repeated vertices. Since the original network is complete, you can join consecutive vertices in the first-visit list directly. The result is a Hamiltonian cycle, so it is a feasible tour.

    最小生成树的深度优先搜索给出一个至少访问每个顶点一次的序列,记录首次访问可以去掉重复顶点。由于原网络是完全的,你可以直接连接首次访问列表中相邻的顶点。得到的结果是一个哈密顿回路,因此是一条可行路线。

    The optimal tour is the shortest of all Hamiltonian cycles. Any feasible tour length must be greater than or equal to the optimal length, so the calculated tour length is an upper bound. A smaller upper bound is better, but any valid upper bound is accepted unless the question demands the best one.

    最优路线是所有哈密顿回路中最短的。任何可行路线长度都一定大于或等于最优长度,因此计算出的路线长度是一个上界。较小的上界更好,但除非题目要求最佳上界,任何有效上界都可以接受。


    10. Common Mistakes and Exam Tips | 常见错误与应试技巧

    One common mistake is writing down a vertex every time it is passed during backtracking. This creates repeated vertices in the tour, which is not a Hamiltonian cycle. Only record the first visit to each vertex.

    一个常见错误是在回溯时每次经过顶点都写下来。这会在路线中产生重复顶点,这不是哈密顿回路。只记录每个顶点的首次访问。

    Another mistake is using an edge that is not in the original graph to close the cycle. The network must be complete, so the direct return edge exists, but always check the distance table. Also do not use the MST weight as the upper bound; you must calculate the original edge weights along the tour.

    另一个错误是使用原图中不存在的边来闭合回路。网络必须是完全的,所以直接返回边确实存在,但务必检查距离表。此外不要用最小生成树的权重作为上界;你必须计算路线沿线原图边的权重。

    In the exam, show the sorted edges for Kruskal or the Prim table, draw the MST, draw or list the depth-first search order, then show the final tour and its length. Clear working helps secure method marks even if a small arithmetic error occurs.

    考试中,展示 Kruskal 的排序边或 Prim 表格,画出最小生成树,画出或列出深度优先搜索顺序,然后展示最终路线及其长度。清晰的步骤有助于即使出现小的计算错误也能拿到方法分。


    11. Quick Comparison with Nearest Neighbour | 与最近邻法快速比较

    The nearest neighbour algorithm chooses the cheapest unvisited vertex from the current vertex. It is faster, but it often produces a tour that can be locally trapped. The minimum spanning tree method uses global cheap connections first and then converts the tree into a cycle, so it is less likely to miss very cheap edges.

    最近邻算法从当前顶点选择最便宜的未访问顶点。它速度更快,但常常会陷入局部最优。最小生成树方法先利用全局的廉价连接,然后将树转化为回路,因此不太可能漏掉非常便宜的边。

    Both methods produce upper bounds. In Edexcel D1, you may be asked to compare two upper bounds or to explain why the minimum spanning tree method is suitable. A smaller upper bound is closer to the true optimal tour, so it is more useful.

    两种方法都产生上界。在 Edexcel D1 中,你可能会被要求比较两个上界,或解释为什么最小生成树方法适用。较小的上界更接近真实最优路线,因此更有用。


    12. Summary | 小结

    To find an upper bound using a minimum spanning tree method: find the MST, perform a depth-first search from a chosen start vertex, list vertices in first-visit order, return directly to the start, and calculate the tour length. This gives a valid Hamiltonian cycle, so its length is an upper bound for the optimal travelling salesman tour.

    使用最小生成树方法求上界的步骤为:找到最小生成树,从选定的起点进行深度优先搜索,按首次访问顺序列出顶点,直接返回起点,并计算路线长度。这给出一个有效的哈密顿回路,因此其长度是旅行商最优路线的一个上界。

    Practice with different complete networks and check your depth-first search order carefully. In the exam, always state your ordering rule and show your working for full marks.

    用不同的完全网络多加练习,并仔细检查深度优先搜索顺序。考试中务必说明你的排序规则并展示步骤,以获得满分。

    Published by TutorHao | Further Maths (D1) Revision Series | aleveler.com

    更多咨询请联系16621398022(同微信)

  • The Nearest Neighbour Algorithm | 最近邻算法

    📚 The Nearest Neighbour Algorithm | 最近邻算法

    The nearest neighbour algorithm is a fast, greedy route-building method. It is particularly important in the Edexcel A Level Computer Science specification when solving the travelling salesman problem (TSP), where an exact solution is often computationally infeasible.

    最近邻算法是一种快速、贪心的路径构建方法。在 Edexcel A Level 计算机科学大纲中,它在求解旅行商问题(TSP)时尤为重要,因为精确解往往在计算上不可行。

    1. Overview and Exam Context | 概述与考试背景

    In Edexcel A Level Computer Science, the nearest neighbour algorithm is a standard example of a greedy heuristic. It is used to produce a route, or tour, through a graph in which every pair of vertices is connected by a weighted edge. The most common application is the travelling salesman problem, where the goal is to visit every vertex exactly once and return to the start with the smallest possible total weight.

    在 Edexcel A Level 计算机科学中,最近邻算法是贪心启发式算法的标准示例。它用于在每对顶点都由加权边相连的图中生成一条路线或回路。最常见的应用是旅行商问题,目标是恰好访问每个顶点一次并返回起点,使总权重尽可能小。

    Exam questions may ask candidates to trace the algorithm on a distance matrix, write pseudocode, state the time complexity, or discuss why the result is not necessarily optimal. Marks are typically awarded for a clear sequence of visited

    Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com

    更多咨询请联系16621398022(同微信)

  • Chapter Review 4: Graphs and Transformations | 第4章复习:函数图像与变换

    📚 Chapter Review 4: Graphs and Transformations | 第4章复习:函数图像与变换

    This chapter review consolidates the key skills for Edexcel A-Level Pure Mathematics Chapter 4: recognising and sketching cubic, quartic and reciprocal graphs, and applying transformations to any given function y = f(x). The focus is on efficient curve sketching and writing new equations after translations, stretches and reflections.

    本章复习巩固爱德思 A-Level 纯数学第4章的核心技能:识别并绘制三次、四次和倒数函数图像,以及对任意给定函数 y = f(x) 进行图像变换。重点是高效绘制曲线以及写出平移、伸缩和反射后的新方程。

    1. Sketching Cubic Graphs | 绘制三次函数图像

    A cubic curve has the general form y = ax³ + bx² + cx + d. The sign of a controls the end behaviour: if a > 0, the curve falls to −∞ on the left and rises to +∞ on the right; if a < 0, this is reversed.

    三次曲线的一般式为 y = ax³ + bx² + cx + d。系数 a 的正负决定两端走势:若 a > 0,曲线左侧趋向 −∞、右侧趋向 +∞;若 a < 0 则相反。

    To sketch a cubic, find the y-intercept at (0, d) and factorise where possible to locate x-intercepts. A repeated factor gives a stationary point on the x-axis, while a triple factor gives an inflection point that crosses the axis.

    绘图时先找出 y 轴截距 (0, d),并尽可能因式分解以确定 x 轴截距。重复因式表示 x 轴处有静止点;三重因式表示过 x 轴处为拐点。

    For example, y = (x − 2)(x + 3)² has a root at x = 2 where the curve crosses the x-axis, and a repeated root at x = −3 where the curve touches the x-axis and turns.

    例如,y = (x − 2)(x + 3)² 在 x = 2 处有一个根且曲线穿过 x 轴,在 x = −3 处有重根,曲线在 x 轴处相切并转向。


    2. Sketching Quartic Graphs | 绘制四次函数图像

    A quartic graph y = ax⁴ + bx³ + cx² + dx + e is shaped like a W or U depending on repeated roots. If a > 0, both ends rise to +∞; if a < 0, both ends fall to −∞.

    四次函数图像 y = ax⁴ + bx³ + cx² + dx + e 根据重根不同可呈 W 形或 U 形。若 a > 0,两端都上升至 +∞;若 a < 0,两端都下降至 −∞。

    Repeated factors such as (x − p)² create a bounce at the x-axis, while a single factor creates a crossing. A triple factor in a quartic

    Published by TutorHao | A-Level Revision Series | aleveler.com

    更多咨询请联系16621398022(同微信)

  • Using Dijkstra’s Algorithm to Find the Shortest Path | 使用 Dijkstra 算法求解最短路径

    📚 Using Dijkstra’s Algorithm to Find the Shortest Path | 使用 Dijkstra 算法求解最短路径

    Dijkstra’s algorithm is a classic graph traversal method used to find the shortest path from a single source node to every other node in a weighted graph with non-negative edge weights. In Edexcel A-Level Computer Science, it is important to understand both the mechanics of the algorithm and the way it is presented in exam answers, including distance tables, priority queues and predecessor tracking.

    Dijkstra 算法是一种经典的图遍历方法,用于在具有非负边权的加权图中,找到从单一源节点到其他所有节点的最短路径。在 Edexcel A-Level 计算机科学考试中,既要理解算法的执行机制,也要掌握在答题中呈现距离表、优先队列和前驱节点跟踪的方法。


    1. The Shortest Path Problem | 最短路径问题

    A weighted graph consists of vertices, also called nodes, connected by edges that have an associated cost or weight. The shortest path problem asks us to find a route between two vertices such that the sum of the weights along the chosen edges is minimised.

    加权图由顶点(也称为节点)和连接这些顶点的边组成,每条边都有一个相关的代价或权值。最短路径问题要求我们找到两个顶点之间的一条路线,使得所选边上权值的总和最小。

    For example, in a road network the vertices could be towns and the edge weights could be driving times in minutes. The shortest path is not necessarily the path with the fewest edges; it is the path with the lowest total cost.

    例如,在道路网络中,顶点可以是城镇,边权可以是驾车时间(分钟)。最短路径并不一定是经过边数最少的路径,而是总代价最低的路径。

    Dijkstra’s algorithm solves the single-source shortest path problem. Starting from a given source node, it calculates the minimum distance to every other reachable node, provided all edge weights are zero or positive.

    Dijkstra 算法解决的是单源最短路径问题。从给定的源节点开始,它会计算到每一个可到达节点的最小距离,前提是所有的边权都为零或正数。


    2. Graph Representation for Dijkstra | Dijkstra 算法的图表示

    To apply Dijkstra’s algorithm, a weighted graph can be stored using an adjacency matrix or an adjacency list. An adjacency matrix uses a 2D array where the cell value gives the weight of the edge between two vertices; a missing edge can be represented by infinity or a very large number.

    要应用 Dijkstra 算法,加权图可以用邻接矩阵或邻接表来存储。邻接矩阵使用二维数组,单元格的值表示两个顶点之间边的权值;不存在的边可以用无穷大或一个非常大的数表示。

    An adjacency list stores, for each vertex, a list of its direct neighbours together with the corresponding edge weights. This is often more memory-efficient for sparse graphs and is the natural representation used with a priority queue.

    邻接表为每个顶点存储其直接邻居以及对应边权的列表。对于稀疏图,这种方式通常更节省内存,并且是与优先队列配合使用时的自然表示方法。

    In Edexcel exam questions, graphs are usually presented visually or as a table. You are expected to read the graph, build a working-values table, and show how the algorithm updates the shortest known distances.

    在 Edexcel 考试题中,图通常以图形或表格形式给出。你需要读懂图,建立工作值表,并展示算法如何更新已知的最短距离。


    3. Greedy Relaxation: The Key Idea | 贪心松弛:核心思想

    Dijkstra’s algorithm is a greedy algorithm. At each step it selects the unvisited vertex with the smallest current distance, marks it as visited, and then uses it to improve the distances to its neighbours. This improvement step is called relaxation.

    Dijkstra 算法是一种贪心算法。每一步它选择当前距离最小的未访问顶点,将其标记为已访问,然后利用它来改善其邻居的距离。这个改善步骤称为松弛。

    If vertex u has distance dist[u] and there is an edge from u to v with weight w(u, v), then the candidate distance to v through u is:

    如果顶点 u 的距离为 dist[u],且存在一条从 u 到 v 的边,权值为 w(u, v),那么通过 u 到达 v 的候选距离为:

    candidate = dist[u] + w(u, v)

    If this candidate is smaller than the currently stored dist[v], we update dist[v] and record u as the predecessor of v.

    如果这个候选值小于当前存储的 dist[v],我们就更新 dist[v],并将 u 记录为 v 的前驱节点。

    if dist[u] + w(u, v) < dist[v] then dist[v] = dist[u] + w(u, v)

    The key insight is that once a vertex has the smallest temporary distance among all unvisited vertices, its shortest distance is final. This is why Dijkstra’s algorithm works when all edge weights are non-negative.

    关键思想是:一旦某个顶点在所有未访问顶点中具有最小的临时距离,那么它的最短距离就已经确定。这就是为什么当所有边权非负时 Dijkstra 算法是有效的。


    4. The Formal Step-by-Step Procedure | 正式的分步流程

    The algorithm can be described as follows. First, create a distance table with three rows: vertex, shortest distance from source, and predecessor. Initialise the source distance to zero and every other vertex to infinity.

    该算法可以描述如下。首先创建一个距离表,包含三行:顶点、从源点到该顶点的最短距离、前驱节点。将源点的距离初始化为零,其他所有顶点初始化为无穷大。

    • Mark the source as current, and do not mark it as visited yet.
    • 将源点作为当前节点,此时尚未标记为已访问。
    • For the current vertex, examine every unvisited neighbour and relax the edge if possible.
    • 对于当前顶点,检查每一个未访问的邻居,并在可能的情况下进行松弛。
    • After examining all neighbours, mark the current vertex as visited.
    • 检查完所有邻居后,将当前顶点标记为已访问。
    • Select the unvisited vertex with the smallest distance as the new current vertex.
    • 选择未访问顶点中距离最小的那个作为新的当前顶点。
    • Repeat until the target vertex is visited or all reachable vertices have been visited.
    • 重复上述过程,直到目标顶点被访问,或者所有可到达的顶点都已访问。

    It is essential to only consider unvisited neighbours when relaxing, because the shortest path to a visited vertex is already final and cannot be improved later.

    必须只考虑未访问的邻居来进行松弛,因为已访问顶点的最短路径已经确定,之后不能再次改善。


    5. Worked Example: A to F | 例题:从 A 到 F

    Consider the following weighted graph. The edges and their weights are: A-B 4, A-C 2, B-C 1, B-D 5, C-D 8, C-E 10, D-E 2, D-F 6 and E-F 3. We want to find the shortest path from A to F.

    考虑以下加权图。边及其权值为:A-B 4、A-C 2、B-C 1、B-D 5、C-D 8、C-E 10、D-E 2、D-F 6 和 E-F 3。我们需要找到从 A 到 F 的最短路径。

    Initialise the distance table as follows:

    初始化距离表如下:

    Vertex A B C D E F
    Distance 0
    Predecessor

    Start at A. Relax its neighbours: B becomes 4 and C becomes 2. Mark A as visited. The smallest unvisited distance is C with 2, so C becomes current.

    从 A 开始。松弛其邻居:B 变为 4,C 变为 2。将 A 标记为已访问。未访问顶点中最小距离是 C,为 2,因此 C 成为当前节点。

    From C, relax unvisited neighbours B, D and E. Distances are updated as follows: B = min(4, 2+1) = 3, D = min(∞, 2+8) = 10, E = min(∞, 2+10) = 12. Mark C as visited. The next node is B with distance 3.

    从 C 出发,松弛未访问的邻居 B、D 和 E。距离更新如下:B = min(4, 2+1) = 3,D = min(∞, 2+8) = 10,E = min(∞, 2+10) = 12。将 C 标记为已访问。下一个节点是距离为 3 的 B。

    From B, relax unvisited neighbour D: D = min(10, 3+5) = 8. Mark B as visited. The next node is D with distance 8.

    从 B 出发,松弛未访问的邻居 D:D = min(10, 3+5) = 8。将 B 标记为已访问。下一个节点是距离为 8 的 D。

    From D, relax unvisited neighbours E and F: E = min(12, 8+2) = 10, F = min(∞, 8+6) = 14. Mark D as visited. The next node is E with distance 10.

    从 D 出发,松弛未访问的邻居 E 和 F:E = min(12, 8+2) = 10,F = min(∞, 8+6) = 14。将 D 标记为已访问。下一个节点是距离为 10 的 E。

    From E, relax unvisited neighbour F: F = min(14, 10+3) = 13. Mark E as visited. Finally, F is visited with distance 13.

    从 E 出发,松弛未访问的邻居 F:F = min(14, 10+3) = 13。将 E 标记为已访问。最后,F 被访问,距离为 13。


    6. Distance Table and Priority Queue Trace | 距离表与优先队列跟踪

    The final distance table after the algorithm terminates is shown below. It records the shortest distance from A to every vertex.

    算法终止后的最终距离表如下所示。它记录了从 A 到每个顶点的最短距离。

    Vertex A B C D E F
    Shortest distance 0 3 2 8 10 13
    Predecessor C A B D E

    Using the predecessor row, we can reconstruct the shortest path by starting at F and working backwards: F → E → D → B → C → A. Reversing this gives A → C → B → D → E → F.

    利用前驱行,我们可以从 F 开始反向重建最短路径:F → E → D → B → C → A。将其反转得到 A → C → B → D → E → F。

    The priority queue trace would show the order in which vertices were extracted: A, C, B, D, E, F. This order matches the visited sequence because each time we select the unvisited vertex with the smallest known distance.

    优先队列的跟踪会显示顶点的提取顺序:A、C、B、D、E、F。这个顺序与访问顺序一致,因为每次我们都选择已知距离最小的未访问顶点。


    7. Pseudocode for Edexcel Exam Questions | Edexcel 考试伪代码

    A standard exam-style pseudocode for Dijkstra’s algorithm is given below. It assumes a graph represented by an adjacency list and a priority queue ordered by distance.

    下面给出一个标准的考试风格 Dijkstra 算法伪代码。它假设图用邻接表表示,并且有一个按距离排序的优先队列。

    function dijkstra(graph, source):
        dist = array of size |V| filled with infinity
        pred = array of size |V| filled with null
        dist[source] = 0
        pq = priority queue containing all vertices keyed by dist
        while pq is not empty:
            u = pq.removeMin()
            for each neighbour v of u:
                if v is in pq:
                    newDist = dist[u] + weight(u, v)
                    if newDist < dist[v]:
                        dist[v] = newDist
                        pred[v] = u
                        pq.decreaseKey(v, newDist)
        return dist, pred

    In the pseudocode, removeMin extracts the vertex with the smallest distance. The decreaseKey operation updates the priority of a vertex after its distance has been reduced, ensuring the priority queue remains correct.

    在伪代码中,removeMin 取出距离最小的顶点。decreaseKey 操作在某个顶点的距离减小后更新其在优先队列中的优先级,从而确保优先队列保持正确。

    When writing pseudocode in an Edexcel exam, it is acceptable to show relaxation and selection steps more informally, as long as the greedy selection and distance update logic are clear.

    在 Edexcel 考试中编写伪代码时,可以更非正式地展示松弛和选择步骤,只要贪心选择和距离更新逻辑清晰即可。


    8. Time and Space Complexity | 时间复杂度与空间复杂度

    The time complexity of Dijkstra’s algorithm depends on the data structures used. With an adjacency matrix and a simple linear search for the minimum, the algorithm runs in O(V²) time, where V is the number of vertices.

    Dijkstra 算法的时间复杂度取决于所使用的数据结构。使用邻接矩阵和简单的线性搜索最小值时,算法的时间复杂度为 O(V²),其中 V 是顶点数量。

    With a binary heap as the priority queue and an adjacency list, the time complexity becomes O((V + E) log V), where E is the number of edges. This is better for sparse graphs where E is much smaller than V².

    使用二叉堆作为优先队列和邻接表时,时间复杂度变为 O((V + E) log V),其中 E 是边的数量。对于 E 远小于 V² 的稀疏图,这种实现更高效。

    The space complexity is O(V + E) for the adjacency list representation, plus O(V) for the distance and predecessor arrays. For an adjacency matrix, the space complexity is O(V²).

    邻接表表示的空间复杂度为 O(V + E),距离和前驱数组还需要 O(V) 的空间。对于邻接矩阵,空间复杂度为 O(V²)。

    In exam answers, it is useful to state both the basic and the heap-based complexity, and to explain when each implementation is preferable.

    在考试答案中,最好同时说明基本实现和基于堆的实现的时间复杂度,并解释每种实现分别适用于什么情况。


    9. Limitations: Negative Edge Weights | 局限性:负权边

    Dijkstra’s algorithm does not produce correct results when a graph contains negative edge weights. Because the algorithm greedily finalises a vertex once it has the smallest temporary distance, a later negative edge could provide an even shorter path to that vertex.

    当图中包含负权边时,Dijkstra 算法无法得到正确结果。因为该算法会在某个顶点具有最小临时距离时就将其贪心地确定下来,但之后出现的一条负权边可能会提供一条到达该顶点的更短路径。

    As an example, suppose the edges are A-B with weight 2, A-C with weight 4, and C-B with weight -3. Starting at A, the algorithm sets B = 2 and C = 4. It visits B first, marks it as final, and then relaxes C-B to give a path A-C-B with total cost 1. However, B has already been visited, so the correct shortest path is missed.

    举例来说,假设边为 A-B 权值 2,A-C 权值 4,C-B 权值 -3。从 A 开始,算法设 B = 2,C = 4。它先访问 B 并将其标记为最终节点,然后通过 C-B 松弛得到路径 A-C-B,总代价为 1。但此时 B 已经被访问过,因此正确的最短路径被遗漏了。

    For graphs that may contain negative edges, the Bellman-Ford algorithm should be used instead, because it can correctly handle them, although it has a higher time complexity.

    对于可能包含负权边的图,应改用 Bellman-Ford 算法,因为它能正确处理负权边,尽管其时间复杂度更高。


    10. Dijkstra vs A* Search | Dijkstra 与 A* 搜索

    Dijkstra’s algorithm explores outward from the source in all directions based purely on actual known distances. It guarantees the shortest path but can be slow for large graphs because it does not use any information about the target’s direction.

    Dijkstra 算法仅根据已知的实际距离,从源点向所有方向扩展搜索。它能保证最短路径,但在大规模图中可能较慢,因为它没有利用任何关于目标方向的信息。

    The A* algorithm improves on Dijkstra by using a heuristic function h(n) that estimates the remaining cost from a node to the target. Its selection priority is dist[n] + h(n). Dijkstra is a special case of A* where h(n) = 0 for every node.

    A* 算法通过使用启发函数 h(n) 来改进 Dijkstra,该函数估计从节点 n 到目标的剩余代价。它的选择优先级为 dist[n] + h(n)。Dijkstra 是 A* 在 h(n) = 0 时的特殊情况。

    If the heuristic is admissible, meaning it never overestimates the true remaining cost, A* is guaranteed to find the shortest path while usually visiting fewer nodes than Dijkstra.

    如果启发函数是可采纳的,即它从不高估真实的剩余代价,那么 A* 算法保证能够找到最短路径,同时通常比 Dijkstra 访问更少的节点。


    11. Exam Technique and Presentation | 考试技巧与作答呈现

    In Edexcel A-Level Computer Science exams, you may be asked to run Dijkstra’s algorithm on a given graph, complete a working-values table, or state the final shortest path and its length. Clear presentation is essential for full marks.

    在 Edexcel A-Level 计算机科学考试中,你可能会被要求对给定图运行 Dijkstra 算法、填写工作值表,或者写出最终的最短路径及其长度。清晰的作答呈现对于获得满分至关重要。

    A well-presented answer should include a table showing all vertices, their current distances, their predecessor vertices, and whether each vertex has been visited. At each iteration, the selected vertex should be clearly stated.

    一份好的答案应包括一个表格,显示所有顶点、它们的当前距离、前驱节点以及每个顶点是否已访问。在每次迭代中,应清楚地说明所选择的顶点。

    After the algorithm finishes, you must reconstruct the shortest path using the predecessor column and state the total weight. Do not forget to write the path in the correct order from source to target.

    算法结束后,你必须使用前驱列重建最短路径,并写出总权值。不要忘记按从源点到目标的正确顺序书写路径。


    12. Common Mistakes and Revision Checklist | 常见错误与复习清单

    Common mistakes include forgetting to initialise all distances to infinity, updating visited vertices after they have been finalised, selecting a vertex with a larger distance instead of the smallest, and failing to record predecessors for path reconstruction.

    常见错误包括:忘记将所有距离初始化为无穷大、在顶点已经确定后仍对其进行更新、选择了距离较大的顶点而不是最小距离顶点,以及没有记录前驱节点导致无法重建路径。

    Use this checklist before an exam: initialise source to 0 and others to ∞; select the unvisited vertex

    Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com

    更多咨询请联系16621398022(同微信)

  • Using the Route Inspection Algorithm | 使用路径检查算法(中国邮递员算法)

    📚 Using the Route Inspection Algorithm | 使用路径检查算法(中国邮递员算法)

    The route inspection algorithm, often called the Chinese postman algorithm, is a graph theory method used to find the shortest route that traverses every edge in a network at least once and returns to the start vertex. In A-Level Computer Science and Decision Mathematics, this algorithm models real-world tasks such as refuse collection, postal delivery, gritting roads, and network maintenance. The central idea is to make a non-Eulerian graph Eulerian by adding the least possible extra distance in the form of repeated edges.

    路径检查算法,通常称为中国邮递员算法,是一种图论方法,用于寻找至少遍历网络中每条边一次并返回起点的最短路线。在 A-Level 计算机科学和决策数学中,该算法用于建模垃圾清运、邮政投递、道路撒盐和网络维护等实际任务。其核心思想是通过添加尽可能少的额外路程(以重复边形式),使非欧拉图变为欧拉图。

    1. What is the Route Inspection Algorithm? | 什么是路径检查算法?

    The route inspection problem asks: given a connected weighted graph, find the minimum-weight closed walk that includes every edge at least once. A walk that covers every edge exactly once is an Eulerian circuit and exists only if every vertex has even degree. The route inspection algorithm identifies which edges must be repeated in order to create such a circuit when the original graph does not already have one.

    路径检查问题要求:给定一个连通加权图,找出至少包含每条边一次的最小权重闭合行走。恰好覆盖每条边一次的行走称为欧拉回路,仅当每个顶点的度数为偶数时才存在。路径检查算法用于在原图不存在欧拉回路时,确定必须重复哪些边以构造这样的回路。


    2. Key Graph Theory Terms | 关键图论术语

    Before applying the algorithm, you must be confident with basic graph terminology. The degree of a vertex is the number of edges incident to it. A vertex is odd if its degree is odd, and even if its degree is even. A walk is a sequence of edges where consecutive edges share a vertex. A circuit is a closed walk. An Eulerian circuit traverses every edge exactly once, while a semi-Eulerian trail traverses every edge exactly once but starts and ends at different vertices.

    在应用算法之前,必须熟悉基本图术语。顶点的度是与该顶点相连的边数。度数为奇数的顶点称奇顶点,度数为偶数的顶点称偶顶点。行走是一系列边,相邻边共享顶点。回路是闭合行走。欧拉回路恰好经过每条边一次,而半欧拉迹恰好经过每条边一次,但起点和终点不同。

    English term 中文术语 Meaning / 含义
    Degree 度数 Number of edges incident to a vertex / 与顶点相连的边数
    Odd vertex 奇顶点 Vertex with odd degree / 度数为奇数的顶点
    Even vertex 偶顶点 Vertex with even degree / 度数为偶数的顶点
    Eulerian circuit 欧拉回路 Closed walk using every edge exactly once / 恰好经过每条边一次的闭合行走
    Semi-Eulerian trail 半欧拉迹 Trail using every edge exactly once, different start and end / 恰好经过每条边一次但起点终点不同的迹

    3. Eulerian Graphs and Closed Routes | 欧拉图与闭合路线

    A connected graph is Eulerian if every vertex has even degree. In this case, an Eulerian circuit exists, so the route inspection answer is simply the total weight of all edges. No edge needs to be repeated. You can find the circuit using Fleury’s algorithm or by tracing edges and removing them once used, but for exam purposes you may only need the total length.

    如果连通图的每个顶点都是偶顶点,则该图是欧拉图。此时存在欧拉回路,因此路径检查的答案就是所有边的总权重,无需重复任何边。可以使用弗勒里算法构造回路,或通过每次走过一条边并删除已使用的边来跟踪,但考试中通常只需要总长度。


    4. When a Graph is Not Eulerian | 当图不是欧拉图时

    If a connected graph has exactly two odd vertices, it is semi-Eulerian and has an Eulerian trail but no Eulerian circuit. To return to the start, the two odd vertices must become even by duplicating a path connecting them. The least extra distance is the shortest path between those two odd vertices. The route inspection length is total weight + shortest path weight.

    如果连通图恰好有两个奇顶点,则该图是半欧拉图,具有欧拉迹但没有欧拉回路。为了回到起点,必须通过复制连接这两个奇顶点的一条路径,使它们变为偶顶点。最少的额外距离就是这两个奇顶点之间的最短路径长度。路径检查长度为总权重 + 最短路径权重。


    5. Pairing Odd Vertices and Repeated Edges | 配对奇顶点与重复边

    When a graph has more than two odd vertices, the number of odd vertices is always even. The algorithm requires pairing all odd vertices so that every odd vertex is connected by a repeated shortest path to exactly one other odd vertex. These repeated paths add extra edges and make every vertex even. The challenge is to choose the pairing with the smallest total additional weight.

    当图的奇顶点超过两个时,奇顶点的数量总是偶数。该算法要求将所有奇顶点配对,使每个奇顶点通过一条重复的最短路径恰好与另一个奇顶点相连。这些重复路径增加了额外边,使每个顶点变为偶顶点。难点在于选择总附加权重最小的配对方案。


    6. The Route Inspection Algorithm Step by Step | 路径检查算法逐步解析

    Step 1: List all vertices and calculate their degrees. Identify which vertices are odd.

    步骤 1:列出所有顶点并计算它们的度数。标出哪些顶点是奇顶点。

    Step 2: If there are no odd vertices, the graph is Eulerian and the minimum route length is the sum of all edge weights.

    步骤 2:如果没有奇顶点,则图是欧拉图,最短路线长度就是所有边权重之和。

    Step 3: If there are exactly two odd vertices, find the shortest path between them using Dijkstra’s algorithm or inspection. Add this path as repeated edges. Total length = sum of edge weights + shortest path weight.

    步骤 3:如果恰好有两个奇顶点,使用 Dijkstra 算法或观察法找到它们之间的最短路径。将该路径作为重复边添加。总长度 = 边权重总和 + 最短路径权重。

    Step 4: If there are more than two odd vertices, list all possible pairings of odd vertices. For each pairing, find the sum of the shortest path weights for the pairs. Choose the pairing with the smallest total.

    步骤 4:如果奇顶点多于两个,列出所有可能的奇顶点配对。对每种配对,计算各对顶点最短路径权重之和。选择总和最小的配对。

    Step 5: Duplicate the edges along the chosen shortest paths so every vertex becomes even. Then find an Eulerian circuit through the enlarged graph. The total route length is the original weight + added repeated weight.

    步骤 5:沿所选最短路径复制边,使每个顶点都变为偶顶点。然后在扩大后的图中找出欧拉回路。路线总长度为原始权重 + 增加的重复权重。


    7. Worked Example: Simple Network | 示例:简单网络

    Consider a graph with vertices A, B, C, D and weighted edges AB = 5, BC = 4, CD = 6, DA = 3, AC = 7. The degrees are: deg(A) = 3, deg(B) = 2, deg(C) = 3, deg(D) = 2. Vertices A and C are odd. The sum of all edge weights is 25. The shortest path from A to C is the direct edge AC = 7 because AB + BC = 9 and AD + DC = 9. Therefore the route inspection length is 25 + 7 = 32, and edge AC must be repeated.

    考虑一个图,顶点为 A、B、C、D,加权边为 AB = 5、BC = 4、CD = 6、DA = 3、AC = 7。度数分别为:deg(A) = 3、deg(B) = 2、deg(C) = 3、deg(D) = 2。顶点 A 和 C 是奇顶点。所有边权重之和为 25。从 A 到 C 的最短路径是直接边 AC = 7,因为 AB + BC = 9、AD + DC = 9。因此路径检查路线长度为 25 + 7 = 32,边 AC 必须重复。


    8. Worked Example with Multiple Pairings | 多组配对示例

    Suppose a graph has four odd vertices A, B, C and D. The shortest distances between every pair have been calculated

    Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com

    更多咨询请联系16621398022(同微信)

  • Eulerian Graphs | 欧拉图

    📚 Eulerian Graphs | 欧拉图

    In Edexcel Decision Mathematics, Eulerian graphs provide a powerful way to model routes that cover every edge of a network exactly once. This article explains the definitions, degree conditions, algorithms and exam-style applications you need.

    在 Edexcel 决策数学中,欧拉图提供了一种强大的建模方法,用来描述恰好经过网络中每条边一次的路由。本文讲解定义、顶点度条件、算法以及考试风格的应用。

    1. Graphs and trails | 图与路径

    A graph G = (V, E) consists of vertices (nodes) and edges (arcs) joining pairs of vertices. A trail is a sequence of edges in which no edge is repeated; a circuit is a closed trail.

    图 G = (V, E) 由顶点(节点)和连接顶点对的边(弧)组成。路径(trail)是指没有重复边的边序列;回路(circuit)是闭合的路径。

    In A-Level questions, graphs may be simple, multiple or directed. For Eulerian graphs, the usual focus is on undirected connected graphs, but directed versions appear in Further Mathematics.

    在 A-Level 试题中,图可以是简单图、多重图或有向图。对于欧拉图,通常关注无向连通图,但在进阶数学中也会出现有向版本。


    2. Eulerian graph definition | 欧拉图的定义

    A connected graph is Eulerian if it contains an Eulerian circuit: a closed trail that uses every edge exactly once. A graph with an Eulerian circuit is called an Eulerian graph.

    如果连通图包含欧拉回路,则该图是欧拉图:欧拉回路是恰好使用每条边一次的闭合路径。含有欧拉回路的图称为欧拉图。

    Equivalently, a graph is Eulerian if you can start at a vertex, travel along every edge exactly once, and return to the starting vertex without lifting your pen.

    等价地说,如果可以从某个顶点出发,沿每条边恰好走一次,并回到起点,且不抬笔,那么该图就是欧拉图。


    3. Eulerian trails and circuits | 欧拉路径与回路

    An Eulerian trail uses every edge exactly once but does not need to end where it started. An Eulerian circuit is a closed Eulerian trail. Every Eulerian circuit is an Eulerian trail, but not conversely.

    欧拉路径恰好使用每条边一次,但不要求终点与起点重合。欧拉回路是闭合的欧拉路径。每个欧拉回路都是欧拉路径,但反过来不一定成立。

    For example, the graph with vertices A, B, C and edges AB, BC, CA, AD, DC has an Eulerian trail from B to D but no Eulerian circuit.

    例如,顶点为 A、B、C,边为 AB、BC、CA、AD、DC 的图具有从 B 到 D 的欧拉路径,但没有欧拉回路。


    4. Semi-Eulerian graphs | 半欧拉图

    A connected graph is semi-Eulerian if it contains an Eulerian trail but no Eulerian circuit. This means you can cover every edge exactly once, but the start and end vertices must be different.

    如果连通图包含欧拉路径但没有欧拉回路,则该图是半欧拉图。这意味着你可以恰好覆盖每条边一次,但起点和终点必须是不同的顶点。

    The term “semi-Eulerian” is used in Edexcel D1. Make sure you do not call such a graph Eulerian unless a closed trail covering all edges exists.

    “半欧拉图” 这一术语用于 Edexcel D1。请确保不要将这类图称为欧拉图,除非存在覆盖所有边的闭合路径。


    5. Degree conditions | 顶点度条件

    For a connected graph, Euler’s theorem gives a simple test. A connected graph is Eulerian if and only if every vertex has even degree.

    对于连通图,欧拉定理给出一个简单判定。连通图是欧拉图当且仅当每个顶点的度数都是偶数。

    A connected graph is semi-Eulerian if and only if exactly two vertices have odd degree. In that case, the Eulerian trail must start at one odd-degree vertex and end at the other.

    连通图是半欧拉图当且仅当恰好有两个顶点的度数为奇数。此时,欧拉路径必须从一个奇度顶点开始,并在另一个奇度顶点结束。

    If a graph has more than two odd-degree vertices, it is neither Eulerian nor semi-Eulerian. You would need to repeat some edges to cover the network.

    如果图中超过两个奇度顶点,则它既不是欧拉图也不是半欧拉图。你需要重复某些边才能遍历整个网络。

    Degrees (connected graph) 中文:度数(连通图) Classification 中文:分类
    All even 全部为偶数 Eulerian 欧拉图
    Exactly two odd 恰好两个奇数 Semi-Eulerian 半欧拉图
    More than two odd 超过两个奇数 Neither 都不是

    6. Connectedness and isolated vertices | 连通性与孤立顶点

    The degree condition only works for connected graphs. A disconnected graph with all even degrees is not Eulerian because you cannot travel between components.

    度条件只适用于连通图。一个所有顶点度数均为偶数但不连通的图不是欧拉图,因为你无法在不同连通分量之间通行。

    Isolated vertices with degree 0 are even-degree vertices. If the rest of the graph is connected, isolated vertices may be ignored when checking Eulerian properties.

    度数为 0 的孤立顶点属于偶度顶点。如果图的其余部分是连通的,在判断欧拉性质时可以忽略孤立顶点。


    7. Fleury’s algorithm | Fleury 算法

    Fleury’s algorithm constructs an Eulerian circuit or trail by never crossing a bridge unless there is no alternative. A bridge is an edge whose removal increases the number of connected components.

    Fleury 算法通过除非别无选择,否则绝不经过桥的方式来构造欧拉回路或欧拉路径。桥是指删除后会增加连通分量数量的边。

    Start at an appropriate vertex: any vertex for an Eulerian circuit, or one of the two odd-degree vertices for a semi-Eulerian trail. At each step, choose a non-bridge edge if possible.

    从合适的顶点出发:对于欧拉回路可以从任意顶点出发;对于半欧拉路径则从一个奇度顶点出发。每一步尽可能选择非桥边。

    This algorithm is often tested with small networks where you must explain why a particular edge cannot be used until later.

    该算法常在小网络上考查,要求解释为什么某条边必须留到后面才能使用。


    8. Hierholzer’s algorithm | Hierholzer 算法

    Hierholzer’s algorithm builds an Eulerian circuit by merging edge-disjoint cycles. Start from any vertex, follow unused edges until returning to the start, forming a cycle.

    Hierholzer 算法通过合并边不交的回路来构造欧拉回路。从任意顶点出发,沿着未使用的边走,直到返回起点,形成一个回路。

    If unused edges remain, find a vertex on the current circuit with unused incident edges, then start a new cycle from that vertex and splice it into the original circuit.

    如果仍有未使用的边,则在当前回路上找一个仍有未使用关联边的顶点,从该顶点开始新回路,并将其拼接到原回路中。

    This algorithm is efficient for computer implementations, but exam questions usually ask for one valid Eulerian circuit rather than a specific algorithm.

    该算法在计算机实现中很高效,但考试题目通常只要求给出一个有效的欧拉回路,而不要求指定算法。


    9. Route inspection problem | 路线检查问题

    The route inspection problem, sometimes called the Chinese postman problem, asks for the shortest route that covers every edge at least once and returns to the start.

    路线检查问题,有时称为中国邮递员问题,要求找到至少覆盖每条边一次并返回起点的最短路线。

    If the graph is Eulerian, the optimum route is simply an Eulerian circuit, and its length equals the sum of all edge weights.

    如果图是欧拉图,最优路线就是欧拉回路,其长度等于所有边的权重之和。

    If the graph is not Eulerian, you must add repeated edges between odd-degree vertices to make all degrees even. The aim is to minimise the total weight of the repeated edges.

    如果图不是欧拉图,则必须在奇度顶点之间添加重复边,使所有度数变为偶数。目标是使重复边的总权重最小。

    For Edexcel exams, you need to identify odd-degree vertices, consider pairings, and choose the minimum-weight pairing to determine the length

    Published by TutorHao | A-Level Revision Series | aleveler.com

    更多咨询请联系16621398022(同微信)

  • Prim’s Algorithm | Prim 算法

    📚 Prim’s Algorithm | Prim 算法

    Prim’s algorithm is a greedy method for finding the minimum spanning tree of a connected, weighted, undirected graph. It builds the tree one vertex at a time, always adding the cheapest edge that connects the current tree to a vertex outside the tree.

    Prim 算法是一种贪心算法,用于在连通、带权、无向图中寻找最小生成树。它每次扩展一个顶点,总是添加连接当前树与树外顶点的权重最小的边。


    1. Minimum Spanning Trees | 最小生成树

    A minimum spanning tree, or MST, is a subset of edges that connects every vertex in a graph together without any cycles and has the smallest possible total edge weight. An MST with V vertices always contains exactly V – 1 edges.

    最小生成树(MST)是指将图中所有顶点连接起来且不含回路的一棵边子集,并且这些边的总权重尽可能小。对于有 V 个顶点的图,最小生成树恰好包含 V – 1 条边。

    Prim’s algorithm is useful because many real-world problems can be modelled as finding a minimum spanning tree, such as designing road networks, laying cables, or building low-cost communication links.

    Prim 算法非常实用,因为许多现实问题都可以建模为寻找最小生成树,例如设计道路网络、铺设电缆或建立低成本的通信连接。


    2. The Core Idea of Prim’s Algorithm | Prim 算法的核心思想

    Prim’s algorithm starts at an arbitrary vertex and treats this vertex as the initial tree. At each step, it looks at every edge that connects a vertex already in the tree to a vertex outside the tree, and it selects the edge with the minimum weight. That edge and the new vertex are then added to the tree.

    Prim 算法从任意一个顶点开始,把这个顶点当作初始的树。每一步,它查看所有连接已在树中的顶点与树外顶点的边,并选择权重最小的那条边。然后将这条边和新的顶点加入树中。

    This process repeats until all vertices have been included. Because the algorithm always picks the cheapest available connection and never revises earlier decisions, it is classified as a greedy algorithm.

    这个过程不断重复,直到所有顶点都被加入树中。由于算法总是选择当前可用的最便宜连接,并且不会修正之前的决定,因此它被归类为贪心算法。


    3. Step-by-Step Procedure | 逐步执行步骤

    The algorithm can be described as follows:

    算法可以描述如下:

    1. Choose any starting vertex. Mark it as visited and set its key value to 0. For every other vertex, set the key value to infinity.

    1. 选择任意一个起始顶点。将其标记为已访问,并设置它的 key 值为 0。对于其他所有顶点,把 key 值设为无穷大。

    2. While there are still unvisited vertices, select the unvisited vertex with the smallest key value. Add the edge connecting this vertex to the current tree, and mark the vertex as visited.

    2. 当仍然存在未访问顶点时,选择 key 值最小的未访问顶点。将连接该顶点与当前树的边加入生成树,并把这个顶点标记为已访问。

    3. After visiting a vertex, examine all its neighbours that are not yet visited. If the weight of the edge to a neighbour is smaller than the neighbour’s current key value, update that key value and record the current vertex as its parent.

    3. 访问一个顶点后,检查它所有尚未访问的邻接顶点。如果通向某个邻接顶点的边的权重小于该邻接顶点当前的 key 值,就更新这个 key 值,并把当前顶点记录为它的父顶点。

    4. Repeat steps 2 and 3 until every vertex is visited. The resulting set of edges used to visit each vertex forms the minimum spanning tree.

    4. 重复步骤 2 和 3,直到所有顶点都被访问。最终用于访问每个顶点的边的集合就构成最小生成树。


    4. Worked Example | 示例演算

    Consider the following weighted graph with vertices A, B, C and D. The edge weights are AB = 4, AC = 2, BC = 1, BD = 5 and CD = 3. Start Prim’s algorithm at vertex A.

    考虑一个包含顶点 A、B、C 和 D 的带权图。边的权重为 AB = 4、AC = 2、BC = 1、BD = 5 和 CD = 3。从顶点 A 开始执行 Prim 算法。

    The tables below show the visited set, the chosen edge and the current total cost after each step.

    下表展示了每一步的已访问集合、选择的边以及当前总成本。

    Step Visited set Chosen edge Weight Total
    0 {A} 0
    1 {A, C} AC 2 2
    2 {A, C, B} CB 1 3
    3 {A, C, B, D} CD 3 6

    The minimum spanning tree consists of edges AC, CB and CD, with total weight 2 + 1 + 3 = 6.

    最小生成树由边 AC、CB 和 CD 组成,总权重为 2 + 1 + 3 = 6。


    5. Data Structures and Implementation | 数据结构与实现

    To implement Prim’s algorithm efficiently, we need three main structures: a key array to store the current minimum distance from the tree to each vertex, a parent array to record the edge that connects each vertex to the tree, and a priority queue or similar structure to select the next unvisited vertex with the smallest key.

    为了高效地实现 Prim 算法,我们需要三种主要结构:一个 key 数组,用于存储从当前树到每个顶点的最小距离;一个 parent 数组,用于记录连接每个顶点与树的边;以及一个优先队列或类似结构,用于选择下一个 key 值最小的未访问顶点。

    A typical high-level implementation can be expressed using the following update rule after adding a vertex u:

    在加入顶点 u 之后,典型的高层实现可以用下面的更新规则表示:

    if v is unvisited and weight(u, v) < key[v] then key[v] ← weight(u, v), parent[v] ← u

    For small graphs, a simple array and linear scan can be used, which is easier to trace in an exam. For larger graphs, a binary heap priority queue reduces the time needed to find the minimum key value.

    对于小图,可以使用简单的数组和线性扫描,这在考试中更容易追踪。对于较大的图,二叉堆优先队列可以减少查找最小 key 值所需的时间。


    6. Time Complexity Analysis | 时间复杂度分析

    The time complexity of Prim’s algorithm depends on how the graph is stored and how the next vertex is selected.

    Prim 算法的时间复杂度取决于图的存储方式以及如何选择下一个顶点。

    If the graph is stored as an adjacency matrix and we use a simple linear scan to find the minimum key, the complexity is O(V²), where V is the number of vertices. This approach is simple and works well for dense graphs.

    如果图用邻接矩阵存储,并且使用简单的线性扫描来查找最小 key 值,那么时间复杂度为 O(V²),其中 V 是顶点数。这种方法简单,并且适用于稠密图。

    If the graph is stored as an adjacency list and a binary heap is used as the priority queue, the complexity is O(E log V), where E is the number of edges. This is generally better for sparse graphs. With a Fibonacci heap, the complexity can be improved to O(E + V log V).

    如果图用邻接表存储,并使用二叉堆作为优先队列,时间复杂度为 O(E log V),其中 E 是边数。对于稀疏图,这种方式通常更好。如果使用斐波那契堆,复杂度可以进一步优化为 O(E + V log V)。


    7. Correctness of Prim’s Algorithm | Prim 算法的正确性

    Prim’s algorithm is correct because of the cut property. A cut partitions the vertices into two disjoint sets; the cut property states that for any cut, the minimum-weight edge crossing the cut belongs to some minimum spanning tree.

    Prim 算法之所以正确,是因为切分性质。一个切分将顶点分为两个不相交的集合;切分性质指出,对于任意一个切分,横跨该切分的最小权重边一定属于某个最小生成树。

    At every step, Prim’s algorithm considers the cut between the set of visited vertices and the set of unvisited vertices. It adds the minimum-weight edge crossing this cut. By the cut property, this edge is safe to include in an MST. Therefore, after V – 1 iterations, the algorithm has constructed a valid minimum spanning tree.

    在每一步,Prim 算法考虑已访问顶点集合与未访问顶点集合之间的切分。它加入横跨这个切分的最小权重边。根据切分性质,这条边可以安全地包含在最小生成树中。因此,经过 V – 1 次迭代后,算法就构造出了一棵有效的最小生成树。


    8. Prim’s vs Kruskal’s Algorithm | Prim 与 Kruskal 算法比较

    Both Prim’s algorithm and Kruskal’s algorithm find the same minimum spanning tree weight, but they build the tree in different ways. Prim’s algorithm grows a single tree from a starting vertex, whereas Kruskal’s algorithm sorts all edges by weight and adds the cheapest edge that does not create a cycle.

    Prim 算法和 Kruskal 算法都能得到相同的最小生成树总权重,但它们的建树方式不同。Prim 算法从一个起始顶点开始生长一棵树,而 Kruskal 算法将所有边按权重排序,然后添加不会形成回路的最便宜边。

    Feature Prim’s algorithm Kruskal’s algorithm
    Approach Grow one tree from a start vertex Build forest and merge components
    Best for Dense graphs Sparse graphs
    Time complexity O(V²) with adjacency matrix, O(E log V) with heap O(E log E) or O(E log V)
    Data structure needed Priority queue or key array Union-find / disjoint set

    In exam questions, you should choose the algorithm that is easier to apply to the given graph. If the graph is drawn with a clear starting point, Prim’s algorithm is usually faster to trace manually. If the edges are already listed, Kruskal’s algorithm may be simpler.

    在考试题目中,你应该选择更适合给定图的算法。如果图给出了明确的起点,Prim 算法通常更容易手动追踪。如果边已经列出,Kruskal 算法可能更简单。


    9. Common Mistakes and Exam Tips | 常见错误与应试技巧

    One common mistake is updating a key value without checking whether the vertex is already visited. This can lead to the same vertex being added twice or an incorrect edge being selected. Always separate the visited set from the unvisited set.

    一个常见错误是在没有检查顶点是否已经访问的情况下就更新 key 值。这可能导致同一个顶点被加入两次,或者选择了错误的边。一定要把已访问集合和未访问集合分开。

    Another mistake is choosing the smallest edge globally instead of the smallest edge crossing the cut. Prim’s algorithm only considers edges that connect the current tree to an outside vertex, not any edge anywhere in the graph.

    另一个错误是选择全局最小的边,而不是横跨切分的最小边。Prim 算法只考虑连接当前树与树外顶点的边,而不是图中任意位置的边。

    When tracing Prim’s algorithm in an exam, always draw the current tree and list the candidate crossing edges at each step. Show key values in a table and record which vertex and edge are selected. This makes your reasoning clear and helps avoid arithmetic slips.

    在考试中追踪 Prim 算法时,始终画出当前的树,并在每一步列出候选的横跨边。在表格中显示 key 值,并记录选择了哪个顶点和哪条边。这会让你的推理过程更清晰,并帮助避免计算错误。


    10. Exam-Style Practice Question | 考试风格练习题

    Consider the weighted graph below. The vertices are P, Q, R, S and T. The edge weights are PQ = 7, PR = 5, QR = 3, QS = 4, RS = 2, RT = 6, ST = 5 and QT = 9. Starting at vertex P, use Prim’s algorithm to construct a minimum spanning tree. Show each step clearly.

    考虑下面的带权图。顶点为 P、Q、R、S 和 T。边的权重为 PQ = 7、PR = 5、QR = 3、QS = 4、RS = 2、RT = 6、ST = 5 和 QT = 9。从顶点 P 开始,使用 Prim 算法构造最小生成树。请清楚地展示每一步。

    Solution: Start with P and choose PR = 5. From the visited set {P, R}, the candidate edges are PQ = 7, RQ = 3, RT = 6 and RS = 2. Choose RS = 2. From {P, R, S}, candidates are PQ = 7, RQ = 3, RT = 6, SQ = 4 and ST = 5. Choose RQ = 3. From {P, R, S, Q}, candidates are QT = 9, QS = 4 already visited, RT = 6 and ST = 5. Choose ST = 5. The MST has weight 5 + 2 + 3 + 5 = 15 with edges PR, RS, RQ and ST.

    解答:从 P 开始,选择 PR = 5。从已访问集合 {P, R} 出发,候选边为 PQ = 7、RQ = 3、RT = 6 和 RS = 2。选择 RS = 2。从 {P, R, S} 出发,候选边为 PQ = 7、RQ = 3、RT = 6、SQ = 4 和 ST = 5。选择 RQ = 3。从 {P, R, S, Q} 出发,候选边为 QT = 9、QS = 4 已访问、RT = 6 和 ST = 5。选择 ST = 5。最小生成树的总权重为 5 + 2 + 3 + 5 = 15,包含边 PR、RS、RQ 和 ST。


    11. Summary | 总结

    Prim’s algorithm is a greedy algorithm for finding a minimum spanning tree. It grows the tree one vertex at a time by repeatedly adding the cheapest edge that connects a visited vertex to an unvisited vertex. With clear step-by-step tracing, you can confidently solve MST questions in the Edexcel A-Level Computer Science exam.

    Prim 算法是一种用于寻找最小生成树的贪心算法。它通过不断添加连接已访问顶点与未访问顶点的最便宜边,每次扩展一个顶点。只要按照清晰的步骤逐步追踪,你就能在 Edexcel A-Level 计算机科学考试中自信地解决最小生成树问题。

    Published by TutorHao | Computer Science Revision Series | aleveler.com

    更多咨询请联系16621398022(同微信)