Graph Theory for GCSE OCR Mathematics: Key Points | GCSE OCR 数学：图论考点精讲

📚 Graph Theory for GCSE OCR Mathematics: Key Points | GCSE OCR 数学：图论考点精讲

Graph theory is a fascinating branch of mathematics that models relationships between objects using diagrams made up of points and connecting lines. For the OCR GCSE Mathematics specification, you need to master key concepts including graph terminology, trees, algorithms for minimum spanning trees and shortest paths, and the travelling salesman problem. This revision guide breaks down the entire syllabus into concise, exam-focused sections to help you achieve top marks.

图论是数学的一个迷人分支，它用点和连线构成的图示来模拟对象之间的关系。针对 OCR GCSE 数学考试大纲，你需要掌握图论术语、树、最小生成树与最短路径算法，以及旅行商问题等核心概念。这篇复习指南将整个考纲拆解为精炼、聚焦考点的章节，助你取得高分。

1. What is a Graph? | 什么是图？

A graph is a set of points, called vertices (or nodes), connected by lines, called edges. Graphs are used to model networks such as road maps, social connections, or computer networks. Unlike coordinate graphs from algebra, these graphs do not require an x-y plane; the focus is purely on connections.

图是由称为顶点（或节点）的点以及连接这些点的线（称为边）组成的集合。图用于为道路地图、社交联系或计算机网络等网络建模。与代数中的坐标图不同，这类图不依赖 x-y 平面，纯粹关注连接关系。

In the exam, a graph is usually presented as a labelled diagram. You might be asked to identify the order (number of vertices) or size (number of edges) of a graph, or to draw a graph from a given description.

考试中，图通常以带标签的图示呈现。你可能需要识别图的阶（顶点数）或大小（边数），或根据给定描述画出一个图。

2. Basic Terminology: Vertices, Edges, and Degree | 基本术语：顶点、边与度

A vertex (plural: vertices) is a point where edges meet. An edge is a line segment or curve connecting two vertices. The degree of a vertex is the number of edges incident to it. Loops, where an edge connects a vertex to itself, count twice towards the degree.

顶点是边交汇的点。边是连接两个顶点的线段或曲线。顶点的度是指与该顶点相连的边的数量。若存在连接顶点自身的环，则它对度的贡献算作 2。

Adjacent vertices are connected directly by an edge. A graph can be simple (no loops and no multiple edges between the same pair) or non-simple. Most OCR problems use simple, weighted, undirected graphs, but you should be prepared for directed edges (digraphs) in some contexts.

相邻顶点由一条边直接相连。图可以是简单图（无环且任意两顶点间最多一条边），也可以是非简单图。OCR 的多数问题使用简单、加权、无向图，但在某些情境下你要准备好处理有向边（有向图）。

3. Types of Graphs | 图的类型

A connected graph has a path between every pair of vertices. A disconnected graph contains at least two separate components. A complete graph is a simple graph in which every pair of distinct vertices is connected by a unique edge. The complete graph with n vertices is denoted K_n.

连通图中任意两个顶点之间都存在一条路径。非连通图至少包含两个分离的连通分量。完全图是一种简单图，其中每一对不同的顶点都由唯一一条边相连。有 n 个顶点的完全图记作 K_n。

A weighted graph assigns a numerical value (weight) to each edge, often representing distance, cost, or time. A digraph has directed edges, shown with arrows. A tree is a connected graph with no cycles; we will study trees in detail later.

加权图为每条边分配一个数值（权重），通常表示距离、成本或时间。有向图具有带箭头的有向边。树是没有回路的连通图；稍后我们将详细学习树。

4. Paths, Cycles and Trails | 路径、回路与迹

A walk is a sequence of vertices and edges. A trail is a walk with no repeated edges. A path is a walk with no repeated vertices except possibly the first and last. A cycle (or circuit) is a closed path where the start and end vertices are the same, and no other vertex is repeated.

游走是顶点和边的序列。迹是没有重复边的游走。路径是没有重复顶点的游走（首尾顶点可相同）。回路（或圈）是起点与终点相同的闭合路径，且中间没有重复顶点。

Understanding these terms is crucial for explaining why certain algorithms work. For instance, Kruskal’s algorithm avoids creating cycles, and Dijkstra’s algorithm finds the shortest path.

理解这些术语对于解释算法为何有效至关重要。例如，Kruskal 算法避免产生回路，Dijkstra 算法寻找最短路径。

An Eulerian trail uses every edge exactly once; an Eulerian circuit is an Eulerian trail that starts and ends at the same vertex. A Hamiltonian path visits every vertex exactly once. OCR may ask you to recognise these properties without requiring exhaustive search.

欧拉迹恰好经过每条边一次；欧拉回路是起点和终点相同的欧拉迹。哈密顿路径恰好访问每个顶点一次。OCR 可能会要求你识别这些性质，但不需要进行穷举搜索。

5. 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. A graph can have many different spanning trees.

树是没有回路的连通图。有 n 个顶点的树恰好有 n − 1 条边。连通图的生成树是包含所有顶点且为一棵树的子图。一个图可以有多个不同的生成树。

In weighted graphs, a minimum spanning tree (MST) is a spanning tree with the smallest possible total edge weight. MSTs are used to design efficient networks at minimal cost. You need to be able to find an MST using either Kruskal’s or Prim’s algorithm.

在加权图中，最小生成树（MST）是总边权最小的生成树。MST 用于以最小成本设计高效网络。你需要能够使用 Kruskal 算法或 Prim 算法找出最小生成树。

6. Minimum Spanning Tree: Kruskal’s Algorithm | 最小生成树：Kruskal 算法

Kruskal’s algorithm builds an MST by considering edges in order of increasing weight. If adding the next edge does not create a cycle, include it; otherwise discard it. Repeat until all vertices are connected (n − 1 edges added).

Kruskal 算法按照权重从小到大的顺序考查边。如果添加下一条边不会形成回路就加入，否则丢弃。重复直到所有顶点连通（已添加 n − 1 条边）。

Steps: (1) List all edges in ascending weight. (2) Select the smallest edge that does not form a cycle with already chosen edges. (3) Continue until you have a spanning tree. (4) Write down the edges and total weight. Always draw partial trees to check for cycles.

步骤：(1) 将所有边按权重升序排列。(2) 选择不会与已选边构成回路的最小边。(3) 持续直到得到生成树。(4) 写下边和总权重。一定要画出部分树来检查是否有回路。

Example: For a network with vertices A, B, C, D and edges AB=4, BC=5, CD=3, DA=6, AC=7, BD=8. Sorted: CD(3), AB(4), BC(5), DA(6), AC(7), BD(8). Select CD, then AB, then BC (no cycle yet). Now all 4 vertices connected, total weight 3+4+5=12.

示例：网络有顶点 A,B,C,D，边 AB=4, BC=5, CD=3, DA=6, AC=7, BD=8。排序：CD(3), AB(4), BC(5), DA(6), AC(7), BD(8)。选择 CD，再选 AB，然后 BC（尚未形成回路）。此时 4 个顶点已连通，总权重 3+4+5=12。

7. Minimum Spanning Tree: Prim’s Algorithm | 最小生成树：Prim 算法

Prim’s algorithm grows a tree from a chosen starting vertex. At each step, add the smallest-weight edge that connects a vertex in the tree to a vertex outside the tree. This is sometimes taught as ‘the nearest neighbour’ method for trees, but do not confuse it with the TSP nearest neighbour heuristic.

Prim 算法从选定的起始顶点开始生长一棵树。每一步添加一条连接树内顶点与树外顶点的最小权重边。这有时被教成树的“最近邻”方法，但不要与 TSP 的最近邻启发式混淆。

Steps: (1) Pick any start vertex. (2) From the vertices already in the tree, find the edge of least weight that goes to a vertex not yet in the tree. (3) Add that edge and vertex. (4) Repeat until all vertices are included. (5) Record the order of edge selection and total weight.

步骤：(1) 任选一个起始顶点。(2) 从已在树中的顶点出发，找到通往尚未在树中的顶点的最小权重边。(3) 添加该边和顶点。(4) 重复直到所有顶点都被包含。(5) 记录边选择的顺序和总权重。

Using the same network starting at A: Edges from A: AB=4, AD=6, AC=7. Choose AB(4). Now tree = {A,B}. Options: AD=6, AC=7, BC=5, BD=8 (if available). Choose BC(5). Tree = {A,B,C}. Options: CD=3, AC=7, AD=6 (but A already in). Choose CD(3). Now all vertices in tree. Total weight = 4+5+3 = 12.

使用相同网络，从 A 开始：从 A 出发的边：AB=4, AD=6, AC=7。选 AB (4)。现在树 = {A,B}。可选：AD=6, AC=7, BC=5, BD=8。选 BC (5)。树 = {A,B,C}。可选：CD=3, AC=7, AD=6。选 CD (3)。所有顶点入树，总权重 = 4+5+3 = 12。

8. 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 with non-negative weights. At each stage, you assign and update temporary distance labels, then finalise the smallest tentative distance.

Dijkstra 算法在具有非负权重的加权图中找出从源顶点到所有其他顶点的最短路径。在每一阶段，你分配并更新临时距离标签，然后将最小的暂定距离固定下来。

Steps: (1) Label the start vertex 0, all others ∞. (2) From the set of unvisited vertices, select the one with the smallest label. Mark it as visited. (3) For all neighbours of this vertex, update their labels if the new path is shorter. (4) Repeat until all vertices are visited or you reach the target. (5) The final ordered labels give the shortest distance. You can record the order of working in a table.

步骤：(1) 为起始顶点标 0，其他顶点标 ∞。(2) 从未访问顶点集中选出标签最小的顶点，标记为已访问。(3) 对于该顶点的所有邻居，如果新路径更短就更新其标签。(4) 重复直到所有顶点都被访问或到达目标。(5) 最终的固定标签给出最短距离。你可以用表格记录工作顺序。

Example: vertices S, A, B, T; edges S–A(4), S–B(3), A–T(5), B–T(6), A–B(1). Starting S(0). Unvisited min: S. Update: A=4, B=3. Next min: B(3). Visit B. From B: to A: 3+1=4 (no change), to T: 3+6=9. Next min: A(4). From A: to T: 4+5=9 (no change). Final: S->B->T shortest distance 9, or S->A->T also 9. Both are valid.

示例：顶点 S,A,B,T；边 S–A(4), S–B(3), A–T(5), B–T(6), A–B(1)。从 S(0) 开始。未访问最小：S。更新：A=4, B=3。下一个最小：B(3)。访问 B。从 B 到 A: 3+1=4 (不变)，到 T: 3+6=9。下一个最小：A(4)。从 A 到 T: 4+5=9 (不变)。最终：S->B->T 最短距离 9，或 S->A->T 也是 9。两者均可行。

9. Traveling Salesman Problem (TSP) | 旅行商问题

The Travelling Salesman Problem asks: given a list of cities and distances between them, what is the shortest possible route that visits each city exactly once and returns to the start? This is a Hamiltonian cycle of minimum total weight. TSP is known to be computationally hard, so for GCSE you only need to find upper and lower bounds and interpret practical solutions.

旅行商问题要求：给定城市列表及城市间的距离，找出恰好访问每个城市一次并返回起点的最短可能路线。这是一个总权重最小的哈密顿圈。TSP 在计算上非常困难，因此在 GCSE 你只需找出上界和下界，并解释实际解决方案。

Upper bound (nearest neighbour method): start at any vertex, repeatedly visit the nearest unvisited vertex, then return to start. This gives a quick upper bound. Lower bound: delete a vertex, find the MST of the remaining network, then add the two shortest edges from the deleted vertex to the tree. The higher of such lower bounds gives a good estimate.

上界（最近邻法）：从任意顶点出发，重复访问最近的未访问顶点，最后返回起点。这给出一个快速的上界。下界：删除一个顶点，求出剩余网络的 MST，然后将被删顶点到树的两个最短边加上。取这些下界中的最高值作为良好估计。

Example: Complete graph with 4 vertices, weights: AB=3, AC=4, AD=5, BC=4, BD=6, CD=2. Upper bound from A: nearest B (3), from B nearest C (4), from C nearest D (2), return to A (5). Tour A-B-C-D-A weight 3+4+2+5=14. This is an upper bound. Lower bound: delete A, MST of B,C,D: BC=4, CD=2 (or BD=6 not chosen), tree weight 6. Two shortest edges from A: AB=3, AC=4. Lower bound 6+3+4=13. Optimal tour weight is likely 13 or 14.

示例：4 顶点完全图，权重：AB=3, AC=4, AD=5, BC=4, BD=6, CD=2。从 A 上界：最近 B (3)，从 B 最近 C (4)，从 C 最近 D (2)，返回 A (5)。路线 A-B-C-D-A 权重 3+4+2+5=14。这是一个上界。下界：删除 A，B,C,D 的 MST：BC=4, CD=2，树权重 6。从 A 的两条最短边：AB=3, AC=4。下界 6+3+4=13。最优巡回权重可能是 13 或 14。

10. Graph Representations: Adjacency Matrices | 图的表示：邻接矩阵

An adjacency matrix is a square table that records whether pairs of vertices are adjacent or, in weighted graphs, the weight of the edge connecting them. For a graph with n vertices, the matrix is n × n. Unconnected pairs are often shown as ‘–’ or a very large number.

邻接矩阵是一个记录顶点对之间是否相邻、或在加权图中记录连接边权重的方表。对于有 n 个顶点的图，矩阵为 n×n。未相连的顶点对通常用 ‘–’ 或非常大的数表示。

Example: vertices A,B,C; edges AB=7, BC=5. Matrix (order A,B,C):

–	7	–
7	–	5
–	5	–

This is symmetric for undirected graphs. You may need to draw a graph from a matrix or interpret one. Recognise that the sum of a row gives the degree of that vertex (ignoring ‘–’).

对于无向图，矩阵是对称的。你可能需要根据矩阵画出图，或解读矩阵。注意一行的总和（忽略 ‘–’）给出该顶点的度。

11. Exam Tips and Common Pitfalls | 考试技巧与常见错误

Always show clear working: write down the edge list for Kruskal, the growing tree sketch for Prim, and a labels table for Dijkstra. Marks are often awarded for correct selection orders, not just the final answer.

始终展示清晰的解题过程：Kruskal 写下边表，Prim 画出生长中的树草图，Dijkstra 记录标签表格。分数常常奖励正确的选择顺序，而不仅是最终答案。

Common mistakes include: forgetting to avoid cycles in Kruskal; choosing a wrong edge in Prim by not checking all available edges from the current tree; misreading weighted edges; and confusing TSP upper/lower bound methods. Practice with past paper questions to become familiar with the mark schemes.

常见错误包括：Kruskal 算法中忘记避免回路；Prim 算法中未检查当前树的所有可用边而选错；看错加权边；混淆 TSP 上/下界方法。通过练习历年真题熟悉评分方案。

In Dijkstra, always re-check labels after updating. Use a systematic method to avoid missing a shorter path. If a graph has directed edges, follow arrows carefully. When finding a lower bound for TSP, remember to add back the two shortest edges from the removed vertex to the MST total.

在 Dijkstra 算法中，更新标签后务必重新检查。使用系统的方法避免遗漏更短路径。若图含向边，仔细遵循箭头方向。在求 TSP 下界时，记得将被删顶点的两条最短边加回到 MST 总和中。

Published by TutorHao | Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）