📚 A-Level OCR Mathematics: Graph Theory Key Points | A-Level OCR 数学：图论 考点精讲
Graph theory is a fundamental part of OCR Further Mathematics Decision 1. It provides the language and algorithms to model networks, find efficient routes, and solve optimisation problems. In this revision guide we break down every essential concept, from basic terminology to minimum spanning trees, shortest paths, Eulerian and Hamiltonian graphs, the Travelling Salesman Problem, and matching.
图论是 OCR 进阶数学决策 1 的核心内容，它为建立网络模型、寻找高效路径和解决优化问题提供了语言与算法。本文逐一解析每一个重要考点，包括基本术语、最小生成树、最短路径、欧拉图与哈密顿图、旅行商问题以及匹配等。
1. Basic Terminology | 基本术语
A graph G consists of vertices (nodes) connected by edges (arcs). The degree of a vertex is the number of edges incident to it. A loop is an edge that starts and ends at the same vertex. Two vertices are adjacent if an edge directly connects them. A path is a sequence of distinct vertices where each consecutive pair is adjacent. A cycle (circuit) is a path that starts and ends at the same vertex without repeating any edge.
图 G 由顶点（节点）和连接顶点的边（弧）组成。顶点的度是指与该顶点相连的边的条数。环是一条起点与终点为同一顶点的边。如果两个顶点被一条边直接相连，则它们相邻。路径是一序列互不相同的顶点，且依次相邻。圈（回路）是一条起点与终点重合且不重复任何边的路径。
A graph is simple if it has no loops and no multiple edges between the same pair of vertices. A graph is connected if there is a path between any two vertices. A directed graph (digraph) has edges with a direction indicated by arrows. The order of a graph is its number of vertices, and the size is its number of edges.
若图没有环且任意两个顶点之间最多只有一条边，则称为简单图。如果任意两顶点之间都存在一条路径，则该图是连通的。有向图（有向网络）的边带有用箭头表示的方向。图的阶是其顶点的个数，规模是其边的条数。
2. Matrix Representations | 矩阵表示
Graphs can be stored as matrices. The adjacency matrix is a square matrix A where the entry aᵢⱼ is the number of edges joining vertex i to vertex j (0 if none). For a simple graph, entries are 0 or 1. For an undirected graph, the adjacency matrix is symmetric. A distance matrix is similar but records the weight (length, cost) of each edge; a 0 usually indicates no direct connection, not necessarily distance zero.
图可以用矩阵存储。邻接矩阵是一个方阵 A，其中元素 aᵢⱼ 表示顶点 i 与顶点 j 之间边的条数（没有边则为 0）。对于简单图，元素为 0 或 1。无向图的邻接矩阵是对称的。距离矩阵与之类似，但记录每条边的权重（长度、费用）；矩阵中的 0 通常表示无直接连接，而不是距离为 0。
These matrices are the starting point for many algorithmic processes, such as applying Prim’s algorithm on a table or running Dijkstra’s algorithm. When working with distance tables, remember that the matrix is symmetric for undirected networks.
这些矩阵是许多算法过程的起点，例如在表格上应用普里姆算法，或执行迪杰斯特拉算法。处理距离表时，请记住无向网络的距离矩阵是对称的。
3. Trees and Spanning Trees | 树与生成树
A tree is a connected graph with no cycles. It has exactly (n – 1) edges if it has n vertices. A spanning tree of a connected graph is a subgraph that includes all the vertices and is a tree. In other words, it connects every vertex together without any cycles, possibly leaving out some edges of the original graph.
树是一个无圈的连通图。若一棵树有 n 个顶点，则恰好有 (n – 1) 条边。一个连通图的生成树是一个包含所有顶点的子图，且该子图是一棵树。也就是说，它用不含圈的方式将所有顶点连接在一起，可能会省略原图中的一些边。
For a weighted graph, a minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible. Two classic algorithms used to find the MST are Kruskal’s algorithm and Prim’s algorithm. Both are essential for OCR Decision 1.
对于赋权图，最小生成树（MST）是总边权尽可能小的一棵生成树。寻找最小生成树的两种经典算法是克鲁斯卡尔算法和普里姆算法，两者皆为 OCR 决策 1 的重要考点。
4. Kruskal’s Algorithm | 克鲁斯卡尔算法
Kruskal’s algorithm builds the MST by adding edges in increasing order of weight, provided they do not create a cycle. Steps: (1) List all edges in ascending order of weight. (2) Start with an empty edge list for the MST. (3) Go through the sorted edges and add the next edge to the tree if it connects two different components (i.e., does not form a cycle). (4) Stop when (n – 1) edges have been added.
克鲁斯卡尔算法通过按权重的升序依次添加边来构造最小生成树，条件是所添加的边不会构成圈。步骤：(1) 将所有边按权重升序列出；(2) 从一个空边集开始作为 MST；(3) 依次检查排好序的边，若该边连接两个不同的连通分量（即不构成圈），则将其加入树中；(4) 当已添加 (n – 1) 条边时停止。
In the exam, you may be given a list of edges or a graph. You must clearly show the order of selection and reject any edge that would cause a cycle. Kruskal is particularly convenient when edges are already sorted.
考试中你可能拿到一张边的列表或一幅图。你必须清晰地标明加入边的顺序，并拒绝任何会形成圈的边。当边已经排好序时，克鲁斯卡尔算法尤为方便。
5. Prim’s Algorithm | 普里姆算法
Prim’s algorithm grows the MST from a starting vertex by repeatedly adding the cheapest edge that connects a vertex already in the tree to a vertex not yet in the tree. On a graph, you can show this by colouring chosen edges. In a distance matrix, you cross out chosen rows/columns and look for the smallest number available.
普里姆算法从一个初始顶点开始生长最小生成树，反复添加连接树内顶点与树外顶点的最小权重边。在图上，你可以通过标出已选边来展示算法过程。在距离矩阵中，你需要划去已选的行与列，并找出可用的最小数值。
Matrix Prim: (1) Choose any start vertex and delete its row. Label its column as included. (2) Scan all included columns for the smallest weight in the non-deleted rows. (3) Add that edge, delete the row of the newly chosen vertex, and mark its column. (4) Repeat until all vertices are included. Always show your working.
表格形式的普里姆算法：(1) 任意选择一个起始顶点，删去该行，并标记其列已包含；(2) 在所有已标记列中，找出未被删去的行中的最小权重；(3) 添加该边，将新选顶点所在的行删去，并标记其列；(4) 重复直到所有顶点都被包含。务必展示完整过程。
6. Dijkstra’s Algorithm | 迪杰斯特拉最短路径算法
Dijkstra’s algorithm finds the shortest path from a start vertex to all other vertices in a weighted graph with non-negative weights. It uses permanent labels (boxed) and temporary working values. Steps: (1) Label the start vertex with 0 permanently. (2) For the current vertex, consider all its unlabelled neighbours and calculate their temporary distances. Record the smallest temporary value, along with the order of labelling. (3) Choose the vertex with the smallest temporary value, make its label permanent, and set it as the new current vertex. (4) Repeat until the destination is permanently labelled. Trace back from the destination to obtain the shortest path.
迪杰斯特拉算法用于在非负权图中找出从起点到所有其他顶点的最短路径。它使用永久性标签（方框）与临时工作值。步骤：(1) 将起点的永久标签设为 0；(2) 对当前顶点，考虑其所有尚未永久标记的邻点并计算临时距离，记录最小的临时值以及标记顺序；(3) 选出临时值最小的顶点，将其标签永久化，并设为新的当前顶点；(4) 重复直到目标顶点获得永久标签。从目标反向追踪即可获得最短路径。
OCR exams often require the full working box procedure: a row for each vertex showing the label order, the final permanent value, and the temporary working values updated at each stage. Explain any back-tracing clearly.
OCR 考试通常要求完整的方框法步骤：为每个顶点显示标签顺序、最终永久值和在每个阶段更新的临时工作值。需清晰地说明反向追踪过程。
7. Eulerian Graphs and the Route Inspection Problem | 欧拉图与路径巡视问题
An Eulerian path (trail) is a trail that uses every edge of a graph exactly once. An Eulerian circuit is an Eulerian trail that starts and ends at the same vertex. A connected graph has an Eulerian circuit if and only if every vertex has even degree. It has an Eulerian trail but not a circuit if exactly two vertices have odd degree; the trail must start at one odd-degree vertex and end at the other.
欧拉路径是一条恰好经过图中每条边一次的迹。欧拉回路是起点与终点重合的欧拉路径。一个连通图存在欧拉回路当且仅当每个顶点的度均为偶数。如果一个连通图恰有两个奇数度顶点，则存在欧拉路径但不存在欧拉回路；路径必须从一个奇数度顶点开始，到另一个奇数度顶点结束。
The Route Inspection (Chinese Postman) problem asks for the shortest route that traverses every edge at least once. If all vertices are even, the optimum route is simply an Eulerian circuit. If there are odd-degree vertices, we pair them up to minimise the total extra distance by repeating edges. The algorithm finds the minimum weight matching of the odd vertices and adds these repeated edges to the network.
路径巡视（中国邮递员）问题要求找出一条至少遍历每条边一次的最短路线。若所有顶点都是偶度，最优路线即一条欧拉回路。若存在奇数度顶点，则需将它们两两配对并重复某些边，以便使总额外距离最小。算法为奇度顶点寻找最小权匹配，然后将这些重复边加入网络中。
8. Hamiltonian Graphs and the Travelling Salesman Problem | 哈密顿图与旅行商问题
A Hamiltonian cycle (circuit) is a cycle that visits every vertex exactly once before returning to the start. There is no simple condition like Euler’s theorem to determine whether a graph is Hamiltonian; it is generally harder. The Travelling Salesman Problem (TSP) is to find a minimum-weight Hamiltonian cycle in a complete weighted graph, visiting each vertex exactly once and returning to the start.
哈密顿圈是一个访问每个顶点恰好一次并返回起点的圈。不存在类似欧拉定理的简单条件来判定一个图是否具有哈密顿圈，问题通常更为困难。旅行商问题（TSP）是在完全赋权图中寻找一个最小权哈密顿圈，要求访问每个顶点恰好一次并返回起点。
Since the TSP is computationally hard, for OCR we use heuristic methods to find an upper bound and a lower bound for the optimal tour length. The quality of the solution is often judged by how close the upper bound is to the lower bound.
由于 TSP 计算复杂，OCR 要求使用启发式方法找出最优巡回路长度的上界和下界。通常通过比较上界与下界的接近程度来评判解的质量。
9. Bounds for the Travelling Salesman Problem | 旅行商问题的界限
Upper bounds: The nearest neighbour algorithm provides a quick upper bound. Start at any vertex, repeatedly go to the nearest unvisited vertex, and finally return to the start. This gives a feasible tour, not necessarily optimal. Other methods like using a better starting point or improving by swapping can be used.
上界：最近邻算法可快速提供一个上界。从任意顶点出发，反复前往最近的尚未访问过的顶点，最后返回起点。这样得到一条可行巡回路，但不一定最优。也可通过尝试不同起点或使用边交换改进等方法求更小的上界。
Lower bounds: The most common method for a complete graph is to remove a vertex, find a minimum spanning tree of the remaining vertices, and then add the two shortest edges from the removed vertex to the tree. This gives a lower bound for any tour. You may need to repeat this for different removed vertices and take the greatest lower bound.
下界：对于完全图，最常用的方法是删去一个顶点，求出剩余顶点的最小生成树，再将该树与被删顶点的两条最短边相加。这样得到一个巡回路的下界。可能需要针对不同被删的顶点重复此过程，并取最大的下界作为更强的下界。
Exam questions often ask for an upper bound using nearest neighbour and a lower bound by deleting a vertex. You must clearly show the MST used, the two added edge weights, and the calculation. The optimal tour length lies between the best lower bound and the best upper bound.
试题常要求用最近邻法求上界，并通过删去一个顶点求下界。你必须清晰地展示所用的生成树、添加的两条边权以及计算过程。最优巡回路长度介于最佳下界与最佳上界之间。
10. Matching Problems | 匹配问题
A matching is a set of edges with no shared vertices. In a bipartite graph, the vertices are partitioned into two sets and each edge runs between the sets. A maximum matching is a matching with the largest possible number of edges. OCR D1 uses the alternating path algorithm to find a maximum matching. Start with an initial matching (maybe empty or given), then look for an alternating path that starts and ends at unmatched vertices. If such a path exists, the matching can be improved by changing the status of edges along the path.
匹配是一组没有公共顶点的边。在二分图中，顶点被划分为两个集合，每条边都跨越两个集合。最大匹配是包含边数最多的匹配。OCR D1 使用交错路径算法寻找最大匹配。从某个初始匹配（可能为空或已给出）开始，然后寻找起点和终点都是未匹配顶点的交错路径。若找到这样的路径，则可通过切换路径上边的状态来改进匹配。
The algorithm terminates when no more alternating paths from an unmatched vertex lead to another unmatched vertex. You must draw the bipartite graph, clearly indicate the alternating path, and show the updated matching. This topic also appears in context problems like allocating tasks to workers or pairing students to courses.
当不再存在从一个未匹配顶点到另一个未匹配顶点的交错路径时，算法终止。你必须画出二分图，清楚地标出交错路径，并展示更新后的匹配。该主题也出现在将任务分配给工人或学生配对课程等情境问题中。
11. Summary of Key Points | 考点总结
Graph theory in OCR Decision 1 focuses on algorithmic thinking and systematic recording of steps. Remember: degree conditions decide Eulerian trails; trees have (n – 1) edges; Kruskal and Prim both produce a minimum spanning tree but work differently; Dijkstra yields shortest paths with non-negative weights; route inspection uses pairing of odd vertices; TSP bounds are constructed via spanning trees and nearest neighbour; matching is solved by augmenting alternating paths. Always show every step of your working clearly, label final values, and use the correct notation for edges, vertices, and weights.
OCR 决策 1 中的图论强调算法思维和步骤的系统记录。记住：度条件决定欧拉路径；树有 (n – 1) 条边；克鲁斯卡尔和普里姆算法都能生成最小生成树但过程不同；迪杰斯特拉算法给出非负权的最短路径；路径巡视利用奇数度顶点的配对；TSP 的界限通过生成树和最近邻法构建；匹配问题依靠增广交错路径解决。务必清晰展示每一步操作，标记最终值，并使用正确的边、顶点和权重符号。
Practice plenty of past paper questions, as the OCR paper expects you to apply algorithms accurately under time pressure. Good luck!
多做往年真题，因为 OCR 试卷要求你在时间压力下准确应用算法。祝你好运！
Published by TutorHao | OCR Decision 1 Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply