📚 AQA Mathematics: Graph Theory Key Points | AQA 数学：图论 考点精讲
Graph theory is a central topic in AQA Decision Mathematics, providing tools to model and solve real-world problems such as network design, shortest routes, and logistics. Mastering the key algorithms and their applications is essential for the exam.
图论是 AQA 决策数学的核心主题，为网络设计、最短路径和物流等现实问题提供了建模和求解工具。掌握关键算法及其应用对考试至关重要。
1. Basic Graph Terminology | 图的基本术语
A graph consists of vertices (nodes) connected by edges (arcs). The degree of a vertex is the number of edges incident to it. A path is a sequence of distinct vertices where consecutive vertices are adjacent. A cycle is a closed path that starts and ends at the same vertex without repeating edges.
图由通过边（弧）连接的顶点（节点）组成。顶点的度是与该顶点相连的边的数量。路径是一个顶点序列，其中连续顶点相邻，且顶点互不相同。回路（圈）是一条闭合路径，起点与终点相同且不重复经过任何边。
A graph is connected if there is a path between every pair of vertices. A simple graph has no loops and no multiple edges. In a weighted graph, each edge is assigned a numerical value, often representing distance, time, or cost.
如果任意两顶点间都存在路径，则该图是连通的。简单图没有环和多重边。在加权图中，每条边都赋有一个数值，通常表示距离、时间或成本。
A digraph (directed graph) has edges with direction. A complete graph Kn has n vertices, each pair of vertices joined by exactly one edge.
有向图（有向图）的边具有方向。完全图 Kn 有 n 个顶点，且每对顶点之间恰好有一条边相连。
2. Trees and Spanning Trees | 树与生成树
A tree is a connected graph with no cycles. A tree with n vertices always has exactly n – 1 edges. A spanning tree of a connected graph is a subgraph that includes all the vertices and is a tree.
树是一个无环的连通图。具有 n 个顶点的树恒有恰好 n – 1 条边。连通图的生成树是包含所有顶点的树形子图。
A minimum spanning tree (MST) is a spanning tree with the smallest possible total edge weight. Kruskal’s and Prim’s algorithms are used to find the MST.
最小生成树（MST）是总边权最小的生成树。Kruskal 算法和 Prim 算法用于寻找最小生成树。
3. Minimum Spanning Tree: Kruskal’s Algorithm | 最小生成树：Kruskal 算法
Step 1: List all edges in ascending order of weight.
步骤1：按权重升序列出所有边。
Step 2: Select the edge with the smallest weight that does not form a cycle with already chosen edges.
步骤2：选择权重最小且不与已选边形成环的边。
Step 3: Repeat Step 2 until you have selected (n – 1) edges, where n is the number of vertices.
步骤3：重复步骤2，直至选中 (n – 1) 条边，其中 n 为顶点数。
Use a table to sort edges and keep track of which vertices are already connected to avoid cycles.
使用表格对边进行排序，并跟踪已连通的顶点以避免环。
Algorithm table (example):
算法表格（示例）：
| Edge | Weight | Action | Reason |
|---|---|---|---|
| CF | 8 | Add | Connects C and F, no cycle |
| AD | 10 | Add | Connects A and D |
| … | … | Reject | Would create cycle |
4. Minimum Spanning Tree: Prim’s Algorithm | 最小生成树：Prim 算法
Step 1: Start at any vertex. Mark it as connected.
步骤1：从任意顶点开始，并将其标记为已连接。
Step 2: Choose the edge of minimum weight connecting a connected vertex to an unconnected vertex. Add the edge and mark the new vertex as connected.
步骤2：选择连接已连接顶点与未连接顶点的最小权重边。将该边加入，并将新顶点标记为已连接。
Step 3: Repeat Step 2 until all vertices are connected. Record the order of edge selection.
步骤3：重复步骤2，直至所有顶点均已连接。记录边的选择顺序。
Prim’s is efficient when edges are given in a matrix form. Create a table showing the shortest distance from any connected vertex to each unvisited vertex at each stage.
当边以矩阵形式给出时，Prim 算法效率较高。可以创建一个表格，展示每个阶段从任意已连接顶点到每个未访问顶点的最短距离。
Prim’s matrix/table approach (distance from connected set):
Prim 矩阵/表格法（与已连接集的距离）：
| Vertex | Step 1 (A) | Step 2 (A,B) | … |
|---|---|---|---|
| A | – | – | – |
| B | 12 | – | – |
| C | ∞ | 9 | … |
5. Shortest Path: Dijkstra’s Algorithm | 最短路径：Dijkstra 算法
Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph (weights must be non‑negative).
Dijkstra 算法可在加权图（权重必须非负）中找出从源顶点到其他所有顶点的最短路径。
Step 1: Label the start vertex with permanent label 0. All other vertices get temporary label ∞.
步骤1：将起点标记为永久标号 0。其他所有顶点暂时标号 ∞。
Step 2: From the most recently permanently labelled vertex, update temporary labels of its unvisited neighbours: if (permanent label + edge weight) < current temporary label, replace it.
步骤2：从最新拥有永久标号的顶点出发，更新其未访问邻居的暂时标号：若 (永久标号 + 边权) < 当前暂时标号，则替换。
Step 3: Choose the smallest temporary label, make it permanent, and repeat from Step 2 until the destination (or all vertices) are permanently labelled.
步骤3：选择最小的暂时标号，将其设为永久，并从步骤2重复，直至目标顶点（或所有顶点）均被永久标号。
Record the working values in a neat box table. The final permanent label gives the shortest distance; the route is traced backwards using labels or a separate predecessor column.
用整洁的方框表格记录工作值。最终的永久标号即为最短距离；可通过标号或前驱列反向追溯路径。
Dijkstra table (start vertex A):
Dijkstra 表格（起点 A）：
| Step | A | B | C | D | Permanent |
|---|---|---|---|---|---|
| 1 | 0 | ∞ | ∞ | ∞ | A |
| 2 | 7,A | 3,A | 16,A | C | |
| 3 | 5,C | 11,C | B |
6. Eulerian Graphs and Route Inspection | 欧拉图与路线检查问题
An Eulerian trail uses every edge exactly once. A graph has an Eulerian trail that starts and ends at different vertices if exactly two vertices have odd degree (semi‑Eulerian). It has an Eulerian circuit (starting and ending same vertex) if all vertices have even degree (Eulerian).
欧拉迹恰好经过每条边一次。若一个图中恰有两个奇度顶点，则该图存在起点和终点不同的欧拉迹（半欧拉图）。若所有顶点均为偶度，则存在欧拉回路（起点终点相同，欧拉图）。
The Route Inspection (Chinese Postman) problem requires covering every edge at least once and returning (or not) to the start. For a semi‑Eulerian graph, a least‑weight duplicate path must be added between the two odd nodes to make degrees even. The total weight = sum of all edges + weight of shortest path connecting the odd vertices.
路线检查问题（中国邮递员问题）要求至少经过每条边一次，并可选择是否返回起点。对于半欧拉图，必须在两个奇度节点间添加一条最小权重重复路径，使其度变为偶数。总权重 = 所有边权之和 + 连接奇度顶点的最短路径权重。
Exam tip: Identify odd vertices, use Dijkstra to find the shortest distance between them, and add this length to the total to get the minimal route length.
应试技巧：找出奇度顶点，使用 Dijkstra 求出它们之间的最短距离，并将该长度加到总权重中即为最短路线长度。
7. The Travelling Salesman Problem | 旅行商问题
The Travelling Salesman Problem (TSP) seeks the shortest Hamiltonian cycle (visiting every vertex exactly once and returning to the start) in a complete weighted graph. Finding the exact optimal tour is computationally hard; hence we use approximation algorithms.
旅行商问题（TSP）要求在完全加权图中寻找最短的哈密尔顿回路（恰好经过所有顶点一次并返回起点）。精确最优解计算困难，因此我们使用近似算法。
We find both an upper bound (a feasible tour length) and a lower bound (the minimum possible tour length). The optimal tour length lies between the best upper bound and the best lower bound.
我们找出上界（一个可行回路长度）和下界（可能的最小回路长度）。最优回路长度介于最佳上界和最佳下界之间。
8. Nearest Neighbour Algorithm | 最近邻算法
The nearest neighbour algorithm provides an upper bound for the TSP. Step 1: Start at any vertex.
最近邻算法为 TSP 提供上界。步骤1：任意选择一个起点。
Step 2: From your current vertex, go to the nearest unvisited vertex. Repeat until all vertices are visited.
步骤2：从当前顶点前往最近的未访问顶点。重复此操作，直至访问所有顶点。
Step 3: Return directly from the last vertex to the start. The total length of this tour is an upper bound.
步骤3：从最后一个顶点直接返回起点。此回路的总长度即为一个上界。
Repeat the algorithm starting from each vertex (or several) to find the best (smallest) upper bound.
从每个（或若干个）顶点出发重复此算法，以找到最佳（最小）上界。
9. Lower Bound Using Minimum Spanning Tree | 利用最小生成树求下界
To find a lower bound, delete one vertex (say A) and all its incident edges. Find the minimum spanning tree (MST) for the remaining vertices.
要求下界，可删除一个顶点（例如 A）及其所有关联边。为剩余顶点找出最小生成树（MST）。
Add the two shortest edges from the deleted vertex to the MST. This sum gives a lower bound. Repeat this process deleting a different vertex each time, and take the greatest lower bound obtained.
将 MST 的权重加上从被删顶点出发的两条最短边的权重。此和即为一个下界。对不同的顶点重复此过程，并取最大下界。
The optimal tour length cannot be less than this lower bound. The gap between the best upper and best lower bound indicates the quality of the approximation.
最优回路长度不可能低于此下界。最佳上界与最佳下界之间的差值反映了近似解的质量。
10. Summary and Exam Tips | 总结与应试技巧
Always show clear working: use tables for Dijkstra and Prim, and list edges in order for Kruskal. State whether you are finding an upper or lower bound and explain each step in the context of the problem.
始终展示清晰的解题过程：Dijkstra 和 Prim 使用表格，Kruskal 按序列出边。说明你在求上界还是下界，并在问题情境中解释每一步。
Check degree of vertices for Eulerian problems; remember that a Hamiltonian cycle must visit each vertex exactly once. For TSP bounds, calculate multiple starting points for the nearest neighbour algorithm and delete different vertices for the lower bound to ensure you have the best possible values.
对于欧拉问题，检查顶点的度；记住哈密尔顿回路必须恰好经过每个顶点一次。对于 TSP 定界，要从多个起点计算最近邻算法，并删除不同顶点来计算下界，以确保得到可能的最佳值。
Manage your time: knowing the algorithm steps by heart will save precious minutes in the exam. Practise interpreting real‑world scenarios as graph problems.
合理安排时间：熟记算法步骤能为考试节省宝贵时间。练习将实际情景转化为图论问题。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply