📚 IGCSE WJEC Maths: Graph Theory Essentials | IGCSE WJEC 数学：图论 考点精讲
Graph theory is a fascinating branch of mathematics that studies networks of points connected by lines. In the IGCSE WJEC specification, you will learn how to represent real-world problems – such as delivery routes, communication networks, or even social connections – using graphs, and then apply algorithms to find optimal solutions. This article covers all the essential concepts: from basic terminology to Eulerian trails, Hamiltonian cycles, trees, minimum spanning trees, and the Travelling Salesperson Problem. Mastering these ideas will not only help you tackle exam questions with confidence but also sharpen your logical thinking and problem-solving skills.
图论是数学中一个迷人的分支，研究由点和线构成的网络。在IGCSE WJEC考纲中，你将学习如何用图来表示现实世界中的问题——比如配送路线、通信网络，甚至社交关系——然后运用算法找出最优解。本文涵盖了所有核心概念：从基本术语到欧拉迹、哈密顿回路、树、最小生成树以及旅行商问题。熟练掌握这些知识不仅能让你自信地应对考试题目，还能提升你的逻辑思维和问题解决能力。
1. Basic Graph Terminology | 图的基本术语
A graph consists of vertices (or nodes) connected by edges (or arcs). An edge can be undirected, meaning there is no specific direction (e.g., a road that can be travelled both ways), or directed, often called a digraph, where each edge has a direction (like a one-way street). A loop is an edge that starts and ends at the same vertex, and a simple graph has no loops and at most one edge between any pair of vertices. In WJEC questions, you will mostly work with simple, undirected, and weighted graphs, where edges carry numerical values representing distances, costs, or times.
一个图由顶点（或称节点）以及连接它们的边（或称弧）组成。边可以是无向的，意味着没有特定方向（比如双向可通行的道路），也可以是有向的，此时常称为有向图，每条边都有方向（如同单行道）。环是指起点和终点为同一顶点的边；简单图既没有环，并且任意两个顶点之间最多只有一条边。在WJEC的考题中，你接触的大多是简单、无向、带权图，边上的数值代表距离、成本或时间。
A graph is often denoted as G = (V, E), where V is the set of vertices and E is the set of edges. You need to be comfortable reading adjacency matrices, which are square grids showing the connections between vertices, and also interpreting weighted networks drawn as diagrams. Pay attention to whether a graph is connected – a graph is connected if there is a path between every pair of vertices; otherwise it is disconnected and may consist of several components.
图通常记作G = (V, E)，其中V是顶点集，E是边集。你需要熟练阅读邻接矩阵——一种显示顶点之间连接关系的正方形网格，同时也要会解读画成示意图的带权网络。注意图是否连通：如果任意两个顶点之间都存在一条路径，那么该图就是连通的；否则就是不连通的，可能由几个连通分量组成。
2. Degree of a Vertex and the Handshaking Lemma | 顶点的度与握手引理
The degree (or valency) of a vertex is the number of edges incident to it. A loop contributes 2 to the degree. For example, in a simple graph, a vertex directly connected to three other vertices has degree 3. The handshaking lemma states that the sum of the degrees of all vertices in any graph is twice the number of edges. Symbolically: Σ deg(v) = 2|E|. This result is very useful for checking the consistency of degree sequences and for proving that a graph cannot have an odd number of odd-degree vertices.
顶点的度（或称价）是指与该顶点相关联的边的条数。一条环对度的贡献为2。例如，在一个简单图中，如果一个顶点与另外三个顶点直接相连，那么它的度就是3。握手引理指出，任何图中所有顶点的度数之和等于边数的两倍。用符号表示：∑ deg(v) = 2|E|。这个结果非常有用，可以检查度序列是否一致，也能证明图中不可能有奇数个奇度顶点。
In exam scenarios, you might be given a degree sequence and asked to determine if a graph with that sequence can exist. Use the handshaking lemma: the sum must be even. Also, a vertex with degree 0 is called an isolated vertex. When dealing with problems about traversability (Eulerian graphs), the number of odd-degree vertices is the key indicator.
在考试中，你可能会遇到给定一个度序列，要求判断该序列是否能构成一个图。这时就用握手引理：度数之和必须为偶数。此外，度为0的顶点称为孤立点。在处理可遍历性（欧拉图）问题时，奇度顶点的个数是关键指标。
3. Paths, Cycles, and Connectivity | 路径、回路与连通性
A walk is a sequence of vertices where consecutive vertices are adjacent. A trail is a walk with no repeated edges. A path is a walk with no repeated vertices (and therefore no repeated edges). 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 differences is essential because algorithms for route inspection or the Travelling Salesperson Problem often require you to distinguish between trails, paths, and cycles.
迹是顶点的一个序列，其中相继的两个顶点都相邻。迹是无重复边的行走。路径是无重复顶点的行走（因而也无重复边）。回路（或圈）是一条闭合路径，起点和终点重合，且沿途无其他重复顶点。理解这些区别至关重要，因为邮差问题或旅行商问题中的算法往往要求你区分迹、路径和回路。
Connectivity measures how robust a network is. A graph is connected if there is a path between every pair of vertices. A bridge (or cut-edge) is an edge whose removal disconnects the graph. Similarly, a cut-vertex is a vertex whose removal increases the number of components. In minimum spanning tree problems you will avoid cycles, because trees are connected graphs with no cycles.
连通性衡量网络的鲁棒性。如果任意两个顶点之间都存在路径，则图是连通的。桥（或称割边）是指删除后会使得图不再连通的边。类似地，割点是指删除后会增加连通分量个数的顶点。在最小生成树问题中，你会避开回路，因为树是无回路的连通图。
4. Eulerian Graphs and Route Inspection | 欧拉图与邮差问题
An Eulerian trail (or Eulerian path) is a trail that uses 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. For an undirected graph, an Eulerian circuit exists if and only if the graph is connected and every vertex has even degree. An Eulerian trail (but not a circuit) exists if and only if the graph is connected and exactly two vertices have odd degree – in which case the trail must start at one odd vertex and end at the other.
欧拉迹（或称欧拉路径）是指恰好经过图中每条边一次的迹。欧拉回路（或称欧拉圈）是指起点和终点重合的欧拉迹。对于一个无向图，存在欧拉回路的充分必要条件是图连通且所有顶点的度均为偶数。存在欧拉迹（但不存在回路）的充分必要条件是图连通且恰好有两个顶点的度为奇数——此时该迹必须以其中一个奇度顶点为起点，另一个奇度顶点为终点。
The Route Inspection Problem (also called the Chinese Postman Problem) asks for the shortest closed walk that traverses every edge at least once. If the graph is Eulerian, the optimal route is simply an Eulerian circuit and the length equals the total weight of all edges. If there are odd-degree vertices, you must pair them up by adding extra edges (repeating existing edges) along the shortest possible paths between these vertices, so that all vertices become even. The total length is then the sum of all original edge weights plus the lengths of the added shortest paths. WJEC questions usually provide small networks where you can find the optimal pairing by inspection and simple addition.
邮差问题（中国邮递员问题）要求找出一条遍历每条边至少一次的最短闭合行走路线。如果图是欧拉图，最优路线直接就是一条欧拉回路，其长度等于所有边的总权重。如果存在奇度顶点，则必须将这些奇度顶点两两配对，在它们之间沿着最短路径添加额外的边（即重复走已有的边），使得所有顶点都变成偶度。此时总长度为所有原始边权重之和再加上这些添加的最短路径长度。WJEC的考题通常会给出小型网络，让你通过观察和简单加法找出最优配对。
5. Hamiltonian Graphs | 哈密顿图
A Hamiltonian path visits every vertex of a graph exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that returns to the starting vertex, again visiting all vertices exactly once (except the start/end vertex). Unlike Eulerian graphs, there is no simple necessary and sufficient condition for a graph to be Hamiltonian; you must check by inspection or by constructing the cycle. In WJEC problems, you will often be asked to find a Hamiltonian cycle of minimum total weight – this is the Travelling Salesperson Problem (TSP).
哈密顿路径恰好经过图中每个顶点一次。哈密顿回路（或称哈密顿圈）是一条回到起点的哈密顿路径，同样恰好经过所有顶点一次（起点/终点除外）。与欧拉图不同，判断一个图是否为哈密顿图没有简单的充分必要条件；你必须通过观察或构造回路来检查。在WJEC的题目中，常常要求你找出总权重最小的哈密顿回路——这就是旅行商问题（TSP）。
Some graphs may have many Hamiltonian cycles. You need to be able to list all possible Hamiltonian cycles for small complete graphs, particularly when applying the brute-force method. A complete graph with n vertices, denoted Kₙ, has (n-1)! / 2 distinct Hamiltonian cycles (if undirected and you consider cycles the same regardless of starting point and direction). For n=5, there are 12 cycles. Knowing this helps you verify that you have listed all possibilities in an exam question.
有些图可能存在多个哈密顿回路。你需要能够列出小型完全图的所有可能哈密顿回路，尤其是在使用穷举法时。一个有n个顶点的完全图，记作Kₙ，共有(n-1)! / 2个不同的哈密顿回路（对于无向图，不考虑起点和方向带来的重复）。当n=5时，共有12个回路。了解这一点有助于你在考试题目中验证是否已经列出所有可能性。
6. Trees and Spanning Trees | 树与生成树
A tree is a connected, undirected graph with no cycles. Key properties of a tree with n vertices: it has exactly n-1 edges, it is minimally connected (removing any edge disconnects it), and there is a unique simple path between any two vertices. A spanning tree of a connected graph G is a subgraph that includes all the vertices of G and is a tree. In other words, a spanning tree keeps the network connected using the minimum possible number of edges (n-1 edges).
树是一种无回路的连通无向图。含有n个顶点的树具有以下关键性质：它恰好有n-1条边，它是极小连通的（删除任意一条边都会使其不连通），并且任意两个顶点之间有唯一的一条简单路径。连通图G的生成树是指包含G的所有顶点并且构成一棵树的子图。换言之，生成树使用最少数量的边（n-1条边）来保持网络连通。
In a weighted graph, different spanning trees can have different total weights. The Minimum Spanning Tree (MST) is the spanning tree with the smallest possible total edge weight. MSTs are crucial for solving problems like designing a minimum-cost network (e.g., connecting towns with fibre optic cable). You will need to apply Kruskal’s or Prim’s algorithm to find the MST efficiently.
在带权图中，不同的生成树可能具有不同的总权重。最小生成树（MST）就是总边权尽可能小的那棵生成树。MST在求解诸如设计最小成本网络（例如用光缆连接城镇）等问题时至关重要。你需要熟练运用克鲁斯卡尔算法或普里姆算法来高效地找出MST。
7. Kruskal’s Algorithm | 克鲁斯卡尔算法
Kruskal’s algorithm builds the minimum spanning tree by considering edges in order of increasing weight, adding an edge if it does not create a cycle. The steps: (1) List all edges in ascending order of weight. (2) Start with an empty graph on the given vertices (or just a list of chosen edges). (3) Go through the sorted list, and for each edge, check if its endpoints are already connected via the edges already chosen. If not, include this edge. (4) Stop when n-1 edges have been selected. A convenient way to check for cycles is to shade or colour the vertices as they become connected.
克鲁斯卡尔算法通过按权重递增的顺序考察边来构建最小生成树，如果一条边不会构成回路就将它加入。步骤如下：(1) 将所有边按权重升序排列。(2) 从一张只含给定顶点的空图开始（或仅列出已选择的边）。(3) 依次处理排序后的列表，对每条边检查其两个端点是否已经通过先前选出的边连通。若未连通，则增添这条边。(4) 当已选出n-1条边时终止。一种方便的查环方法是，随着顶点被连接起来，对它们进行阴影标记或涂色。
Kruskal’s algorithm is particularly easy to apply when the graph is given as a list of edges, which is common in WJEC exam papers. You must show your working clearly – list the edges in order and explain why you accept or reject each one. If two edges have the same weight, you can choose either, and the total weight of the MST will be the same regardless, though the tree shape might differ. Always state the total minimum weight at the end.
当题目以边列表形式给出图时，克鲁斯卡尔算法特别容易使用，这在WJEC试卷中很常见。你必须清晰地展示演算过程——将边按顺序列出，并解释接受或拒绝每条边的原因。如果有两条边的权重相同，你可以任选一条，无论如何MST的总权重都相同，尽管树的形状可能不同。最后务必写出最小总权重。
8. Prim’s Algorithm | 普里姆算法
Prim’s algorithm builds the MST from a starting vertex by greedily adding the cheapest edge that connects the current tree to a vertex not yet in the tree. Steps: (1) Choose any starting vertex and add it to the tree. (2) From all edges that connect a vertex in the tree to a vertex outside the tree, select the edge with the smallest weight. Add that edge and the new vertex to the tree. (3) Repeat step 2 until all vertices are included. To avoid confusion, you can maintain a table showing, at each iteration, the nearest distance from the tree to each unconnected vertex.
普里姆算法从一个起始顶点开始，贪心地添加一条边，该边连接当前树与尚未在树中的顶点，且权重最小。步骤如下：(1) 任选一个起始顶点加入树中。(2) 从所有连接树内顶点与树外顶点的边中，选出权重最小的一条。将这条边以及对应的新顶点加入树中。(3) 重复第2步，直到所有顶点都被包含。为避免混乱，你可以维护一张表格，显示在每一轮迭代中，生成树到每个未连接顶点的最近距离。
Prim’s algorithm is often applied from a matrix (adjacency matrix or distance table) and is particularly efficient for dense graphs. In WJEC questions, you might be asked to use Prim starting from a specific vertex and record the order in which vertices are added. Both Kruskal’s and Prim’s algorithms always give an MST, but the sequence of edge selection may differ. You should be familiar with both methods and use the one best suited to the data format in the question.
普里姆算法通常借助矩阵（邻接矩阵或距离表）来使用，对于稠密图尤为高效。在WJEC考题中，你可能会被要求从指定顶点开始运用普里姆算法，并记录顶点被加入的顺序。克鲁斯卡尔算法和普里姆算法都能确保得到MST，但边选择的顺序可能不同。你应当熟练掌握两种方法，并根据题目给出的数据格式选用最合适的一种。
9. Travelling Salesperson Problem | 旅行商问题
The Travelling Salesperson Problem (TSP) aims to find a Hamiltonian cycle of minimum total weight in a complete weighted graph. For small graphs (typically up to 6 vertices in WJEC exams), you can find the exact solution by listing all distinct Hamiltonian cycles and calculating their lengths. This brute-force method is straightforward: list cycles systematically, for example by fixing one vertex as the start to reduce duplication, and then compute each total.
旅行商问题（TSP）的目标是在一个带权完全图中找出总权重最小的哈密顿回路。对于小型图（在WJEC考试中通常不超过6个顶点），你可以通过列出所有不同的哈密顿回路并计算其长度来求出精确解。这种穷举法很直接：系统地列出回路，比如固定一个顶点作为起点以减少重复，然后计算每个回路的总权重。
For larger networks, finding the exact TSP solution becomes impractical, so WJEC also tests heuristic and bound methods. An upper bound for the TSP can be found using the Nearest Neighbour algorithm: start at a vertex, repeatedly go to the nearest unvisited vertex, and finally return to the start. The total length gives an upper bound, but it may not be optimal. A lower bound is often found by removing a vertex and finding the MST of the remaining graph, then adding the two shortest edges from the removed vertex to the MST. The best lower bound (highest value) from repeating this for different vertices is called the best lower bound. These bounds allow you to write an inequality: lower bound ≤ optimal tour length ≤ upper bound. This is a key skill for WJEC evaluation questions.
对于较大的网络，寻找TSP的精确解变得不现实，因此WJEC也会考察启发式方法和界值法。TSP的一个上界可以通过最近邻算法求得：从一个顶点出发，反复前往最近且未访问过的顶点，最后返回起点。总长度给出一个上界，但不一定是最优的。下界通常通过删除一个顶点，求出剩余图的最小生成树，再加上从被删顶点到该MST的两条最短边来得到。换用不同顶点重复上述过程，取其中最大的下界即为最佳下界。这些界值让你能够写出不等式：下界 ≤ 最优回路长度 ≤ 上界。这是WJEC评估题中的一项关键技能。
10. Exam Tips and Common Pitfalls | 考试技巧与常见错误
When tackling graph theory questions in the IGCSE WJEC exam, careful reading and systematic working are your best tools. Always check if the graph is directed or undirected, weighted or unweighted. For route inspection, first count odd-degree vertices – this immediately tells you whether an Eulerian circuit exists or whether you need to add extra edges. For MST algorithms, show your selection process step by step; simply writing the final tree without working may lose marks. When listing Hamiltonian cycles, use an organised method (e.g., lexicographic order of vertices) to avoid duplicates and omissions.
在应对IGCSE WJEC考试中的图论题目时，仔细审题和有条理的演算是你最好的工具。务必确认图是有向还是无向、带权还是不带权。在处理邮差问题时，首先数出奇度顶点的个数——这能立刻告诉你是否存在欧拉回路，或者是否需要添加额外的边。对于最小生成树算法，要一步步展示你的选择过程；只写出最终的生成树而没有过程可能会失分。在列举哈密顿回路时，采用有条理的方法（例如按顶点的字典序排列）以避免重复和遗漏。
Common mistakes include: forgetting that a loop adds 2 to a vertex’s degree; mixing up Eulerian and Hamiltonian concepts; misapplying Kruskal’s algorithm by adding an edge that creates a cycle; forgetting to add the return journey when calculating the length of a tour in TSP; and confusing upper and lower bounds. Practice with past papers is the best way to avoid these pitfalls. Remember to write your final answer clearly and, for TSP bounds, state the inequality explicitly, e.g., 52 ≤ optimal ≤ 58.
常见的错误包括：忘记一个环会为顶点度数增加2；混淆欧拉图与哈密顿图的概念；在运用克鲁斯卡尔算法时误加了会导致回路的边；在计算TSP回路长度时忘记加上返回起点的行程；以及混淆上界与下界。通过练习历年真题是避免这些失误的最佳途径。记得清晰地写出最终答案，对于TSP的界值，要明确写出不等式，例如 52 ≤ 最优解 ≤ 58。
Finally, always manage your time well – graph theory questions often appear as multipart problems. If a question asks for both an upper bound and a lower bound, allocate enough time for each part. Check your arithmetic when adding weights, and double-check that your spanning tree has exactly n-1 edges. With solid preparation, graph theory can become one of the most rewarding topics on the WJEC paper.
最后，务必合理分配时间——图论题目常常以多问形式出现。如果一道题要求同时求出上界和下界，就要为每个部分留足时间。在累加权重时仔细核对计算，并再次检查你的生成树是否恰好包含n-1条边。只要准备充分，图论完全可以成为WJEC试卷中最有把握得分的话题之一。
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