GCSE AQA Mathematics: Graph Theory Revision Notes | GCSE AQA 数学：图论考点精讲

📚 GCSE AQA Mathematics: Graph Theory Revision Notes | GCSE AQA 数学：图论考点精讲

Graph theory is a key topic in the AQA GCSE Mathematics specification, focusing on networks, vertices, edges, and algorithms such as Kruskal’s and Dijkstra’s. Mastering these concepts will help you solve real-world problems involving routes, connections, and optimisation. This guide covers all the essential definitions, techniques, and exam tips you need to succeed.

图论是AQA GCSE数学大纲中的一个重要主题，重点涉及网络、顶点、边以及Kruskal和Dijkstra等算法。掌握这些概念能帮助你解决涉及路线、连接和优化的实际问题。本指南涵盖了你所需的所有基本定义、技巧和考试提示，助你取得成功。

1. Introduction to Graphs | 图论简介

A graph is a mathematical structure used to model pairwise relationships between objects. It consists of vertices (also called nodes) and edges that connect pairs of vertices. Graphs are widely used in transport networks, social networks, and scheduling problems.

图是一种用于对对象之间成对关系进行建模的数学结构。它由顶点（也称为节点）和连接顶点对的边组成。图被广泛应用于交通网络、社交网络和调度问题中。

In GCSE Mathematics, you will learn to represent information as a graph, identify special types of graphs, and apply algorithms to solve problems such as finding the shortest path or the minimum spanning tree.

在GCSE数学中，你将学习将信息表示为图，识别特殊类型的图，并应用算法来解决诸如寻找最短路径或最小生成树等问题。

Vertices are usually drawn as points or circles, while edges are drawn as lines or curves connecting them. A graph does not need to be drawn to scale, and the layout is not fixed – only the connections matter.

顶点通常用点或圆圈表示，而边则用连接它们的直线或曲线表示。图不必按比例绘制，布局也不固定——只有连接关系是重要的。

2. Key Terminology: Vertices, Edges, Degree | 关键术语：顶点、边、度

A vertex (plural: vertices) is a fundamental unit of a graph. An edge is a line joining two vertices. The degree of a vertex is the number of edges incident to it. For example, if a vertex has three edges connected to it, its degree is 3.

顶点（复数：vertices）是图的基本单元。边是连接两个顶点的线段。顶点的度是指与该顶点相连的边的数量。例如，如果一个顶点连接了三条边，则它的度为3。

A loop is an edge that connects a vertex to itself; it contributes 2 to the degree of that vertex. A simple graph has no loops and no multiple edges between the same pair of vertices. In GCSE, we mostly work with simple graphs.

环是一条连接顶点自身的边；它为该顶点的度贡献2。简单图没有环，且同一对顶点之间没有多条边。在GCSE中，我们主要研究简单图。

The handshaking lemma states that the sum of the degrees of all vertices in a graph is equal to twice the number of edges. This is often written as:

握手引理指出，图中所有顶点的度数之和等于边数的两倍。这通常写作：

∑ deg(v) = 2E

This is a useful result for checking your work and solving problems involving unknown degrees. Adjacent vertices are those directly connected by an edge. A path is a sequence of vertices where each consecutive pair is joined by an edge, with no vertex repeated. A cycle is a closed path where the start and end vertex are the same, and all other vertices are distinct.

这是一个有用的结论，可用于检查工作并解决涉及未知度数的问题。相邻顶点是指由边直接连接的顶点。路径是一个顶点序列，其中每对连续顶点都由一条边连接，且没有重复的顶点。回路是一个闭合路径，其中起点和终点相同，其余顶点各不相同。

3. Types of Graphs | 图的分类

A simple graph has no loops or multiple edges. A connected graph is one in which there is a path between every pair of vertices. A complete graph is a simple graph in which every pair of distinct vertices is connected by exactly one edge. The complete graph with n vertices is denoted Kₙ. For example, K₄ has 4 vertices and 6 edges.

简单图没有环或多重边。连通图是指图中每对顶点之间都存在路径。完全图是一种简单图，其中每对不同的顶点都恰好由一条边连接。具有n个顶点的完全图记作Kₙ。例如，K₄有4个顶点和6条边。

A bipartite graph is one whose vertices can be divided into two disjoint sets, such that every edge connects a vertex from one set to a vertex from the other. No edge connects vertices within the same set. A tree is a connected graph with no cycles. Trees have important properties: a tree with n vertices always has exactly n − 1 edges, and any two vertices are connected by exactly one simple path.

二分图是这样一种图：其顶点可被划分为两个不相交的集合，使得每条边都连接一个集合中的顶点与另一个集合中的顶点。同一集合内的顶点之间没有边。树是一种无回路的连通图。树具有重要性质：具有n个顶点的树恰好有n − 1条边，并且任意两个顶点之间恰好由一条简单路径连接。

A directed graph or digraph has edges with a direction, often represented with arrows. A weighted graph assigns a numerical weight to each edge, which might represent distance, cost, or time. In GCSE, weighted graphs are used extensively in algorithms.

有向图或 digraph 具有带方向的边，通常用箭头表示。加权图为每条边分配一个数值权重，可以表示距离、成本或时间。在GCSE中，加权图广泛用于算法中。

A subgraph is a graph formed from a subset of vertices and edges of the original graph. You will often need to identify subgraphs, such as spanning trees.

子图是由原图的顶点和边的子集构成的图。你经常需要识别子图，例如生成树。

4. Eulerian Paths and Circuits | 欧拉路径与回路

An Eulerian trail (or Eulerian path) is a trail that visits every edge of a graph exactly once. An Eulerian circuit (or Eulerian cycle) is an Eulerian trail that starts and ends at the same vertex. A graph that contains an Eulerian circuit is called an Eulerian graph.

欧拉轨迹（或欧拉路径）是一条恰好经过图中每条边一次的轨迹。欧拉回路（或欧拉环）是一条起点和终点相同的欧拉轨迹。包含欧拉回路的图称为欧拉图。

According to Euler’s theorem, a connected graph has an Eulerian circuit if and only if every vertex has an even degree. It has an Eulerian trail but no Eulerian circuit if and only if exactly two vertices have odd degree; the trail must start at one of these odd-degree vertices and end at the other. If there are more than two vertices of odd degree, no Eulerian trail exists.

根据欧拉定理，一个连通图有欧拉回路当且仅当每个顶点的度数均为偶数。它有欧拉轨迹但没有欧拉回路当且仅当恰好有两个顶点的度数为奇数；轨迹必须从其中一个奇度顶点开始，到另一个奇度顶点结束。如果有超过两个顶点的度数为奇数，则不存在欧拉轨迹。

You may be asked to determine if a graph has an Eulerian trail or circuit, and if so, to find one. Use the degree condition to decide, then carefully trace edges without reusing any until all are covered.

你可能会被要求判断一个图是否有欧拉轨迹或回路，如果有，就要找出一条。利用度数条件来判断，然后仔细地描出边且不重复使用任何边，直到覆盖所有边。

5. Hamiltonian Paths and Circuits | 汉密尔顿路径与回路

A Hamiltonian path visits every vertex of a graph exactly once. A Hamiltonian cycle (or circuit) is a Hamiltonian path that returns to the starting vertex. Unlike Eulerian paths, there is no simple necessary and sufficient condition to determine whether a Hamiltonian path or cycle exists; you must find one by inspection or systematic trial.

汉密尔顿路径恰好访问图中每个顶点一次。汉密尔顿回路（或环）是一条能回到起点的汉密尔顿路径。与欧拉路径不同，没有简单的充要条件来判断汉密尔顿路径或回路是否存在；你必须通过观察或系统尝试来找到一条。

In exam questions, you might be given a graph and asked to find a Hamiltonian cycle. A useful strategy is to list all vertices, choose a starting point, and try to visit each vertex exactly once, ensuring the final step returns to the start. Not all graphs have Hamiltonian cycles; for example, a tree with more than two vertices cannot have one because trees have no cycles.

在考试题目中，可能会给你一个图并要求找出一条汉密尔顿回路。一个有用的策略是列出所有顶点，选择一个起点，然后尝试恰好访问每个顶点一次，并确保最后一步回到起点。并非所有图都有汉密尔顿回路；例如，具有多于两个顶点的树就不可能有，因为树没有回路。

The concept is important for problems like the travelling salesman problem, which you may encounter in decision mathematics later.

这一概念对诸如旅行商问题等重要问题至关重要，你可能在以后的决策数学中会碰到。

6. Trees and Spanning Trees | 树与生成树

A tree is a connected graph with no cycles. Key properties: a tree with n vertices has exactly n − 1 edges; removing any edge disconnects the tree; adding any edge creates exactly one cycle. A spanning tree of a connected graph is a subgraph that includes all the vertices and is a tree. Every connected graph has at least one spanning tree.

树是一种无回路的连通图。关键属性：具有n个顶点的树恰好有n − 1条边；移除任何一条边都会使树不连通；添加任何一条边都会恰好创建一个回路。连通图的生成树是一个包含所有顶点的子图，且该子图是一棵树。每个连通图至少有一棵生成树。

A minimum spanning tree (MST) is a spanning tree with the smallest possible total edge weight in a weighted graph. MST problems appear frequently in network design, such as laying cables or pipelines at minimum cost.

最小生成树（MST）是加权图中具有最小可能总边权重的生成树。MST问题常出现在网络设计中，例如以最低成本铺设电缆或管道。

To find a spanning tree from a graph, you can remove edges that are part of cycles while ensuring the graph remains connected. For an MST, you must use an algorithm.

要从图中找出一棵生成树，可以在保持图连通的同时，移除属于回路的边。对于最小生成树，你必须使用算法。

7. Kruskal’s Algorithm for Minimum Spanning Tree | 最小生成树之Kruskal算法

Kruskal’s algorithm finds a minimum spanning tree for a connected, weighted graph. The steps are:

Kruskal算法为连通加权图寻找最小生成树。步骤如下：

List all edges in order of increasing weight.

将所有边按权重递增的顺序列出。
Start with an empty set of edges for your spanning tree.

从一个空的边集开始，作为生成树。
Go through the sorted list, adding the next edge if it does not create a cycle with the edges already chosen.

遍历排序后的列表，如果下一条边不会与已选边形成回路，则将其加入。
Stop when you have added exactly (n − 1) edges, where n is the number of vertices.

当添加了恰好(n − 1)条边时停止，其中n是顶点数。

To check for cycles, you can use a quick visual method or draw the partial tree. If an edge connects two vertices already connected by a path using chosen edges, it would form a cycle, so reject it.

要检查回路，你可以使用快速视觉方法或画出部分树。如果一条边连接的两个顶点已经通过已选边形成了通路，那么加入该边就会形成一个回路，因此拒绝该边。

