📚 Graph Theory Essentials for IGCSE AQA Maths | 图论考点精讲
Graph theory is a vital part of the IGCSE AQA Mathematics syllabus, equipping you with powerful tools for modelling real-world situations. In these topics, you will learn how to represent networks of roads, pipelines, computer connections, and scheduling problems using vertices and edges. By mastering fundamental concepts such as trees, minimum spanning trees, and shortest-path algorithms, you develop systematic problem-solving skills that are assessed through both structured questions and more open-ended tasks. This article walks you through every key idea you need, with clear step-by-step explanations, worked examples, and tips for the exam.
图论是IGCSE AQA数学大纲中的重要组成部分,为你提供描述现实情境的强大工具。在这些课题中,你将学会用顶点和边来表示道路网络、管道系统、计算机连接以及调度问题。通过扎实掌握树、最小生成树和最短路径算法等基本概念,你能够培养系统化的解题能力,这些能力在考试中会通过结构化问题以及更开放的题目来考查。本文将带你逐一梳理每一个需要掌握的关键知识点,并配以清晰的步骤讲解、例题和应试技巧。
1. What is a Graph? Basic Definitions | 图论入门:基本定义
A graph in mathematics is a set of points, called vertices (or nodes), joined by lines, called edges (or arcs). Graphs are used to model connections: for instance, towns on a map linked by roads, or friends connected in a social network. A vertex is usually drawn as a dot or circle with a label, and an edge is a line connecting two vertices. Edges can be undirected (traffic can go both ways) or directed (one-way streets), but at IGCSE you primarily work with undirected, weighted edges where each edge has a number representing distance, cost, or time.
在数学中,图是由一些被称为顶点(或节点)的点以及连接这些点的线(称为边或弧)组成的集合。图用来描述各种连接关系:例如,地图上由道路相连的城镇,或者社交网络中彼此联系的朋友。顶点通常画成带标签的点或圆圈,边则是连接两个顶点的线段。边可以是无向的(双向通行)或有向的(单行道),但在IGCSE课程中你主要处理的是无向的加权边,每条边都带有一个数字,表示距离、成本或时间。
A graph is called simple if it has no loops (edges from a vertex to itself) and no multiple edges between the same pair of vertices. The degree of a vertex is the number of edges meeting at that vertex. In a simple graph with n vertices, the sum of all vertex degrees is exactly twice the number of edges. This fact (the Handshaking Lemma) often appears in exam questions to test your understanding of basic graph properties.
如果一个图没有环(从顶点连回自身的边),任意两个顶点之间也只有一条边,我们就称它为简单图。顶点的度数是指与该顶点相连的边的条数。在一个有 n 个顶点的简单图中,所有顶点的度数之和恰好等于边数的两倍。这个结论(握手引理)经常出现在考题中,用来考查你对图的基本性质的理解。
- Vertex / Node: a point in the graph. | 顶点/节点:图中的一个点。
- Edge / Arc: a line connecting two vertices. | 边/弧:连接两个顶点的线段。
- Weight: a number assigned to an edge (distance, cost). | 权重:分配给边的数字(距离、成本)。
- Degree: number of edges incident to a vertex. | 度数:与顶点相连的边的数目。
2. Paths, Trails and Cycles | 路径、迹与回路
A path is a sequence of vertices connected by edges, where no vertex is visited more than once. A trail allows revisiting vertices but not edges, while a cycle (or circuit) is a closed trail that starts and ends at the same vertex, with all other vertices distinct. Understanding these terms helps you describe routes in a network and is essential when you study Eulerian and Hamiltonian graphs later.
路径是由边连接起来的一串顶点,其中每个顶点最多只出现一次。迹允许重复经过顶点,但不能重复经过同一条边;而回路(或圈)则是一条闭合的迹,即起点和终点相同,且中间经过的其他顶点互不相同。透彻理解这些术语有助于你描述网络中的行径路线,对后续学习欧拉图和哈密顿图也非常关键。
In exam problems, you may be asked to find a path of a certain length or to list all paths between two given points. Always trace carefully with your finger or a pencil, listing vertices in order. When weights are given, the length of a path is the sum of the weights on its edges. Practice counting degrees along a path: internal vertices on a simple path contribute 2 to the path’s degree sum, while the end vertices contribute only 1.
在考试题目中,你可能会被要求找出给定长度的路径,或者列出两个指定点之间的所有路径。解题时可以用手指或铅笔仔细追踪,按顺序列出经过的顶点。当边带有权重时,路径的长度就是路径上各边的权重之和。你可以通过计算路径上的度数来加深理解:在一条简单路径中,内部的顶点对路径的度数总和贡献 2,而两端的顶点只贡献 1。
3. Connected Graphs and Trees | 连通图与树
A graph is connected if there is a path between every pair of vertices. If a graph is not connected, it splits into several components (separate subgraphs). Many algorithms you learn assume the graph is connected, so always check this condition first when applying Prim’s or Kruskal’s method.
如果一个图中任意两个顶点之间都存在一条路径,则称该图是连通的。如果图不连通,它就会分裂成若干个连通分量(独立的子图)。你所学的很多算法都假设图是连通的,因此在应用普里姆算法或克鲁斯卡尔算法之前,务必先确认这一条件。
A tree is a connected graph with no cycles. Trees have exactly (n – 1) edges, where n is the number of vertices. This property makes trees very efficient: they connect all vertices with the minimum possible number of edges. In network design, a tree ensures that every point is reachable without redundant links. A spanning tree of a connected graph is a subgraph that includes all the vertices and is a tree. A graph usually has many spanning trees, and finding the one with minimum total weight is the famous Minimum Spanning Tree (MST) problem.
树是一种无圈的连通图。一棵树恰好有 (n – 1) 条边,其中 n 是顶点数。这一性质使得树的结构非常高效:它用最少的边将所有顶点连接起来。在网络设计中,树可以保证每个节点都可达,同时没有冗余的链路。一个连通图的生成树指的是包含该图所有顶点且自身为一棵树的子图。一个图通常有许多棵生成树,而找出总权重最小的那一棵,就是著名的最小生成树(MST)问题。
Useful tree facts: In a tree, adding any extra edge creates exactly one cycle. Removing any edge from a tree disconnects it. These facts are frequently tested through multiple-choice or reasoning questions.
关于树的有用结论:在树中任意添加一条边,都会恰好产生一个圈;从树中任意删去一条边,都会使其不再连通。这些知识点经常通过选择题或说理题来考查。
4. Minimum Spanning Tree: Kruskal’s Algorithm | 最小生成树:克鲁斯卡尔算法
Kruskal’s algorithm finds a minimum spanning tree by building it edge by edge, starting with the smallest weight. You list all edges in increasing order of weight, then go through the list, selecting an edge if it does not form a cycle with previously chosen edges. This process continues until you have (n – 1) edges. This method looks at the whole graph at once and is particularly efficient when the graph has relatively few edges.
克鲁斯卡尔算法通过逐条添加边来建立最小生成树,并始终从权重最小的边开始。你将所有边按照权重从小到大排列成表,然后依次检查列表中的每一条边:如果这条边不会与已经选中的边构成圈,就选中它。重复这一过程,直到选中 (n – 1) 条边为止。这种方法从整体上考虑整个图,特别适用于边数相对较少的图。
Worked example: Consider a network with vertices A, B, C, D, E and edges with weights: AB=2, AC=3, AD=4, BC=3, BD=5, CD=1, CE=4, DE=3. List edges by weight: CD(1), AB(2), AC(3), BC(3), DE(3), AD(4), CE(4), BD(5). Start with CD. Then AB (no cycle). Then AC (no cycle). Next BC would form a cycle A–B–C–A, so skip it. Next DE (no cycle). We now have 4 edges and 5 vertices, so we stop. Total weight = 1+2+3+3 = 9.
例题: 考虑一个包含顶点 A、B、C、D、E 的网络,边及其权重为: AB=2, AC=3, AD=4, BC=3, BD=5, CD=1, CE=4, DE=3。按权重排序: CD(1), AB(2), AC(3), BC(3), DE(3), AD(4), CE(4), BD(5)。首先选 CD,再选 AB(不形成圈),再选 AC(不形成圈)。接下来 BC 会形成圈 A–B–C–A,跳过。选 DE(不形成圈)。目前已经有 4 条边和 5 个顶点,停止。总权重 = 1+2+3+3 = 9。
Total weight = 1 + 2 + 3 + 3 = 9
In the exam, you must show your sorted list and indicate which edges are added or rejected. It is wise to draw each step to help visualise cycles.
在考试中,你需要展示排序后的边列表,并标明哪些边被选中,哪些被拒绝。最好每一步都画出草图,以帮助判断是否形成圈。
5. Minimum Spanning Tree: Prim’s Algorithm | 最小生成树:普里姆算法
Prim’s algorithm grows the tree from a chosen starting vertex. At each step, you select the edge of smallest weight that connects a vertex already in the tree to one not yet in the tree. This is repeated until all vertices are included. Unlike Kruskal’s algorithm, Prim’s method works locally, expanding the tree outward, which can be easier when the network is dense or you have a specific starting point.
普里姆算法以任意选定的起始顶点为基础,逐步“生长”出生成树。每一步都选择权重最小的边,这条边要连接一个已在树中的顶点与一个尚未在树中的顶点。重复这一过程,直到所有顶点都被包含进来。与克鲁斯卡尔算法不同,普里姆算法是逐步向外扩张的局部方法,当网络比较密集或者有明确起点时,用起来更加顺手。
Worked example: Using the same weighted graph as above, start at D. Vertex D is in the tree initially. Its neighbours: C (weight 1), B (5), E (3). Smallest is CD=1, so add C. Now tree includes D and C. From {D,C}, connections to outside: from C: CA=3, CB=3, CE=4; from D: DB=5, DE=3. Smallest is CA=3 or CB=3 or DE=3 – any will do. Choose CA=3, add A. Tree now {D,C,A}. From these, connections: from A: AB=2, AD=4; from C: CB=3, CE=4; from D: DE=3, DB=5. Smallest is AB=2, add B. Tree now {D,C,A,B}. Finally choose DE=3 to include E. Total weight = 1+3+2+3 = 9, the same as Kruskal’s result.
例题: 使用上面同一个带权图,从顶点 D 开始。初始时树中仅包含 D。它的邻边有: C(权1), B(5), E(3)。最小的是 CD=1,添加 C。这时树包含 D 和 C。从 {D,C} 连向外部的边有: 从 C 出发: CA=3, CB=3, CE=4;从 D 出发: DB=5, DE=3。最小的为 CA=3 或 CB=3 或 DE=3,任选即可。选择 CA=3,添加 A。树变为 {D,C,A}。继续寻找连接外部的边: 从 A: AB=2, AD=4;从 C: CB=3, CE=4;从 D: DE=3, DB=5。最小的是 AB=2,添加 B。树变为 {D,C,A,B}。最后选择 DE=3 将 E 纳入。总权重 = 1+3+2+3 = 9,与克鲁斯卡尔算法结果完全相同。
In an exam table format, Prim’s is often set out with columns for step number, chosen edge, and weight. Practice drawing the partially built tree after each step to avoid accidentally forming a cycle.
在考试中,普里姆算法通常会以表格形式呈现,表中有步骤编号、被选中的边和权重等列。建议每步都画出当前的部分树,以防不经意间引入圈。
6. Interpreting Minimum Spanning Trees in Context | 在实际情境中解读最小生成树
Once you have found a minimum spanning tree, exam questions often ask you to interpret its meaning in the given context. For instance, a railway company wants to connect towns with new tracks, minimising construction cost. The MST gives the cheapest way to ensure every town is linked. Similarly, a computer network can be laid with the shortest total cable length by following the MST. Be ready to state the total weight and explain why no cheaper network exists.
找到最小生成树后,考试题目常常要求你在给定情境中解释它的含义。例如,一个铁路公司想要用新的铁轨连接若干个城镇,并希望建设成本最低。MST 给出的就是让所有城镇都连通的最省钱方案。再比如,铺设一个计算机网络时,如果按照 MST 布线,就可以使用最短的总线缆长度。你要能够写出总权重,并解释为什么不存在成本更低的连通方案。
You may also face a problem where an existing network needs to be reduced to a tree (e.g., closing roads for maintenance while keeping all towns accessible). In this case, you want to select the edges to keep, which is equivalent to finding a spanning tree of the original graph, but not necessarily the minimum one – read the question carefully!
你还可能遇到这样的问题:现有一个网络需要缩减为一棵树(例如为维护道路而关闭部分路段,但仍需保持所有城镇之间的连通)。此时你要选择保留哪些边,这等价于从原图中找出一棵生成树,但未必是最小生成树——一定要仔细审题!
7. Shortest Path: Dijkstra’s Algorithm | 最短路径:迪杰斯特拉算法
Dijkstra’s algorithm finds the shortest path from a given start vertex to all other vertices in a weighted graph with non-negative weights. It works by labelling vertices with temporary distances, improving them step by step until the shortest distance to each vertex is confirmed. You maintain a list of unvisited vertices and always pick the one with the smallest tentative distance next. This is a key algorithm for route-finding problems.
迪杰斯特拉算法用于在边权非负的加权图中,找出从给定起点到所有其他顶点的最短路径。它的做法是为每个顶点标出临时距离值,然后一步步改进这些值,直至每个顶点的最短距离被确定下来。你需要维护一个未访问顶点的列表,并且每一步都选择当前临时距离最小的顶点进行处理。这是解决路径查找问题的一个核心算法。
Dijkstra’s method step-by-step:
- Label the start vertex with distance 0 and all others with infinity (∞). Mark the start as the ‘current’ vertex.
- For the current vertex, consider all its unvisited neighbours and calculate their distances through the current vertex. If this new distance is smaller than the previously recorded distance, update it.
- After considering all neighbours, mark the current vertex as visited. A visited vertex will not be checked again.
- Choose the unvisited vertex with the smallest tentative distance as the new current vertex. If there are none left, stop. Otherwise, go back to step 2.
迪杰斯特拉算法步骤:
- 给起点标上距离 0,其余顶点标上无穷大 (∞)。将起点设为“当前”顶点。
- 检查当前顶点的所有未访问邻居,计算从起点经当前顶点到达邻居的距离。如果这个新距离小于之前记录的距离,就用新值更新。
- 检查完所有邻居后,将当前顶点标记为已访问。已访问的顶点不会再次被检查。
- 从未访问顶点中选择临时距离最小的那一个作为新的当前顶点。如果没有剩余未访问顶点,则算法结束。否则回到步骤 2。
Worked example: Graph with vertices A,B,C,D,E and weighted edges: AB=6, AC=3, BC=2, BD=5, CD=3, CE=4, DE=2. Start at A. Distances: A=0, B=∞, C=∞, D=∞, E=∞. From A: B via A=6, C via A=3 → update B=6, C=3. Mark A visited. Smallest unvisited is C=3. From C: A visited; B via C: 3+2=5 (<6) → update B=5; D via C: 3+3=6 → update D=6; E via C: 3+4=7 → update E=7. Mark C visited. Next smallest B=5. From B: C visited; D via B: 5+5=10 (>6) so no change. Mark B visited. Next small D=6. From D: C visited; E via D: 6+2=8 (>7) no change. Mark D visited. Finally E=7. Shortest distances from A: B=5, C=3, D=6, E=7.
例题: 图有顶点 A,B,C,D,E,带权边: AB=6, AC=3, BC=2, BD=5, CD=3, CE=4, DE=2。起点为 A。距离初始化: A=0, B=∞, C=∞, D=∞, E=∞。从 A 出发: 经 A 到 B 为 6,经 A 到 C 为 3,更新 B=6, C=3。A 标记为已访问。未访问顶点中最小为 C=3。从 C 出发: A 已访问;经 C 到 B: 3+2=5 (<6) 更新 B=5;经 C 到 D: 3+3=6 更新 D=6;经 C 到 E: 3+4=7 更新 E=7。C 标记为已访问。下一个最小为 B=5。从 B 出发: C 已访问;经 B 到 D: 5+5=10 (>6) 不更新。B 标记为已访问。下一个最小 D=6。从 D 出发: C 已访问;经 D 到 E: 6+2=8 (>7) 不更新。D 标记为已访问。最后 E=7。从 A 出发的最短距离: B=5, C=3, D=6, E=7。
Always present your work in a tidy table with columns for vertex, distance, previous vertex, and visited status. This makes your method clear and helps secure full marks.
考试中一定要将计算过程整理成一个清晰的表格,列明顶点、当前最短距离、前驱顶点和是否已访问。这样可以让你的解法一目了然,确保拿到满分。
8. Shortest Path Interpretation and Alternative Routes | 最短路径的解读与备选路线
Once you have completed Dijkstra’s table, you can trace back from the destination to find the exact route. For instance, in the example above, to reach B from A, the shortest distance is 5, achieved via A→C→B. This reversing process uses the ‘previous vertex’ column. The exam may ask you to state the route clearly or to draw it on a diagram.
完成迪杰斯特拉算法的表格后,你可以从终点开始反向追溯,找出精确的路径。比如在上面的例子中,从 A 到 B 的最短距离为 5,路径为 A→C→B。这个反向过程需要利用“前驱顶点”那一列。考题可能会要求你清楚地写出这条路线,或者在图上把它画出来。
When two routes have the same length, Dijkstra’s algorithm may find either. Always keep track of alternatives in your table, and in worded problems, discuss which route might be more practical (e.g., one route involves fewer turns or avoids a tunnel with a height restriction). IGCSE questions sometimes link graph theory to real-life constraints.
当两条路线的长度相同时,迪杰斯特拉算法可能找到其中任意一条。你应该在表格中记录备选方案,并在文字题中讨论哪条路线在实际中更可行(例如,某条路线转弯更少,或者能够避开有高度限制的隧道)。IGCSE题目有时会将图论与现实约束结合起来考查。
9. Eulerian Graphs – Trails Covering Every Edge | 欧拉图:遍历每条边的迹
An Eulerian trail (or Euler trail) is a trail that uses every edge of a graph exactly once. An Eulerian circuit is an Euler trail that starts and ends at the same vertex. A graph has an Eulerian circuit if and only if it is connected and every vertex has an even degree. A graph has an Eulerian trail but not a circuit if it is connected and exactly two vertices have odd degrees (and the trail must start at one odd-degree vertex and end at the other). This classic result (Euler’s theorem) helps solve problems like the famous Königsberg bridges or determining whether a postman can walk a route covering each street exactly once.
欧拉迹(Euler trail)是一条经过图中每条边恰好一次的迹。欧拉回路则是一条起点和终点相同的欧拉迹。一个连通图具有欧拉回路,当且仅当它的每一个顶点的度数都是偶数。一个连通图具有欧拉迹但不具有欧拉回路,当且仅当它恰好有两个奇数度顶点(而且迹必须从一个奇数度顶点出发,到另一个奇数度顶点结束)。这个经典结论(欧拉定理)可以用于解决诸如著名的柯尼斯堡七桥问题,或者判断一个邮递员是否能够设计出一条恰好走过每条街道一次的路线。
In exam questions, you are likely to be asked whether a given graph has an Eulerian trail or circuit. Count the degrees of all vertices, identify odd-degree vertices, and apply the rules. No algorithm construction is required at IGCSE – only the existence check and statement of the starting and ending vertices.
在考试题中,你很可能会被问到给定的图是否存在欧拉迹或欧拉回路。只要数出所有顶点的度数,找出奇数度顶点,然后运用上述规则即可。IGCSE不要求构造算法,只需要判断是否存在,并指明轨迹的起点和终点。
10. Hamiltonian Graphs – Visiting Every Vertex Once | 哈密顿图:遍历每个顶点一次
A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle is a Hamiltonian path that returns to the starting vertex. Unlike Eulerian problems, there is no simple necessary and sufficient condition for a graph to be Hamiltonian. However, certain sufficient conditions are known: for example, Dirac’s theorem states that a simple graph with n ≥ 3 vertices has a Hamiltonian cycle if every vertex has degree at least n/2. In IGCSE, you mainly need to recognise Hamiltonian cycles in small networks, perhaps applied to travelling salesman–style problems.
哈密顿路径经过图中每个顶点恰好一次;哈密顿圈则是一条能够返回起点的哈密顿路径。与欧拉问题不同,判断一个图是否为哈密顿图没有简单的充要条件。不过,有一些已知的充分条件,比如狄拉克定理:如果一个简单图有 n ≥ 3 个顶点,且每个顶点的度数都至少为 n/2,则该图必定存在哈密顿圈。在IGCSE阶段,你主要需要在小型网络中识别哈密顿圈,并可能将其应用于类似于旅行商问题(TSP)的情景中。
For instance, a salesperson wishes to visit four cities exactly once and return, minimising total distance. The exam may provide a table or graph of distances and ask you to find a short – though not necessarily the absolute shortest – route by inspection. Common techniques include the nearest neighbour method. You must list the order of cities and calculate the total distance.
例如,一个销售员想要恰好访问四个城市一次并返回,要求总路程最短。考题可能会给出距离表格或带权图,要求你通过观察找到一个比较短的路线(不一定是绝对最短的)。常用的技巧包括最近邻点法。你需要列出城市的访问顺序,并计算总路程。
11. Tackling IGCSE Extended Reasoning Problems | IGCSE拓展推理题型的应对策略
IGCSE AQA papers often set graph theory questions in a practical context, requiring you to choose the correct algorithm, show your working, and then interpret the results. They may also include unfamiliar variations: a graph with some directed edges, a network with constraints like time windows, or the need to modify an MST after a new edge is added. To handle these, stay calm and focus on the principles: Kruskal’s builds by avoiding cycles; Prim’s grows by connecting nearest outside vertex; Dijkstra’s updates shortest distances from a start point.
IGCSE AQA的试卷经常将图论问题放在实际情境中,要求你选择合适的算法,展示解题过程,并对结果进行解读。试题中还可能出现一些不常见的变化形式:包含部分有向边的图,带有时间窗口等限制条件的网络,或者需要在添加新边后调整MST。面对这些情况时要保持冷静,紧扣基本原理:克鲁斯卡尔通过避圈来构建;普里姆通过连接最近的树外顶点来生长;迪杰斯特拉从起点更新最短距离。
Always read the rubric to see whether you need to find the minimum length or just any spanning tree. Check if the graph is complete or if edges are already missing. When adapting an MST after adding an edge, remember that the new edge may create a cycle; removing the largest edge in that cycle restores a tree with possibly reduced total weight.
务必仔细阅读题目说明,看是需要找出最小长度,还是只需要任意一棵生成树。检查图是否为完全图,或者某些边是否已被移除。在添加一条边后调整MST时,要记住新边可能会产生一个圈;只需删除该圈上权重最大的边,就能恢复成一棵树,总权重还有可能降低。
12. Revision Tips and Exam Technique | 复习建议与应试技巧
Do: Practise writing out Kruskal’s sorted list with clear accept/reject annotations; draw Prim’s step-by-step networks; always create a Dijkstra table and update methodically. Learn the degree conditions for Eulerian trails and circuits. Don’t: Just skim over – graph algorithms are procedural, and you gain marks for showing the correct sequence. Avoid rushing the addition of edges: one mistake can cascade through your answer.
要做的是:练习列出克鲁斯卡尔算法的排序表,并清楚地标注“接受”或“拒绝”;逐步画出普里姆算法的网络图;每次使用迪杰斯特拉算法时都画表格,并逐行更新。记住欧拉迹和欧拉回路的度数条件。不要做的是:仅仅略读——图论算法非常注重过程,展示正确的步骤就能得分。切莫匆忙添加边,因为一个错误可能会导致后续答案全盘崩塌。
When calculators are allowed, use them for quick addition, but still write down the arithmetic. For Dijkstra, a small error in addition can propagate, so double-check each update. In open-answer questions, always link the mathematics back to the context: ‘The total length of fibre optic cable needed is 34 km, connecting all villages at minimum cost’.
在允许使用计算器时,可以用它快速加法,但仍需把算式写下来。对迪杰斯特拉算法来说,一个微小的加数错误就可能传播到后面,因此每次更新后都要再核对一遍。在开放性回答题中,始终要将数学结果回扣到题目情境中,例如:“所需光纤缆线的总长度为 34 km,可以以最低成本连接所有村庄。”
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022(同微信)