📚 Graph Theory Key Concepts for IB & Edexcel Mathematics | IB 与 Edexcel 数学：图论考点精讲
Graph theory is a fascinating branch of mathematics that models pairwise relations between objects. In both the IB Diploma (especially the Analysis & Approaches HL option and Applications & Interpretation HL) and the Edexcel A Level Further Mathematics (Decision Mathematics 1), graph theory appears as a structured topic covering algorithms, networks, and logical problem-solving. Understanding the fundamental terminology and applying algorithms precisely are key to scoring well. This article systematically unpacks the essential concepts, from basic definitions to advanced algorithms, with clear explanations, worked examples, and exam-focused insights.
图论是数学中一个迷人的分支，它用图来模拟对象之间的成对关系。在 IB 文凭课程（尤其是分析与方法 HL 选修和应用与解释 HL）和 Edexcel A Level 进阶数学（决策数学 1）中，图论都是一个结构化的专题，涵盖算法、网络和逻辑问题求解。理解基本术语并精确应用算法是取得高分的关键。本文系统梳理了从基础定义到高级算法的核心概念，提供清晰的解释、示例和备考要点。
1. What is a Graph? Basic Terminology | 什么是图？基本术语
A graph G = (V, E) consists of a set of vertices (or nodes) V and a set of edges E connecting pairs of vertices. An edge can be represented as an unordered pair {u, v} for an undirected graph or as an ordered pair (u, v) for a directed graph (digraph). Loops are edges that connect a vertex to itself, and multiple edges between the same pair of vertices create a multigraph. A simple graph has no loops and no multiple edges.
一个图 G = (V, E) 由顶点集 V 和边集 E 组成，边连接顶点对。在无向图中，边可表示为无序对 {u, v}；在有向图中，边是有序对 (u, v)。环是连接顶点自身的边，而同一对顶点间多条边构成多重图。简单图既没有环也没有多重边。
The degree of a vertex in an undirected graph is the number of edges incident to it, with loops counting twice. For directed graphs, we distinguish in-degree (edges entering) and out-degree (edges leaving). A graph can be represented using an adjacency matrix or an adjacency list. In examinations, you must be able to construct such representations from a given diagram or word problem.
在无向图中，顶点的度是与它关联的边的数目，环按两次计算。对有向图，我们区分入度（进入的边）和出度（离开的边）。图可以用邻接矩阵或邻接表来表示。在考试中，你需要根据给定的图形或文字描述构建这些表示。
Key terms: isolated vertex (degree 0), pendant vertex (degree 1), and regular graph (all vertices have same degree). For example, a complete graph Kn has n vertices and every possible edge, so each vertex has degree (n – 1). The Handshaking Lemma states that the sum of the degrees of all vertices equals 2 × (number of edges). This result is often used to deduce the number of edges given a degree sequence.
关键术语：孤立顶点（度为 0）、悬挂顶点（度为 1）和正则图（所有顶点度数相同）。例如，完全图 Kn 有 n 个顶点，包含所有可能的边，因此每个顶点的度为 (n – 1)。握手引理指出所有顶点的度数之和等于边数的两倍。这个结论常用来根据度序列推导边的数量。
2. Degrees, Paths and Cycles | 度、路径与环
A walk is a sequence of vertices where consecutive vertices are adjacent. A trail is a walk with no repeated edges, and a path is a walk with no repeated vertices. A cycle (or circuit) is a closed walk where the only repeated vertices are the first and last, and no edges are repeated. Understanding these distinctions is crucial for identifying Eulerian and Hamiltonian structures.
一条途径是一个顶点序列，其中连续顶点相邻。迹是没有重复边的途径，路径是没有重复顶点的途径。环（或回路）是一条闭合途径，只有首尾顶点重复，且没有重复边。理解这些区别对识别欧拉和哈密顿结构至关重要。
The length of a path or cycle is the number of edges it contains. In weighted graphs, we calculate the total weight as the sum of the edge weights along the route. A graph is connected if there exists a path between every pair of vertices. A disconnected graph can be split into connected components. A bridge (or cut-edge) is an edge whose removal increases the number of connected components.
路径或环的长度是指它包含的边数。在带权图中，路线总权重等于沿途边权重之和。如果每对顶点之间都存在路径，则图是连通的。非连通图可分成几个连通分支。桥（或割边）是删除后会增加连通分支数的边。
For directed graphs, we talk about strong connectivity (paths exist in both directions between any two vertices) and weak connectivity (the underlying undirected graph is connected). Exam questions often ask you to identify whether a given graph is connected or to find a path satisfying certain weight conditions.
对有向图，我们讨论强连通（任意两顶点间双向都存在路径）和弱连通（其底图无向图是连通的）。考题经常要求判断给定图是否连通，或者找到满足一定权重条件的路径。
3. Special Types of Graphs | 特殊类型的图
Several graph families appear regularly in IB and Edexcel exams. A complete bipartite graph Km,n has vertices partitioned into two sets of sizes m and n, with every vertex in the first set connected to every vertex in the second set, and no edges within the same set. For instance, K3,3 is a famous non-planar graph.
IB 和 Edexcel 考试中经常出现几类特殊图。完全二分图 Km,n 的顶点划分为两个大小分别为 m 和 n 的集合，第一集合中的每个顶点都与第二集合中的每个顶点相连，同一集合内无边。例如 K3,3 是著名的非平面图。
A tree is a connected, undirected graph with no cycles. A forest is a collection of disconnected trees. In a tree with n vertices, there are exactly n – 1 edges, and adding any edge creates exactly one cycle. Rooted trees direct edges away from a chosen root and are used in algorithms like Prim’s and Dijkstra’s.
树是连通且无环的无向图。森林是不连通的若干棵树的集合。一棵有 n 个顶点的树恰好有 n – 1 条边，添加任意一条边都恰好产生一个环。有根树从选定的根出发定向所有边，常用于 Prim 算法和 Dijkstra 算法。
Weighted graphs assign a numerical weight (cost, distance, time) to each edge. Such graphs model real-world networks. Throughout graph algorithms, you will work with adjacency matrices that record weights (and sometimes indicate no edge with a dash or infinity).
带权图为每条边赋予一个数值权重（成本、距离、时间）。这类图用于对现实世界网络建模。在各种图算法中，你将用到记录权重的邻接矩阵（有时用横线或无穷大表示无边）。
4. Eulerian Graphs and Eulerian Trails | 欧拉图与欧拉路径
An Eulerian trail (or Eulerian path) is a trail that uses every edge of a graph exactly once. An Eulerian circuit (or Eulerian tour) is an Eulerian trail that starts and ends at the same vertex. A connected graph that contains an Eulerian circuit is called an Eulerian graph. Euler’s famous theorem states that a connected graph is Eulerian if and only if every vertex has even degree.
欧拉轨迹（欧拉路径）是一条恰好经过每条边一次的迹。欧拉回路（欧拉环游）是起点和终点相同的欧拉轨迹。包含欧拉回路的连通图称为欧拉图。欧拉著名定理指出：一个连通图是欧拉图当且仅当每个顶点的度均为偶数。
If a connected graph has exactly two vertices of odd degree, then it contains an Eulerian trail but no Eulerian circuit; the trail must start at one odd-degree vertex and end at the other. If there are more than two odd-degree vertices, no Eulerian trail exists. For directed graphs, the corresponding conditions are: every vertex must have equal in-degree and out-degree for an Eulerian circuit; for an Eulerian trail, exactly one vertex has out-degree = in-degree + 1 (start) and one has in-degree = out-degree + 1 (end), with all others balanced.
如果一个连通图恰好有两个奇数度顶点，则它包含欧拉轨迹但不含欧拉回路；该轨迹必须从一个奇数度顶点出发并在另一个结束。如果奇数度顶点多于两个，则不存在欧拉轨迹。对于有向图，相应条件为：欧拉回路要求每个顶点的入度等于出度；对于欧拉轨迹，恰好一个顶点出度比入度大 1（起点），一个顶点入度比出度大 1（终点），其余顶点平衡。
Finding an Eulerian trail can be done using Fleury’s algorithm (bridges avoided if possible) or Hierholzer’s algorithm. Exam questions may ask you to determine if a graph is Eulerian and to list a valid trail.
寻找欧拉轨迹可以使用弗勒里算法（尽可能避开桥）或希尔霍尔泽算法。考题可能要求判断一个图是否为欧拉图，并列出可行的轨迹。
5. Hamiltonian Graphs & Hamiltonian Cycles | 哈密顿图与哈密顿环
A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle (or Hamiltonian circuit) 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, making this an NP-complete problem in general. However, some theorems provide sufficient conditions.
哈密顿路径恰好访问每个顶点一次；哈密顿环（哈密顿回路）是回到起点的哈密顿路径。与欧拉问题不同，对于哈密顿图不存在简单的充要条件，这使得该问题在一般情况下是 NP 完全的。然而，有一些定理给出了充分条件。
Dirac’s theorem: If a simple graph with n ≥ 3 vertices has every vertex of degree at least n/2, then the graph is Hamiltonian. Ore’s theorem: If for every pair of non-adjacent vertices u and v, deg(u) + deg(v) ≥ n, then the graph is Hamiltonian. In IB and Edexcel, you are more likely to be asked to find a Hamiltonian cycle by inspection or through an algorithm like the nearest neighbour method for the Traveling Salesman Problem.
狄拉克定理：若含 n ≥ 3 个顶点的简单图中每个顶点的度至少为 n/2，则该图是哈密顿图。奥尔定理：若对每一对不相邻的顶点 u 和 v，均有 deg(u) + deg(v) ≥ n，则该图是哈密顿图。在 IB 和 Edexcel 考试中，更常见的要求是通过观察或通过旅行商问题的最近邻算法来找到哈密顿环。
Counting Hamiltonian cycles in a complete graph Kn (considering direction but undirected cycle) yields (n – 1)! / 2 distinct cycles. This factorial growth explains the complexity of the TSP.
完全图 Kn 中哈密顿环的数目（无向环，考虑不同起点和方向约简）为 (n – 1)! / 2。这个阶乘增长解释了 TSP 问题的复杂性。
6. Trees and Spanning Trees | 树与生成树
A spanning tree of a connected graph G is a subgraph that includes all vertices of G and is a tree. Every connected graph has at least one spanning tree. A minimum spanning tree (MST) of a weighted graph is a spanning tree with the smallest possible total edge weight.
连通图 G 的生成树是一个包含 G 所有顶点的子图，且它本身是一棵树。每个连通图都至少有一棵生成树。带权图的最小生成树（MST）是一棵总边权尽可能小的生成树。
Properties of trees: a tree with n vertices has exactly n – 1 edges; removing any edge disconnects it; adding any edge creates exactly one cycle. These facts are often used to prove statements about networks. In an MST problem, you must ensure the subgraph spans all vertices, has no cycles, and minimizes total weight.
树的性质：n 个顶点的树恰有 n – 1 条边；删除任意边都会使其不连通；添加任意边都恰好形成一个环。这些事实常被用来证明有关网络的命题。在 MST 问题中，必须确保子图涵盖所有顶点，无环，且总权重最小。
The concept of a minimum spanning tree is applied in designing networks (e.g., electrical grids, pipelines) to minimize cost. Both Kruskal’s and Prim’s algorithms are standard exam content.
最小生成树的概念应用于设计网络（如电网、管道），以最小化成本。克鲁斯卡尔算法和普里姆算法都是标准的考试内容。
7. Minimum Spanning Tree Algorithms | 最小生成树算法
Kruskal’s algorithm: sort all edges in non-decreasing order of weight; initialize a forest where each vertex is a separate tree. Process edges one by one; if the edge connects two different trees, add it to the forest (merging the trees); otherwise, discard it. Stop when n – 1 edges have been added. This is an efficient greedy algorithm often demonstrated with a table.
克鲁斯卡尔算法：将所有边按权重非递减排序；初始化一个森林，每个顶点就是一棵单独的树。依次处理边；如果边连接两棵不同的树，则将其加入森林（合并树）；否则丢弃。当添加了 n – 1 条边时停止。这是一种高效的贪心算法，常用表格展示。
Prim’s algorithm: start at any vertex and grow a tree. Maintain a set of connected vertices. At each step, consider all edges crossing the cut between connected and non-connected vertices, select the one with minimum weight, and add the new vertex and edge to the tree. Continue until all vertices are included. A tabular method (potential method) or matrix approach is often used.
普里姆算法：从任意顶点开始生长树。维护一个已连接顶点集。每一步，考虑跨切分（已连接顶点与未连接顶点之间）的所有边，选择权重最小者，将新顶点和边加入树。继续直到所有顶点被包含。常使用表格法（势能法）或矩阵法。
Both algorithms guarantee an MST. Kruskal’s may be more intuitive for sparse graphs or when edges are pre-sorted, while Prim’s is easily implemented on a distance matrix. Exam questions frequently ask you to execute these algorithms step-by-step and state the final MST and its total weight.
两种算法都能保证最小生成树。克鲁斯卡尔算法对稀疏图或当边已预排序时更直观，而普里姆算法在距离矩阵上容易实现。考题经常要求逐步执行这些算法，并给出最终 MST 及其总权重。
Comparison table:
| Algorithm | Approach | Data Structure | Exam note |
|---|---|---|---|
| Kruskal | Add smallest edges avoiding cycles | Edge list | Check for cycles using sets |
| Prim | Grow tree from starting vertex | Adjacency matrix / list | Update ‘potentials’ stepwise |
上表对比：Kruskal 使用边列表，按权排序，需用集合检查环；Prim 从起点生长树，使用邻接矩阵，逐步更新“势能”。
8. Dijkstra’s Algorithm for Shortest Path | 最短路径—迪杰斯特拉算法
Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a priority queue (or box method in exam scripts) to repeatedly select the vertex with the smallest temporary distance, finalise it, and update its neighbours.
迪杰斯特拉算法用于在边权非负的带权图中找出从源顶点到所有其他顶点的最短路径。它使用优先队列（或考试中的“盒子法”）反复选择临时距离最小的顶点，将其固定，并更新其邻居的距离。
The standard box method taught in Edexcel D1 and applicable in IB: Start with a table where the initial vertex has distance 0, others infinity. Each iteration, choose the unvisited vertex with smallest working value, mark it as visited, and for each neighbour not visited, calculate new distance = current vertex distance + edge weight; if smaller, update. Record the order of labelling and final distances. To find the route, trace back via predecessor notes.
Edexcel D1 及 IB 教学中常用的盒子法：建立一个表格，初始顶点距离为 0，其余为无穷大。每次迭代选取未访问中工作值最小的顶点，将其标记为已访问；对该顶点的每个未访问邻居，计算新距离 = 当前顶点距离 + 边权；若更小则更新。记录标号顺序和最终距离。通过前驱记录回溯即可找到路线。
Key points: Dijkstra’s algorithm does not work with negative weights; it produces a shortest-path tree. When multiple shortest paths exist, the algorithm may give one. Exam questions often involve tracing the algorithm on a network with 5-8 vertices and stating the shortest path and its length.
关键点：Dijkstra 算法不适用于负权边；它生成一棵最短路径树。当存在多条最短路径时，算法可能只给出其中一条。考试题目通常要求在 5-8 个顶点的网络上追踪算法，并说明最短路径及其长度。
If the graph has a small number of vertices, you might be asked to write down the distance matrix and apply Dijkstra’s. Ensure you understand both the tabular method and the concept of permanent vs temporary labels.
如果图的顶点数较少，可能会要求写出距离矩阵并应用 Dijkstra 算法。务必同时掌握表格法以及永久标号与临时标号的概念。
9. The Travelling Salesman Problem | 旅行商问题
The classic Travelling Salesman Problem (TSP) requires finding a Hamiltonian cycle of minimum total weight in a complete weighted graph. It is a computationally hard problem. In IB and Edexcel, you are expected to find upper and lower bounds to estimate the optimal tour length rather than find the exact solution (except for very small n).
经典的旅行商问题（TSP）要求在完全带权图中找到总权重最小的哈密顿环。这是一个计算困难的问题。在 IB 和 Edexcel 中，期望通过寻找上界和下界来估计最优巡回长度，而不是精确求解（除非 n 非常小）。
Upper bounds can be found using heuristics like the nearest neighbour algorithm: start at a vertex, repeatedly go to the nearest unvisited vertex, then return to start. The total length provides an upper bound. You can improve this by trying different starting vertices. Another method is the minimum spanning tree lower bound trick: double MST weight gives a bound, but a better lower bound is obtained by removing a vertex, finding the MST of the remaining vertices, and adding the two shortest edges from the removed vertex — this gives a lower bound for the TSP.
上界可使用启发式算法求得，如最近邻算法：从一个顶点出发，反复前往最近的未访问顶点，最后回到起点。总长度即为一个上界。可通过尝试不同起点改善。另一种方法是用最小生成树下界技巧：将 MST 权重加倍得到一个界，但更好的下界是：删除一个顶点，求剩余顶点的 MST，再加上从该删除顶点出发的两条最短边的权重——这就给出了 TSP 的一个下界。
Exam questions often require calculating both bounds and stating an inequality: lower bound ≤ optimal tour ≤ upper bound. For small instances (n = 4 or 5), you may be asked to find the optimal tour by exhaustive search. Always search for symmetries to reduce cases.
考题经常要求计算上下界并给出不等式：下界 ≤ 最优巡回 ≤ 上界。对于小规模实例（n = 4 或 5），可能要求通过穷举搜索找到最优巡回。注意利用对称性减少情况。
The practical problem-solving here links graph theory to real logistics, so understand the modeling: vertices represent cities, edge weights represent travel costs/distances, objective is to visit each city exactly once and return, minimising total cost.
此处的实际应用将图论与真实物流联系起来，故需理解建模：顶点代表城市，边权代表旅行成本/距离，目标是恰好访问每座城市一次并返回，最小化总成本。
10. Graph Colouring and Chromatic Number | 图着色与色数
Vertex colouring assigns colours to vertices such that no two adjacent vertices share the same colour. The chromatic number χ(G) is the minimum number of colours needed. This appears in scheduling problems (e.g., exams, meetings). The greedy colouring algorithm orders vertices and assigns the smallest available colour; it does not always give the optimal χ(G).
顶点着色是为顶点分配颜色，使得相邻顶点颜色不同。色数 χ(G) 是所需的最少颜色数。这在排课、会议安排等调度问题中出现。贪心着色算法将顶点排序并分配最小的可用颜色；但这不一定给出最优 χ(G)。
A graph is bipartite if and only if it is 2-colourable (no odd cycles). The Four Colour Theorem states that any planar graph can be coloured with at most 4 colours. In IB and Edexcel, you may be asked to determine the chromatic number of a given small graph, prove whether it is bipartite, or schedule tasks using a conflict graph.
一个图是二分图当且仅当它是 2-可着色的（没有奇环）。四色定理指出任何平面图都可用至多 4 种颜色着色。在 IB 和 Edexcel 中，可能要求确定一个小图的色数，证明它是否为二分图，或使用冲突图进行任务调度。
The chromatic index (edge coloring) may be mentioned but vertex coloring is the main focus. A common exam task: from a table of incompatibilities, draw the graph, apply a greedy algorithm, and state the number of colours used. Then justify whether a better (smaller) colouring exists.
边着色（色指数）可能提及，但主要重点是顶点着色。常见考题：根据一张不相容表画出图，应用贪心算法，说明使用的颜色数；然后判断是否存在更优（更少颜色）的着色。
11. Planar Graphs and Euler’s Formula | 平面图与欧拉公式
A planar graph can be drawn in a plane without any edges crossing. Such a drawing divides the plane into faces (regions), including the outer infinite face. Euler’s formula for a connected planar graph: v – e + f = 2, where v = number of vertices, e = number of edges, f = number of faces. This is a powerful relation linking the three counts.
平面图是能够画在平面上而没有任何边交叉的图。这样的画法将平面划分为面（区域），包括外部无限面。连通平面图的欧拉公式：v – e + f = 2，其中 v 为顶点数，e 为边数，f 为面数。这是一个关联三者的强大关系式。
To use Euler’s formula, you must be given or deduce one of the counts and confirm that the graph is planar. For simple, connected planar graphs with v ≥ 3, we also have the inequality e ≤ 3v – 6. This can be used to prove certain graphs are non-planar (e.g., K5 has v=5, e=10, and 10 > 3×5 – 6 = 9, so K5 is non-planar). K3,3 does not violate this inequality but is also non-planar via a bipartite version.
要使用欧拉公式，通常需已知或推导出其中两个计数，并确认图是平面图。对于满足 v ≥ 3 的简单连通平面图，还有不等式 e ≤ 3v – 6。这可用于证明某些图非平面（例如 K5 有 v=5, e=10, 10 > 3×5 – 6 = 9，所以 K5 并非平面）。K3,3 虽不违反该不等式，但通过二分图版本也不可能是平面图。
Exam questions may ask: given a planar graph’s drawing, count faces; verify Euler’s formula; or apply v – e + f = 2 to find an unknown quantity. They can also combine this with graph colouring: since planar graphs are 4-colourable, you may need to determine whether a planar graph’s chromatic number is 2, 3, or 4.
考题可能要求：根据平面图的画法数出面数；验证欧拉公式；或应用 v – e + f = 2 求出未知量。还可能结合图着色：因平面图是 4-可着色的，可能需要判断色数是 2、3 还是 4。
12. Exam Tips and Common Mistakes | 考试技巧与常见错误
Many students lose marks by confusing vertices and edges, or mixing Eulerian and Hamiltonian conditions. Remember: Eulerian trails/circuits cover all edges exactly once and rely on vertex degrees; Hamiltonian paths/cycles cover all vertices exactly once and have no simple degree-based condition. Write clear steps when tracing algorithms — examiners need to see your reasoning.
许多学生因混淆顶点和边，或分不清欧拉条件与哈密顿条件而失分。请牢记：欧拉轨迹/回路要求恰好经过所有边一次，依据顶点度数；哈密顿路径/环要求恰好访问所有顶点一次，没有简单的度数条件。追踪算法时要写下清晰步骤——考官需要看到你的推理过程。
When performing Kruskal’s or Prim’s, list selected edges in order with their weights, and state the total weight explicitly. For Dijkstra, use the box method, scratch out old working values when updated, and record final values. If a question asks for a path, give the vertex sequence and its length.
在应用克鲁斯卡尔或普里姆算法时，按顺序列出所选边及其权重，并明确写出总权重。对于迪杰斯特拉算法，使用盒子法，更新时划掉旧工作值，记录最终值。如果题目要求路径，给出顶点序列及其长度。
Check for reading errors: directed vs undirected, whether weights are symmetric, and if loops or multiple edges are allowed. In graph theory proofs, avoid hand-waving; use precise definitions. For the TSP, unless instructed, do not attempt exhaustive search for n > 6 — use bounds.
检查阅读错误：有向图还是无向图、权重是否对称、是否允许环或重边。在证明中避免模糊不清，使用精确定义。对于 TSP，除非特别说明，对 n > 6 的实例不要尝试穷举搜索，应使用上下界。
Finally, practice with past IB and Edexcel D1 questions. Graph theory builds confidence once the patterns are recognised. Master the algorithms, understand the underlying logic, and you’ll be well-prepared for any exam scenario.
最后，多做 IB 和 Edexcel D1 历年真题。一旦识别出模式，图论将让你充满信心。掌握算法，理解底层逻辑，你就能从容应对任何考试情境。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导