Example: Consider a network with vertices A, B, C, D, and edges: AB (weight 4), AC (2), AD (5), BC (3), BD (6), CD (1). Sorted edges: CD(1), AC(2), BC(3), AB(4), AD(5), BD(6). Choose CD, AC. Next BC: does not form cycle (C-D-A path exists? A-C and C-D, so A and D are connected, but BC connects B-C; B is not yet connected to C-D-A, so safe – actually check: vertices A, C, D are connected via A-C and C-D, B is isolated. Adding BC connects B to C, no cycle, so add BC. We now have 3 edges for 4 vertices, so stop. MST edges: CD, AC, BC; total weight = 1+2+3 = 6.

示例：考虑顶点为A、B、C、D的网络，边为：AB（权重4）、AC（2）、AD（5）、BC（3）、BD（6）、CD（1）。排序后的边：CD(1)、AC(2)、BC(3)、AB(4)、AD(5)、BD(6)。选择CD、AC。下一条BC：不会形成回路（存在C-D-A路径？A-C和C-D，所以A和D已连接，但BC连接B-C；B尚未与C-D-A相连，所以安全——实际上检查：顶点A、C、D通过A-C和C-D连通，B是孤立的。加入BC将B连接到C，无回路，因此加入BC。现在4个顶点有了3条边，停止。MST边为：CD、AC、BC；总权重 = 1+2+3 = 6。

8. Dijkstra’s Algorithm for Shortest Path | 最短路径之Dijkstra算法

Dijkstra’s algorithm finds the shortest path from a start vertex to all other vertices in a weighted graph with non-negative edge weights. The algorithm works by maintaining a set of visited vertices and repeatedly updating the shortest known distance to each unvisited neighbour.

Dijkstra算法用于在具有非负边权重的加权图中，寻找从起点到所有其他顶点的最短路径。该算法通过维护一个已访问顶点集合，并不断更新到每个未访问邻居的已知最短距离来工作。

Algorithm steps:

算法步骤：

Label the start vertex with distance 0 and all other vertices with distance ∞ (infinity). Mark the start vertex as current.

将起始顶点标为距离0，其他所有顶点标为距离∞（无穷大）。将起始顶点标记为当前顶点。
For the current vertex, consider all its unvisited neighbours. Calculate their tentative distance: current vertex’s distance + weight of the connecting edge. If this is less than the neighbour’s recorded distance, update it.

对于当前顶点，考虑其所有未访问的邻居。计算其试探距离：当前顶点的距离 + 连接边的权重。如果该值小于邻居已记录的距离，则更新它。
After considering all neighbours, mark the current vertex as visited. A visited vertex will not be checked again.

考虑完所有邻居后，将当前顶点标记为已访问。已访问的顶点将不再被检查。
Select the unvisited vertex with the smallest tentative distance as the new current vertex, and repeat from step 2. Continue until the destination vertex is marked visited or all vertices are visited.

选择具有最小试探距离的未访问顶点作为新的当前顶点，并从步骤2重复。持续进行，直到目标顶点被标记为已访问或所有顶点均被访问。

To record the actual path, keep track of the predecessor vertex that gave the best distance. You can then trace back from the destination to the start.

要记录实际路径，可以跟踪产生最佳距离的前驱顶点。然后你可以从目标倒推回起点。

Example: Find the shortest path from A to D in the previous network. Initial: A=0, others=∞. Current A: neighbours B (via 4) → update B=4, C (via 2) → C=2. Mark A visited. Smallest unvisited is C (2). Current C: neighbours A (visited, ignore), B (via 3) → 2+3=5, compare with B=4, no update; D (via 1) → 2+1=3, update D=3. Mark C visited. Next smallest is D (3) but it’s our target, or B (4). We can stop once D is marked. Shortest distance A-D = 3 via A-C-D.

示例：在之前的网络中找到从A到D的最短路径。初值：A=0，其余=∞。当前A：邻居B（经4）→ 更新B=4，C（经2）→ C=2。标记A为已访问。最小未访问是C（2）。当前C：邻居A（已访问，忽略）、B（经3）→ 2+3=5，与B=4比较，不更新；D（经1）→ 2+1=3，更新D=3。标记C已访问。下一个最小是D（3）或B（4），当D被标记时可以停止。最短距离A-D = 3，路径A-C-D。

9. Exam Techniques and Common Pitfalls | 考试技巧与常见错误

Always read the question carefully – identify whether you need to find an Eulerian trail, Hamiltonian cycle, minimum spanning tree, or shortest path. Use the correct algorithm and show all working clearly. When running Dijkstra’s algorithm, even if you can see the shortest path, you must still demonstrate the table or systematic updates to earn full marks.

务必仔细读题——判断是需要寻找欧拉轨迹、汉密尔顿回路、最小生成树还是最短路径。使用正确的算法并清晰地展示所有步骤。在运用Dijkstra算法时，即使你能看出最短路径，也必须展示表格或系统更新过程，才能获得满分。

Common mistakes include confusing Eulerian and Hamiltonian concepts, forgetting to check for cycles when applying Kruskal, and misordering edges by weight. Double-check that you have added exactly n − 1 edges in Kruskal’s algorithm. For Dijkstra, avoid updating visited vertices and ensure you select the smallest tentative distance each time. Practise drawing graphs neatly and labelling vertices; a messy diagram can lead to errors.

常见错误包括混淆欧拉和汉密尔顿概念、在应用Kruskal算法时忘记检查回路、以及按权重排序边时出错。请仔细检查是否在Kruskal算法中恰好添加了n − 1条边。对于Dijkstra，避免更新已访问的顶点，并确保每次都选择最小的试探距离。多练习整洁地绘制图形并标记顶点；杂乱的图容易导致错误。

If a question asks you to explain why a certain path is impossible, refer to degree conditions or tree properties. When dealing with word problems, translate the scenario into a clear graph: vertices represent locations or objects, edges represent connections, and weights represent distances, times, or costs.

如果题目要求解释某条路径为何不可能，请引用度数条件或树的性质。在处理应用题时，将情景转化为清晰的图：顶点代表地点或对象，边代表连接，权重代表距离、时间或成本。

Published by TutorHao | Mathematics Revision Series | aleveler.com

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

GCSE AQA Mathematics: Graph Theory Revision Notes | GCSE AQA 数学：图论考点精讲