📚 Graph Theory Essentials for IB & CIE Mathematics | IB CIE 数学：图论考点精讲
Graph theory is a vibrant area of discrete mathematics that models pairwise relations between objects. In IB and CIE syllabuses, graph theory appears as a standalone topic combining algorithmic thinking, logical reasoning, and real-world applications — from navigation to scheduling. This article distils the essential definitions, theorems, and algorithms you must master for the exam.
图论是离散数学中一个充满活力的领域，用于刻画事物之间的两两关系。在 IB 和 CIE 的考纲中，图论作为一个独立主题，融合了算法思维、逻辑推理以及从导航到调度的现实应用。本文将提炼考试必须掌握的必备定义、定理和算法。
1. What is a Graph? | 什么是图？
et V of vertices (or nodes) and a set E of edges, where each edge connects a pair of vertices. Edges can be represented as unordered pairs {u, v} for undirected graphs, or ordered pairs (u, v) for directed graphs (digraphs). A loop is an edge connecting a vertex to itself; multiple edges between the same pair are called parallel edges. A simple graph has no loops and no parallel edges.
图 G = (V, E) 由有限顶点集 V 和边集 E 组成，每条边连接一对顶点。在无向图中，边表示为无序对 {u, v}；在有向图中，边表示为有序对 (u, v)。连接顶点自身的边称为环，同一对顶点之间的多条边称为平行边。简单图不允许有环和平行边。
- Order of a graph is |V|, the number of vertices.
- 图的 阶 是 |V|，即顶点数。
- Size is |E|, the number of edges.
- 图的 规模 是 |E|，即边数。
A graph with n vertices has at most n(n − 1)/2 edges if simple and undirected. This maximum occurs in a complete graph Kn.
一个具有 n 个顶点的简单无向图最多有 n(n − 1)/2 条边，此时为完全图 Kn。
2. Types of Graphs | 图的分类
You will encounter several standard families in exam questions. A null graph has no edges. A complete graph Kn has every pair of vertices joined by exactly one edge. A bipartite graph has its vertex set partitioned into two disjoint sets X and Y such that every edge connects a vertex in X to a vertex in Y; there are no edges within X or within Y. A complete bipartite graph Km,n has all possible edges between the two parts.
考试中会碰到几种标准图类。零图没有边。完全图 Kn 中任意两个顶点都恰有一条边相连。二分图的顶点集可划分为两个互不相交的集合 X 和 Y，使得每条边都连接 X 中的一点与 Y 中的一点，X 内部和 Y 内部没有边。完全二分图 Km,n 包含两集合之间所有可能的边。
A subgraph is obtained by deleting some vertices and/or edges. An induced subgraph is formed by taking a subset of vertices and including all edges between them that were present in the original graph.
子图通过删除某些顶点和/或边得到。生成子图则取顶点子集，并包含原图中这些顶点之间所有的边。
The complement of a simple graph G has the same vertex set, but two vertices are adjacent in the complement if and only if they are not adjacent in G.
简单图 G 的补图具有相同的顶点集，两点在补图中相邻当且仅当它们在 G 中不相邻。
3. Degree of a Vertex | 顶点的度
The degree deg(v) of a vertex v in an undirected graph is the number of edges incident to v, with loops counted twice. In a directed graph we distinguish in-degree degin(v) and out-degree degout(v). The Handshaking Lemma states that the sum of degrees of all vertices equals 2|E|:
无向图中顶点 v 的度 deg(v) 是与 v 关联的边数，环算两次。有向图中区分入度 degin(v) 和出度 degout(v)。握手引理指出，所有顶点的度之和等于 2|E|：
Σ deg(v) = 2|E|
An immediate consequence is that every undirected graph has an even number of vertices of odd degree. This is used to prove that certain degree sequences cannot belong to a simple graph.
直接推论是任何无向图中奇度顶点的个数为偶数。这常用于证明某些度序列不可能是一个简单图的度序列。
A graph is regular if all vertices have the same degree; a 3-regular graph is called a cubic graph.
如果所有顶点具有相同的度，则称该图为正则图；3-正则图又称三次图。
4. Paths and Cycles | 路径与回路
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 hence no repeated edges). A closed walk starts and ends at the same vertex. A cycle (or circuit) is a closed walk with no repeated vertices except the starting/ending vertex, and length at least 3. The length of a path or cycle is the number of edges it contains.
路径序列中相邻顶点均有边相连即为一条路径。迹是不重复边的行走。路径是不重复顶点的行走（因此也不重复边）。闭行走起点与终点相同。回路（或圈）是除起点外无重复顶点的闭行走，长度至少为 3。路径或回路的长度为其所含边数。
A graph is connected if there is a path between every pair of vertices. Connected components are maximal connected subgraphs. A bridge (or cut-edge) is an edge whose removal increases the number of components.
若任意两顶点之间存在路径，则该图连通。连通分支是极大的连通子图。桥（或割边）是删除后会增加连通分支数的边。
The distance between two vertices is the length of a shortest path. The diameter of a graph is the greatest distance between any pair of vertices.
两顶点间的距离是最短路径的长度。图的直径是所有顶点对之间的最大距离。
5. Eulerian Graphs | 欧拉图
An Eulerian trail is a trail that traverses every edge exactly once. An Eulerian circuit (or tour) is an Eulerian trail that starts and ends at the same vertex. A graph is Eulerian if it contains an Eulerian circuit, and semi-Eulerian if it contains an Eulerian trail but not a circuit.
欧拉迹是恰好经过每条边一次的迹。欧拉回路（或欧拉环游）是起点与终点相同的欧拉迹。含有欧拉回路的图称为欧拉图，含有欧拉迹但不含欧拉回路的图称为半欧拉图。
Euler's Theorem: A connected undirected graph is Eulerian if and only if every vertex has even degree. It is semi-Eulerian if and only if exactly two vertices have odd degree (the trail starts at one odd vertex and ends at the other).
欧拉定理：一个连通无向图是欧拉图当且仅当每个顶点的度均为偶数。它是半欧拉图当且仅当恰有两个奇度顶点（迹从其中一个奇度顶点开始，于另一个结束）。
For directed graphs: an Eulerian circuit exists if and only if the graph is strongly connected (or the underlying undirected graph is connected) and degin(v) = degout(v) for every vertex v.
对于有向图：欧拉回路存在当且仅当图是强连通的（或底图连通）且每个顶点的入度等于出度。
A common exam task is to decide whether a given graph is Eulerian or to find an Eulerian trail using Fleury's algorithm or the Hierholzer algorithm.
常见考题包括判断给定图是否为欧拉图，或用 Fleury 算法或 Hierholzer 算法寻找欧拉迹。
6. Hamiltonian Graphs | 哈密顿图
A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle (or circuit) is a Hamiltonian path that returns to the starting vertex. A graph is Hamiltonian if it contains a Hamiltonian cycle. Unlike Eulerian graphs, there is no simple necessary and sufficient condition for Hamiltonicity; the problem is NP-complete in general.
哈密顿路径恰好访问每个顶点一次。哈密顿圈（或回路）是回到起点的哈密顿路径。含有哈密顿圈的图称为哈密顿图。与欧拉图不同，哈密顿性没有简单的充分必要条件，该问题在一般情况下是 NP 完全的。
Sufficient conditions include Dirac' e graph with n ≥ 3 vertices where every vertex has degree at least n/2 is Hamiltonian. Ore' es is Hamiltonian if for every pair of non-adjacent vertices u and v, deg(u) + deg(v) ≥ n.
充分条件包括狄拉克定理：n ≥ 3 的简单图中，若每个顶点的度至少为 n/2，则该图是哈密顿图。奥尔定理：n ≥ 3 的简单图中，若任意不相邻的顶点对 u 和 v 满足 deg(u) + deg(v) ≥ n，则图是哈密顿图。
Bipartite graphs with an odd number of vertices, or where the part sizes differ, cannot be Hamiltonian. The classic travelling salesman problem seeks the minimum-weight Hamiltonian cycle in a weighted graph.
具有奇数个顶点的二分图或两部分顶点数不等的二分图不可能是哈密顿图。经典旅行商问题即在赋权图中寻找最小权重的哈密顿圈。
7. Trees and Spanning Trees | 树与生成树
A tree is a connected acyclic graph. A forest is a disjoint union of trees. For a tree with n vertices, the number of edges is exactly n − 1. Any two vertices are connected by a unique path. Adding any edge creates exactly one cycle; removing any edge disconnects the tree.
树是连通无环图。森林是树的非交并集。具有 n 个顶点的树恰好有 n − 1 条边。任意两顶点间有唯一路径。添加任一边恰好产生一个圈；删除任一边则使树不连通。
A leaf is a vertex of degree 1. Every tree with at least 2 vertices has at least two leaves.
叶是度为 1 的顶点。任何至少有两个顶点的树至少有两片叶。
A spanning tree of a connected graph is a subgraph that is a tree and includes all vertices of the original graph. Every connected graph has at least one spanning tree. The number of spanning trees can be computed using Kirchhoff's matrix tree theorem (removing any row and column from the Laplacian matrix and taking the determinant).
连通图的生成树是一个包含所有顶点的树子图。每个连通图至少有一棵生成树。生成树的个数可利用基尔霍夫矩阵树定理（从拉普拉斯矩阵中删除任意一行一列后取行列式）求出。
8. Minimum Spanning Trees (Kruskal & Prim) | 最小生成树（Kruskal 与 Prim 算法）
In a weighted connected graph, a minimum spanning tree (MST) is a spanning tree with the smallest possible sum of edge weights. Finding an MST is a classic exam task using two greedy algorithms:
在赋权连通图中，最小生成树（MST）是边权总和最小的生成树。求最小生成树是经典考点，常用两种贪心算法：
Kruskal's Algorithm: Start with all vertices and no edges. Sort all edges by increasing weight. Iterate through the sorted list: add an edge to the growing forest if it does not create a cycle. Stop when n − 1 edges have been added. Use disjoint sets or simply check connectivity visually for small graphs.
Kruskal 算法：初始有所有顶点但没有边。将所有边按权重递增排序。依次考虑每条边：若加入后不产生圈，则将其加入森林。直到加入了 n − 1 条边为止。对于小图可以直接目视检查是否成圈。
Prim's Algorithm: Start with an arbitrary vertex and no edges. Repeatedly add the cheapest edge that connects a vertex already in the tree to a vertex not yet in the tree. Grow the tree one vertex at a time. A table or matrix form helps track temporary labels.
Prim 算法：从任一顶点开始，无边。重复添加连接树内顶点与树外顶点的最便宜边。一次添加一个顶点来扩展树。表格或矩阵有助于跟踪临时标号。
Both algorithms yield the same total weight if all edge weights are distinct; if there are ties, different MSTs (with same total weight) may be produced.
若所有边权互异，两种算法得出相同总权重；若有平局，可能产生不同的最小生成树（总权重相同）。
| Property | Kruskal | Prim |
|---|---|---|
| 数据结构 | 排序边 | 邻接矩阵/列表 |
| Edge selection | 全局最短 | 从树到非树顶点最短 |
| Cycle check | 显式排除成圈 | 自然无圈 |
9. Shortest Path Problem (Dijkstra's Algorithm) | 最短路径问题（Dijkstra 算法）
In a weighted graph with non-negative edge weights, Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices. The algorithm maintains a set of permanently labelled vertices with known shortest distances and repeatedly updates temporary labels for neighbouring vertices.
在边权非负的赋权图中，Dijkstra 算法可找出从单一源点到所有其他顶点的最短路径。算法维护一个已知最短距离的永久标号顶点集，并反复更新相邻顶点的临时标号。
t as current. (2) For the current vertex, consider its unvisited neighbours and compute tentative distances. If smaller than existing, update. (3) Mark the current vertex as visited. (4) Select the unvisited vertex with the smallest tentative distance as the new current. Repeat from step 2 until the target is reached or all vertices are visited.
步骤：(1) 起点标号为 0，其他顶点标号为 ∞。设起点为当前顶点。(2) 对于当前顶点的未访邻居，计算试探距离，若小于现有值则更新。(3) 标记当前顶点为已访。(4) 选择未访顶点中试探距离最小者作为新的当前顶点。重复步骤 2 直至到达目标或所有顶点均已访。
A table with columns: Vertex, Shortest distance from start, Previous vertex, and Visited? helps present the solution clearly in exams. Ensure you can trace back the path using the 'Previous vertex' column.
考试中建议用表格列出示：顶点、从起点出发的最短距离、前驱顶点、是否已访问。务必能利用“前驱顶点”列回溯路径。
Dijkstra's algorithm does not work with negative edge weights; for graphs with negative weights (rare in IB/CIE), other methods like Bellman-Ford are used.
Dijkstra 算法不适用于负权边；对于带负权边的图（在 IB/CIE 中罕见），需用 Bellman-Ford 等方法。
10. Graph Colouring | 图着色
rs needed for a proper colouring. Bipartite graphs have χ(G) = 2. Complete graphs have χ(Kn) = n. Cycles of even length are 2-colourable; odd cycles require 3 colours.
正常顶点着色为每个顶点分配一种颜色，使相邻顶点颜色不同。色数 χ(G) 是正常着色所需的最少颜色数。二分图的 χ(G) = 2。完全图 χ(Kn) = n。偶数长圈可用 2 种颜色；奇数长圈需要 3 种颜色。
The Four Colour Theorem states that any planar graph can be properly vertex-coloured with at most four colours. Although the proof is beyond syllabus, the statement may be referenced. For simple classes, upper bounds can be found using greedy colouring: order vertices decreasing by degree, then assign the first available colour not used by neighbours.
四色定理指出任何平面图都可用至多四种颜色进行正常顶点着色。尽管证明超出考纲，但其结论可能被引用。对于简单图类，可用贪心着色找到上界：按度降序排列顶点，然后为每个顶点分配其邻居未用的第一种可用颜色。
igning colours to edges such that incident edges have different colours. Chromatic index χ'(G) is the minimum number of edge colours. Vizing's theorem states that Δ(G) ≤ χ'(G) ≤ Δ(G) + 1, where Δ is the maximum degree. Bipartite graphs always have χ' = Δ (König's theorem).
边着色是为边分配颜色使关联边颜色不同。边色数 χ'(G) 是最少边颜色数。维津定理指出 Δ(G) ≤ χ'(G) ≤ Δ(G) + 1，其中 Δ 是最大度。二分图恒有 χ' = Δ（柯尼希定理）。
Scheduling problems and map colouring are frequent applications: vertices represent exams or regions, edges represent conflicts or shared borders.
排课问题与地图着色是常见应用：顶点代表考试或区域，边代表冲突或共享边界。
11. Matchings | 匹配
A matching in a graph is a set of edges without common vertices. A maximum matching contains the largest possible number of edges. A perfect matching covers every vertex of the graph (possible only if |V| is even). In bipartite graphs, Hall's marriage theorem provides a necessary and sufficient condition for the existence of a matching that covers all vertices of one part.
图的匹配是一组没有公共顶点的边。最大匹配包含尽可能多的边。完美匹配覆盖图的每一个顶点（仅当 |V| 为偶数时才可能）。在二分图中，霍尔婚姻定理给出了存在覆盖其中一部分所有顶点的匹配的充分必要条件。
Hall's condition: For a bipartite graph with parts X and Y, a matching that saturates X exists if and only if for every subset S ⊆ X, the number of neighbours |N(S)| in Y is at least |S|.
霍尔条件：对于划分 X 与 Y 的二分图，存在饱和 X 的匹配当且仅当对任意子集 S ⊆ X，其在 Y 中的邻居数 |N(S)| ≥ |S|。
An alternating path with respect to a matching M alternates between edges in M and not in M. An augmenting path is an alternating path that starts and ends at unmatched vertices. A matching is maximum if and only if there is no augmenting path. This is the basis of the Hungarian algorithm for finding maximum matchings in bipartite graphs, and the blossom algorithm for general graphs.
关于匹配 M 的增广路径是交替使用 M 中边和非 M 中边的路径。增广路径是以未匹配顶点为起点和终点的交替路径。一个匹配是最大的当且仅当不存在增广路径。这是二分图最大匹配匈牙利算法以及一般图开花算法的理论基础。
In weighted bipartite graphs, the Hungarian algorithm finds a maximum weight perfect matching, which is relevant to assignment problems.
在赋权二分图中，匈牙利算法可找出最大权完美匹配，与指派问题相关。
12. Exam Tips | 考试技巧
Master essential vocabulary: vertex (node), edge, loop, simple graph, degree, path, cycle, connected, Eulerian, Hamiltonian, tree, spanning tree, bipartite, matching. Many marks are lost by confusing definitions. Always check the degree sequence against the Handshaking Lemma before attempting construction questions.
掌握核心术语：顶点（节点）、边、环、简单图、度、路径、圈、连通、欧拉、哈密顿、树、生成树、二分图、匹配。很多失分源于混淆定义。在解答构造题之前，务必先用握手引理验算度序列。
For algorithm questions (Kruskal, Prim, Dijkstra), show your working step by step. Use a clear table for Dijkstra. Draw each intermediate stage if required. For Kruskal, list edges in sorted order and state why you accept or reject each.
算法题（Kruskal, Prim, Dijkstra）必须逐步展示过程。Dijkstra 要用清晰的表格。必要时画出每个中间阶段。Kruskal 则列出排序边，并说明接受或拒绝每条边的理由。
When proving a graph is not Eulerian, simply point out vertices of odd degree. For non-Hamiltonian, use common arguments: bipartite with uneven parts, existence of a cut-vertex, or violating necessary conditions like the closure not being complete.
证明非欧拉图时，直接指出奇度顶点即可。证明非哈密顿图可运用常用论证：两部分顶点数不等的二分图、割点的存在，或违反闭包不完全等必要条件。
Graph colouring questions often reduce to recognising a complete subgraph (lower bound) or applying greedy colouring (upper bound). If asked to find χ(G), give the exact value with justification.
图着色问题常归结为识别完全子图（下界）或应用贪心着色（上界）。若要求求出 χ(G)，应给出精确值并说明理由。
Be prepared to translate a real-world scenario into a graph model: cities as vertices, roads as edges, weights as distances or times. State clearly what each element represents.
能够将现实场景转化为图模型：城市为顶点，道路为边，权重为距离或时间。清晰说明每个元素的含义。
Finally, double-check arithmetic in algorithms. A single misstep in edge weight addition can propagate errors through the whole solution.
最后，反复检查算法中的算术。边权加总犯一个错误可能使整个解答随之出错。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图