📚 WJEC GCSE Maths: Graph Theory – Key Points | GCSE WJEC 数学：图论 考点精讲
Welcome to this focused revision guide on Graph Theory for WJEC GCSE Mathematics. Graph theory is a topic in discrete mathematics that appears on the higher tier paper. You will be expected to understand the fundamental definitions, interpret and construct adjacency matrices, solve route inspection problems (Eulerian trails/circuits), tackle the travelling salesman problem (Hamiltonian cycles), find minimum spanning trees using Kruskal’s and Prim’s algorithms, and calculate shortest paths with Dijkstra’s algorithm. This article breaks down each key concept with clear explanations, worked examples using proper notation, and exam tips to help you secure full marks.
欢迎阅读这份针对 WJEC GCSE 数学图论的专项复习指南。图论属于离散数学部分，出现在高等级试卷中。你需要掌握基本定义，能解读和构建邻接矩阵，解决路线检验问题（欧拉路径/回路），处理旅行商问题（哈密顿回路），使用克鲁斯卡尔算法和普里姆算法求最小生成树，以及运用迪杰斯特拉算法计算最短路径。本文拆解每个核心概念，用清晰的解释、规范的符号示例和考试技巧帮助你稳稳拿分。
1. What is a Graph? | 图的基本概念
A graph is a collection of points called vertices (or nodes) connected by lines called edges. Graphs are used to model networks such as roads, circuits, or social connections. A graph is defined by its vertex set V and its edge set E. Edges can be represented as unordered pairs of vertices, e.g. edge between vertex A and vertex B is written as AB.
图是由称为顶点（或节点）的点以及连接它们的称为边的线所组成的集合。图被用来对网络建模，比如道路、电路或社交关系。一个图由它的顶点集 V 和边集 E 定义。边可以用无序顶点对表示，例如顶点 A 和顶点 B 之间的边记作 AB。
An edge may be a loop (connecting a vertex to itself), but in GCSE problems loops are rarely used. If an edge has a direction it is called a directed edge, but WJEC graph theory questions almost exclusively deal with undirected graphs. Multiple edges between the same pair of vertices are called parallel edges; a simple graph has no loops and no parallel edges.
边可以是环（连接一个顶点到自身），但在 GCSE 题目中环极少出现。如果边有方向，则称为有向边，但 WJEC 的图论问题几乎只涉及无向图。同一对顶点之间的多条边称为平行边；简单图既没有环也没有平行边。
The weight of an edge is a number assigned to it, representing distance, cost, or time. Weighted graphs are essential for most algorithms you will use.
边的权重是赋予它的一个数字，代表距离、成本或时间。加权图在你将使用的大多数算法中都必不可少。
2. Degree of a Vertex | 顶点的度数
The degree of a vertex, denoted deg(v), is the number of edges that meet at that vertex. A loop contributes 2 to the degree. The sum of the degrees of all vertices in a graph is twice the number of edges (Handshaking Lemma). This is often tested indirectly: if you are asked to find a missing number of edges or to verify a graph can be Eulerian.
顶点的度数，记作 deg(v)，是指在该顶点处相遇的边的数目。一个环为度数贡献 2。图中所有顶点的度数之和是边数的两倍（握手引理）。这个原理经常被间接考查：要求你找出缺失的边数，或验证一个图是否为欧拉图。
A vertex is odd if its degree is an odd number, and even if its degree is an even number. The Handshaking Lemma implies that the number of odd-degree vertices in any graph must be even. This fact is crucial when determining if a Eulerian trail exists.
如果一个顶点的度数是奇数，它就是奇顶点；如果是偶数，就是偶顶点。握手引理意味着任何图中奇度顶点的个数必定是偶数。这一事实在判断是否存在欧拉路径时至关重要。
3. Types of Graphs | 图的类型
A simple graph has no loops or multiple edges. A complete graph Kn is a simple graph with n vertices where every pair of vertices is connected by exactly one edge. For example, K4 has 4 vertices and 6 edges. The number of edges in Kn is n(n – 1)/2.
简单图没有环或多重边。完全图 Kn 是有 n 个顶点的简单图，其中每对顶点之间恰好有一条边相连。例如 K4 有 4 个顶点和 6 条边。Kn 中的边数为 n(n – 1)/2。
A connected graph means there is a path between every pair of vertices. A tree is a connected graph with no cycles. Trees have exactly (n – 1) edges if there are n vertices. A spanning tree of a connected graph is a subgraph that includes all vertices and is a tree. Minimum spanning tree (MST) problems ask for the tree with the smallest total weight.
连通图意味着每对顶点之间都存在一条路径。树是不含回路的连通图。如果树有 n 个顶点，则恰好有 (n – 1) 条边。一个连通图的生成树是包含所有顶点且构成树的子图。最小生成树（MST）问题要求找出总权重最小的树。
A bipartite graph is a graph whose vertices can be divided into two sets so that every edge connects a vertex from one set to the other. While not always named explicitly, colouring problems often use bipartite ideas. Planar graphs can be drawn with no edges crossing. You may be asked to count faces or apply Euler’s formula: V – E + F = 2 for a connected planar graph.
二分图是其顶点可以分成两个集合，使得每条边都连接一个集合中的顶点与另一个集合中的顶点的图。尽管未必明确提及名称，但着色问题往往会用到二分图的思想。平面图是能够画在平面上而没有边交叉的图。你可能需要计算面数，或应用欧拉公式：对于连通的平面图有 V – E + F = 2。
4. Adjacency Matrices | 邻接矩阵
An adjacency matrix represents a graph using a square table. For a graph with n vertices labelled 1 to n (or A, B, C…), create an n x n matrix. The entry in row i, column j is the number of edges between vertex i and vertex j. For a simple graph, entries are 0 or 1. For a weighted graph, you often record the weight instead of 1, using 0 for no edge and infinity for non-adjacent vertices (∞).
邻接矩阵用一个方形表格来表示图。对于有 n 个顶点、标记为 1 到 n（或 A, B, C…）的图，建立一个 n × n 矩阵。第 i 行第 j 列的元素是顶点 i 与顶点 j 之间的边数。对于简单图，元素为 0 或 1。对于加权图，通常记录权重而不是 1，无边的位置用 0 表示，但在最短路径算法中会用 ∞ 表示不邻接的顶点。
Example: a simple graph with vertices A, B, C and edges AB, AC, BC (i.e. K3) has the adjacency matrix below.
示例：一个有顶点 A、B、C 和边 AB、AC、BC 的简单图（即 K3），其邻接矩阵如下。
| A | B | C | |
| A | 0 | 1 | 1 |
| B | 1 | 0 | 1 |
| C | 1 | 1 | 0 |
Note: the matrix is symmetric for undirected graphs. Loop entries appear on the main diagonal. You may be asked to draw a graph from a given adjacency matrix or to construct a matrix from a diagram. Watch for directed graphs where the matrix is not symmetric.
注意：无向图的邻接矩阵是对称的。环的项出现在主对角线上。你可能需要根据给定的邻接矩阵画出图，或者根据图构建矩阵。当心在有向图中矩阵不对称的情况。
5. Eulerian Trails and Circuits (Route Inspection Problem) | 欧拉路径与回路（路线检验问题）
An Eulerian trail (or path) is a route that traverses every edge of a graph exactly once. An Eulerian circuit (or cycle) is an Eulerian trail that starts and ends at the same vertex. The route inspection problem asks you to find the shortest route that covers every edge at least once, which may require repeating some edges.
欧拉路径（或迹）是一条恰好经过图中每条边一次的路线。欧拉回路（或圈）是起点与终点重合的欧拉路径。路线检验问题要求找出至少经过每条边一次的最短路线，这可能需要重复一些边。
Theorems: A connected graph has an Eulerian circuit if and only if every vertex has even degree. A connected graph has an Eulerian trail but not a circuit if and only if it has exactly two vertices of odd degree (the trail starts at one odd vertex and ends at the other).
定理：一个连通图存在欧拉回路当且仅当每个顶点的度数均为偶数。一个连通图存在欧拉路径但没有欧拉回路，当且仅当它恰好有两个奇度顶点（路径起始于一个奇顶点，终止于另一个奇顶点）。
To solve a route inspection problem on a graph that is not Eulerian, you need to pair up odd-degree vertices in the most efficient way and add duplicate edges along the shortest paths between them. The total length of the route is the sum of all original edge weights plus the lengths of the duplicated edges. You must show the pairing explicitly and calculate the extra distance.
要解决非欧拉图的路线检验问题，你需要以最有效的方式将奇度顶点两两配对，并在它们之间的最短路径上添加重复边。路线的总长度等于原图所有边权重之和加上重复边的长度。你必须明确显示配对并计算额外的距离。
Exam tip: Always start by listing all odd-degree vertices. If there are more than two, consider all possible pairings, add the shortest path distances for each pairing, and choose the combination that gives the smallest total added distance.
考试技巧：务必从列出所有奇度顶点入手。如果有超过两个，考虑所有可能的配对组合，为每种配对加上最短路径距离，选择附加总距离最小的组合。
6. Hamiltonian Cycles (Travelling Salesman Problem) | 哈密顿回路（旅行商问题）
A Hamiltonian cycle is a route that visits every vertex exactly once and returns to the start. The travelling salesman problem (TSP) asks for the Hamiltonian cycle of minimum total weight in a weighted complete graph. Unlike Eulerian problems, there is no simple necessary and sufficient condition for a graph to have a Hamiltonian cycle, so examining all possibilities is often required.
哈密顿回路是一条恰好访问每个顶点一次并返回起点的路线。旅行商问题（TSP）要求在加权完全图中找出总权重最小的哈密顿回路。与欧拉问题不同，一个图是否存在哈密顿回路没有简单的充要条件，因此通常需要检查所有可能的情况。
For the lower bound of a TSP, you can use a minimum spanning tree and the two shortest edges from one vertex, but at GCSE WJEC the focus is usually on finding the exact optimal tour by inspection for small graphs, or using the nearest neighbour algorithm to find an upper bound.
对于 TSP 的下界，你可以利用最小生成树和从一个顶点出发的两条最短边，但在 WJEC GCSE 中，重点通常是对小型图通过穷举来找到精确最优环游，或使用最近邻算法求上界。
Nearest neighbour algorithm: Start at a given vertex, repeatedly move to the nearest unvisited vertex, and finally return to the start. The result is an upper bound for the optimal tour, but not necessarily optimal. You may be asked to improve it by swapping edges.
最近邻算法：从给定顶点开始，反复移动到最近未访问的顶点，最后返回起点。所得结果是最优环游的一个上界，但不一定是最优的。你可能需要交换边来改进它。
When listing Hamiltonian cycles, remember that the reverse order is the same cycle. For n vertices, there are (n-1)!/2 distinct Hamiltonian cycles. In an exam with 4 or 5 vertices, simply list them and compute each total weight.
在列举哈密顿回路时，记住逆序是同一个回路。对于 n 个顶点，共有 (n-1)!/2 个不同的哈密顿回路。在考试中若出现 4 或 5 个顶点，直接列出并计算每个的总权重即可。
7. Minimum Spanning Trees – Kruskal’s Algorithm | 最小生成树 – 克鲁斯卡尔算法
A minimum spanning tree (MST) connects all vertices of a graph with the smallest possible total edge weight, without creating cycles. Kruskal’s algorithm builds the MST by considering edges in increasing order of weight and adding an edge if it does not form a cycle.
最小生成树（MST）用尽可能小的总边权重连接图中的所有顶点，且不形成回路。克鲁斯卡尔算法按权重递增顺序考虑边，如果添加该边不会形成回路则将其加入。
Steps: (1) List all edges with their weights. (2) Sort edges from smallest weight to largest. (3) Go through the sorted list, including an edge in the tree if it connects two different components (i.e. does not complete a cycle). (4) Stop when (n-1) edges have been selected.
步骤：(1) 列出所有边及其权重。(2) 将边按权重从小到大的顺序排列。(3) 依次检查排序列表，如果某条边连接两个不同的分支（即不构成回路），则将其加入树中。(4) 当选中 (n-1) 条边时停止。
It is essential to draw the tree as you add edges. In the exam you must list the edges in the order they were selected and give the total weight. Kruskal’s algorithm is particularly efficient when edge list is easy to sort.
务必在添加边时绘制树形图。在考试中你必须按选择顺序列出边，并给出总权重。当边列表容易排序时，克鲁斯卡尔算法尤其高效。
Common mistake: forgetting to check for cycles. Use a simple method: shade vertices already connected, or write the components. An edge creates a cycle if both end vertices already belong to the same component.
常见错误：忘记检查是否形成回路。可以使用简单方法：给已连接的顶点涂色，或记录分支。如果一条边的两个端点已经属于同一分支，那么加入该边会形成回路。
8. Minimum Spanning Trees – Prim’s Algorithm | 最小生成树 – 普里姆算法
Prim’s algorithm builds the MST by starting from an arbitrary vertex and repeatedly adding the cheapest edge that connects the current tree to a vertex not yet in the tree. The process continues until all vertices are included.
普里姆算法通过从一个任意顶点开始，并反复添加将当前树与尚未在树中的某个顶点连接起来的最短边，来构建最小生成树。持续此过程直到所有顶点都被加入。
Implementation: (1) Choose a start vertex. (2) Mark the start vertex as ‘in the tree’. (3) From all edges that have exactly one end in the tree, pick the one with the smallest weight and add it (and the new vertex) to the tree. (4) Repeat step 3 until all vertices are in the tree.
实现：(1) 选择一个起始顶点。(2) 将该起始顶点标记为“在树中”。(3) 在所有恰好有一个端点在树中的边里，选择权重最小的边，并将该边（以及新顶点）加入树中。(4) 重复步骤 3 直到所有顶点都在树中。
Prim’s algorithm is often requested when the graph is drawn as a network diagram. You must clearly show the order of edge selection, perhaps by numbering them on the diagram. If the question asks for a matrix-based Prim’s approach, you may use a table.
当图以网络图形式呈现时，通常要求使用普里姆算法。你必须清楚地显示边选择的顺序，可以在图上编号。如果问题要求基于矩阵的普里姆算法，你可以使用表格。
Both Kruskal and Prim produce the same total weight for connected graphs, though the edge order may differ. Prim’s is easier to apply to a diagram when you can see the weights visually.
对于连通图，克鲁斯卡尔算法和普里姆算法会得到相同的总权重，尽管边的顺序可能不同。当你可以直观看到权重时，普里姆算法更容易应用于图表。
9. Shortest Path – Dijkstra’s Algorithm | 最短路径 – 迪杰斯特拉算法
Dijkstra’s algorithm finds the shortest distance from a start vertex to all other vertices in a weighted graph with non-negative weights. At GCSE level, you will usually apply it on a small network by completing a labelling table or boxes at vertices.
迪杰斯特拉算法可以在具有非负权重的加权图中，找出从起始顶点到所有其他顶点的最短距离。在 GCSE 级别，你通常会通过填写顶点旁的标签表格或方框，在一个小网络上应用它。
Procedure: (1) Label the start vertex with 0 and all others with ∞ (infinity). (2) From the current vertex, update the distances of unvisited neighbours by adding the edge weight to the distance of the current vertex. If the new calculated distance is smaller, replace it. (3) Mark the current vertex as visited and choose the unvisited vertex with the smallest temporary distance as the new current vertex. (4) Repeat until the destination is reached or all vertices are visited.
步骤：(1) 将起始顶点标记为 0，其余所有顶点标记为 ∞（无穷大）。(2) 从当前顶点出发，通过把边权重与当前顶点的距离相加，更新未访问邻居的距离。如果新算出的距离更小，则替换之。(3) 将当前顶点标记为已访问，并选择临时距离最小的未访问顶点作为新的当前顶点。(4) 重复直至到达目标顶点或所有顶点均已访问。
You must show working by writing intermediate values at each vertex, often in a box. The final shortest path tree or route should be stated. Remember that Dijkstra’s algorithm does not work if any edge weight is negative, although this situation does not appear at GCSE.
你必须通过在每个顶点旁写出中间值来展示步骤，通常写在一个方框内。最终的最短路径树或路线需要明确写出。记住，如果有任何边权重为负，迪杰斯特拉算法将失效，不过这种情况在 GCSE 中不会出现。
Common pitfalls: forgetting to update all neighbours, continuing with the wrong ‘current’ vertex, or misreading edge weights. Redraw the network if necessary to keep your working tidy.
常见陷阱：忘记更新所有邻居，选错了“当前”顶点，或看错边权重。如有必要，重画网络以保持答题过程整洁。
10. Planar Graphs and Graph Colouring | 平面图与图着色
Some WJEC questions involve colouring the vertices or regions of a planar graph. A planar graph can be drawn so that no two edges cross except at vertices. The regions are like the faces of a map. Euler’s formula V – E + F = 2 connects the number of vertices V, edges E, and faces F for a connected planar graph.
一些 WJEC 问题涉及对平面图的顶点或面进行着色。平面图可以画成除了在顶点处以外没有边相交的图。面就像是地图上的区域。欧拉公式 V – E + F = 2 将一个连通平面图的顶点数 V、边数 E 和面数 F 联系起来。
Graph colouring assigns colours to vertices so that adjacent vertices have different colours. The minimum number of colours needed is the chromatic number. The four colour theorem states that any planar graph can be coloured with at most four colours, but in exam problems you are more likely to colour a simple graph with 2 or 3 colours.
图着色是为顶点分配颜色，使得相邻顶点颜色不同。所需的最少颜色数称为色数。四色定理指出任何平面图最多用四种颜色即可着色，但在考试问题中，你更可能需要对一个简单图用 2 或 3 种颜色进行着色。
To colour a map (the dual graph), treat regions as vertices and boundaries as edges. A practical method is to start with the vertex of highest degree and work systematically. Show your colouring clearly on the diagram.
要为地图（对偶图）着色，可将区域视为顶点，边界视为边。一种实用的方法是先从度数最高的顶点开始，然后系统地进行。在图上清晰地展示你的着色。
You may be asked to prove that a graph is not planar using Kuratowski’s theorem (involving K5 or K3,3), but this is rare. Focus on recognising when a given graph can be redrawn without crossings.
你可能需要利用库拉托夫斯基定理（涉及 K5 或 K3,3）证明某个图不是平面图，但这种情况很少见。重点关注如何识别给定的图能否重画而不出现边交叉。
11. Common Exam Mistakes | 常见考试误区
Miscounting vertex degrees: especially when a vertex has a loop, remember a loop adds 2 to the degree. Double-check the sum of degrees to see if it equals twice the number of edges.
错算顶点度数：特别是当顶点有环时，记住一个环为度数贡献 2。检查度数总和是否等于边数的两倍。
Misidentifying odd vertices: for route inspection, always write down the degrees next to each vertex, then highlight the odd ones before pairing. If you miss an odd vertex, your added edges will be wrong.
误判奇度顶点：在路线检验中，务必在每个顶点旁写下度数，然后在配对前高亮所有奇度顶点。如果漏掉一个奇度顶点，你添加的边就会出错。
Adjacency matrix errors: filling in the matrix mirror positions incorrectly or forgetting that a simple graph has 0 on the diagonal unless loops are present. For directed graphs, rows represent ‘from’ and columns ‘to’.
邻接矩阵错误：错误填写矩阵的对称位置，或者忘记除非有环的情况外简单图的对角线应为 0。对于有向图，行代表“从”，列代表“到”。
Algorithm lapses: in Kruskal’s, not checking for cycles; in Prim’s, choosing an edge with both ends already in the tree; in Dijkstra’s, using a visited vertex again. Practise step-by-step with clear labelling to avoid these traps.
算法失误：在克鲁斯卡尔算法中，未检查回路；在普里姆算法中，选择了两个端点都已经在树里的边；在迪杰斯特拉算法中，再次使用了已访问顶点。通过清晰的标注进行逐步练习以避免这些陷阱。
Confusing Eulerian and Hamiltonian concepts: Eulerian = all edges once, Hamiltonian = all vertices once. Never mix the conditions up.
混淆欧拉和哈密顿概念：欧拉 = 每条边一次，哈密顿 = 每个顶点一次。千万不要把条件搞混。
12. Summary and Tips | 总结与应试技巧
Graph theory questions are highly structured. Always read the question carefully to identify which algorithm to use. Show all your working – the steps are often worth more marks than the final answer. Draw the graph clearly on your answer paper and label vertices as you go.
图论题目结构非常清晰。一定要仔细审题，确定使用哪个算法。展示所有解题过程——步骤往往比最终答案值更多分。在答题纸上清晰地画出图形，并随进程标注顶点。
For route inspection, look for the words ‘start and finish at the same point’ (Eulerian circuit) or ‘start and finish at different points’ (Eulerian trail). For TSP, the phrase ‘visit every vertex exactly once’ indicates a Hamiltonian cycle. For MST, the instruction is usually ‘find a minimum spanning tree’ and you must specify which algorithm.
对于路线检验，注意“起点和终点相同”（欧拉回路）或“起点和终点不同”（欧拉路径）这些字眼。对于 TSP，短语“恰好访问每个顶点一次”表明是哈密顿回路。对于最小生成树，指令通常是“找出最小生成树”，并必须明确使用哪种算法。
Keep a calculator handy for adding edge weights accurately. Write the total weight with the correct units if given. Finally, manage your time: a graph theory question can be lengthy, so practise past papers to become efficient at drawing and colouring.
手边准备一个计算器以便准确加总边权重。如果题目给出了单位，总权重需附上正确的单位。最后，管理好时间：图论题可能篇幅较长，所以多练往年真题，以提高绘图和着色的效率。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导