📚 Graph Theory | 图论
Graph theory is a branch of mathematics that studies the properties of graphs – structures used to model pairwise relations between objects. In Edexcel A-Level Decision Mathematics, graph theory provides the foundation for solving real-world problems such as route planning, network design, and resource allocation. You will learn to represent situations using vertices and edges, classify different types of graphs, and apply efficient algorithms to find optimal connections and shortest paths.
图论是数学的一个分支，研究图的性质——图是用来给对象之间成对关系建模的结构。在爱德思 A-Level 决策数学中，图论为解决路径规划、网络设计和资源配置等现实问题提供了基础。你将学习用顶点和边表示情景，区分不同类型的图，并运用高效算法寻找最优连接与最短路径。
1. Introduction to Graphs | 图论导论
A graph consists of a set of points called vertices (or nodes) and a set of lines called edges that connect pairs of vertices. Graphs are abstract representations of networks: roads between towns, cables between computers, or relationships in a social network can all be modelled as graphs. The way the edges link vertices captures only the connectivity, not the geography or scale.
一个图由一组称为顶点（或节点）的点，以及一组称为边的线段组成，每条边连接一对顶点。图是网络的抽象表示：城镇之间的公路、计算机之间的电缆或社交网络中的人际关系都可以建模为图。边连接顶点的方式仅仅反映连通关系，而不涉及地理位置或尺度。
2. Basic Terminology | 基本术语
A vertex can have a degree – the number of edges incident to it. A loop is an edge that starts and ends at the same vertex, and multiple edges are two or more edges connecting the same pair of vertices. Two vertices are adjacent if there is an edge joining them. A simple graph has no loops and no multiple edges, while a general graph may allow them. The order of a graph is the number of vertices, and the size is the number of edges.
顶点具有度——即与其相连的边数。一条起点和终点为同一个顶点的边称为环，多重边是指连接同一对顶点的两条或以上的边。如果有一条边连接两个顶点，它们称为相邻。简单图不含环也没有多重边，而一般图可能包含它们。图的阶指顶点数，规模指边数。
A subgraph is formed by selecting a subset of the vertices and edges from the original graph, where the chosen edges must only connect vertices in the subset. A weighted graph assigns a numerical label to each edge, representing cost, distance, or time. In Edexcel questions, weights are usually real positive numbers.
子图是从原图中选取一部分顶点和边构成的图，其中选取的边只能连接所选子集中的顶点。加权图给每条边赋予一个数值标签，表示成本、距离或时间。在爱德思考题中，权重通常是正实数。
3. Types of Graphs | 图的类型
Graphs can be directed or undirected. In an undirected graph, edges have no orientation – travelling from A to B is the same as travelling from B to A. In a directed graph (digraph), each edge has a direction shown by arrows. A complete graph on n vertices, denoted Kₙ, has every pair of distinct vertices joined by exactly one edge. A bipartite graph is one whose vertex set can be split into two disjoint sets so that every edge joins a vertex from the first set to one from the second. A tree is a connected graph with no cycles.
图可以是有向的或无向的。在无向图中，边没有方向——从 A 走到 B 与从 B 走到 A 是一样的。在有向图（有向图）中，每条边由箭头表明方向。包含 n 个顶点的完全图记作 Kₙ，其中每一对不同顶点之间恰有一条边。二部图是指顶点集可以分成两个不相交的集合，且每条边都连接第一个集合的一个顶点与第二个集合的一个顶点。树是一种没有圈的连通图。
Another special type is a Eulerian graph, where all vertices have even degree, allowing a trail that uses every edge exactly once. A semi‑Eulerian graph has exactly two vertices of odd degree and permits a trail that uses every edge exactly once, starting at one odd vertex and finishing at the other.
另一种特殊类型是欧拉图，图中所有顶点的度都为偶数，这样就能够找到一条恰好使用每条边一次的路径。半欧拉图恰好有两个奇度顶点，可以找到一条恰好使用每条边一次的路径，起点和终点分别为这两个奇度顶点。
4. Paths, Cycles and Walks | 路径、圈与漫步
A walk is a sequence of vertices where each consecutive pair are adjacent; edges and vertices may be revisited. A trail is a walk with no repeated edges. A path is a trail with no repeated vertices except possibly the start and end. A cycle is a closed path where the only repeated vertex is the first and last. Understanding these distinctions is crucial for algorithm design, especially in shortest-path and inspection problems.
漫步是顶点的一个序列，其中每一对相邻顶点都是邻接的；边和顶点可以重复访问。迹是没有重复边的漫步。路径是没有重复顶点的迹（起点和终点可能相同除外）。圈是闭合的路径，仅有的重复顶点是首尾顶点。理解这些区别对算法设计至关重要，尤其是在最短路径和路线检查问题中。
A Hamiltonian path visits every vertex exactly once, while a Hamiltonian cycle is a Hamiltonian path that returns to the start. These concepts appear in decision mathematics but are less common in Edexcel D1 algorithms; however, you must recognise them.
哈密顿路径恰好访问每个顶点一次，哈密顿圈则是回到起点的哈密顿路径。这些概念在决策数学中会出现，但在爱德思 D1 算法中不太常见；不过你必须能辨认它们。
5. Connectedness and Components | 连通性与连通分量
A graph is connected if there is a path between every pair of vertices. If the graph is disconnected, its connected components are the maximal connected subgraphs. In a directed graph, a strongly connected component means you can travel from any vertex to any other within that part following the direction of edges. Weakly connected simply means the underlying undirected graph is connected.
如果在任意一对顶点之间都存在一条路径，则该图是连通的。若图不连通，其连通分量就是极大连通子图。在有向图中，强连通分量意味着在该部分内部你可以沿着边的方向从任意顶点到达任意其他顶点。弱连通仅意味着对应的无向底图是连通的。
Connectedness is often tested with practical networks: you might be asked to determine whether adding or removing an edge makes the graph disconnected, or to identify the minimum number of edges needed to connect all vertices.
连通性经常结合实际网络进行考查：可能要求你判断添加或删除一条边是否会使图不连通，或者找出连接所有顶点所需的最少边数。
6. Trees and Properties of Trees | 树及其性质
A tree is a connected simple graph with no cycles. Trees have exactly n − 1 edges, where n is the number of vertices. Removing any edge from a tree disconnects it, and adding any new edge creates exactly one cycle. A tree is minimally connected. These properties make trees ideal for network backbones where redundancy is avoided.
树是连通的无环简单图。树恰好有 n − 1 条边，其中 n 为顶点数。从树中移除任意一条边会使它不连通，而添加任意一条新边则恰好产生一个圈。树是最小连通的。这些性质使树成为避免冗余的网络骨干的理想模型。
In Edexcel D1, you will often be given a table of distances and asked to find a spanning tree that minimises total weight. Recognising when a subgraph is a tree helps verify the output of algorithms like Kruskal’s.
在爱德思 D1 中，你常常会拿到一张距离表，并被要求找出使总权最小的生成树。识别一个子图是否为树有助于验证像 Kruskal 那样的算法的输出。
7. Spanning Trees | 生成树
A spanning tree of a connected graph is a subgraph that includes all the vertices and is a tree. Every connected graph has at least one spanning tree. In weighted graphs, we are usually interested in the minimum spanning tree (MST) – the spanning tree with the smallest total edge weight. A graph may have several different MSTs if edges share the same weight.
连通图的生成树是包含所有顶点的一棵树的子图。每个连通图都至少有一棵生成树。在加权图中，我们通常对最小生成树 (MST) 感兴趣——即总边权最小的生成树。如果多条边的权值相同，一个图可能有多个不同的最小生成树。
Spanning trees are used to minimise the cost of connecting all nodes in a network, such as laying pipelines or cables. Both Kruskal’s and Prim’s algorithms guarantee an MST for a connected weighted graph.
生成树被用来最小化连接网络中所有节点的成本，例如铺设管道或电缆。Kruskal 算法和 Prim 算法都能为一幅连通加权图确保找到一棵最小生成树。
8. Minimum Spanning Trees: Kruskal’s Algorithm | 最小生成树：Kruskal 算法
Kruskal’s algorithm builds an MST by considering the edges in ascending order of weight. You list all edges sorted by weight, then start with an empty graph and add edges one by one, skipping any that would create a cycle. Continue until you have (n − 1) edges. The process requires careful listing and cycle-checking, often done by shading vertices or showing components.
Kruskal 算法通过按权重递增顺序处理边来构建最小生成树。首先将所有边按权重排序制成列表，然后从空图开始，逐一添加边，跳过任何会形成圈的边。继续直到获得 n − 1 条边。这个过程需要仔细列出边并检查圈，通常通过给顶点涂色或标明连通分量来完成。
In an exam, you will be given a network with labelled edges. Show the sorted list, draw the fragmented stages, and clearly indicate rejected edges. The final tree must be total weight stated. The algorithm is simple but requires accurate sorting.
在考试中，会给你一个带有标记边的网络。展示排序列表，画出分段添加的阶段图，并清楚地标出被拒绝的边。最终树必须标出总权。该算法虽简单，但要求准确的排序。
9. Minimum Spanning Trees: Prim’s Algorithm | 最小生成树：Prim 算法
Prim’s algorithm grows an MST from a chosen starting vertex. You maintain two sets: vertices in the tree and vertices not yet connected. At each step, select the least weight edge that joins a vertex in the tree to one not in the tree, then move that new vertex into the tree. Repeat until all vertices are included. A table or matrix format is often used to keep track of distances, especially when a distance matrix is given.
Prim 算法从一个选定的起始顶点出发逐渐生成最小生成树。你需要维护两个集合：树中的顶点和尚未连接的顶点。每一步选择连接树内顶点与树外顶点的最小权重边，然后将新顶点移入树中。重复直到所有顶点都被包含。通常使用表格或矩阵格式来记录距离，尤其在给出距离矩阵的情况下。
When the graph is represented by a distance matrix, Prim’s algorithm using the matrix method involves selecting a start, crossing out its row and labelling its column, then choosing the smallest entry in labelled columns, and so on. Edexcel accepts either the graphical or the matrix approach, so practise both.
当用距离矩阵表示图时，使用矩阵法的 Prim 算法包括选一个起点、划掉其所在行并标记其列，然后在已标记列中选最小项，依此类推。爱德思考试接受图形法或矩阵法，因此两种都要练习。
10. Shortest Path: Dijkstra’s Algorithm | 最短路径：Dijkstra 算法
Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a non‑ ce with value 0 and all others as infinity. At each step, choose the unvisited vertex with the smallest working value, update its final value, and then update working values for its neighbours using the formula: new working = min(old working, final(vertex) + edge weight).
Dijkstra 算法用于在所有权重非负的图中寻找从源顶点到其他所有顶点的最短路径。通过表格操作，你要维护包括标签次序、工作值和最终值的盒子。将源顶点初始化为 0，其他设为无穷大。每一步选择具有最小工作值的未访问顶点，更新其最终值，然后使用公式更新其邻居的工作值：新工作值 = min(原工作值, 最终值(顶点) + 边权)。
Continue until the destination vertex receives a final label, or all vertices are finalised. To retrieve the route, backtrack from the destination using the recorded working values to identify the preceding vertex at each stage. You must present your answer as a full table, the shortest distance, and the route explicitly.
不断重复，直到目标顶点获得最终标签，或所有顶点都被最终化。为找回路径，从终点回溯，利用记录的工作值识别每一阶段的前驱顶点。你必须将答案以完整表格、最短距离和明确路线呈现。
Typical table headings include: Vertex, Order of labelling, Final value, and working values for each neighbour. Ensure neat presentation – marks are awarded for accurate working and correctly boxed final values.
典型的表格标题包括：顶点、标签次序、最终值，以及各个邻居的工作值。务必保持卷面整洁——准确的运算和正确打框的最终值才能拿到分数。
11. Route Inspection Problem (Chinese Postman Problem) | 路线检查问题（中国邮差问题）
The route inspection problem asks for the shortest closed walk that traverses every edge at least once. If the graph is Eulerian (all vertices even degree), the optimum route is simply any Eulerian trail, with total length equal to the sum of all edge weights. If the graph is semi‑Eulerian (exactly two odd vertices), you must start at one odd vertex and finish at the other, covering each edge exactly once.
路线检查问题要求找出至少遍历每条边一次的最短闭合漫步。如果图是欧拉图（所有顶点度均为偶数），最优路线就是任意一条欧拉路径，总长度等于所有边权之和。如果图是半欧拉图（恰好两个奇度顶点），你必须从一个奇度顶点出发，在另一个奇度顶点结束，恰好每条边遍历一次。
For graphs with more than two odd vertices, you must pair up the odd vertices and duplicate edges along the shortest paths between those pairs, so that the augmented graph becomes Eulerian. The algorithm involves identifying all odd vertices, finding shortest distances between every pair (using Dijkstra or by inspection), then applying a minimum weight perfect matching to select which pairs to duplicate. This is the most challenging part of the D1 specification and requires careful logical reasoning.
对于超过两个奇度顶点的图，你必须将奇度顶点两两配对，并沿这些配对之间的最短路径复制边，从而使增广图成为欧拉图。算法包括：找出所有奇度顶点，求出每对之间的最短距离（可以用 Dijkstra 或直接判断），然后应用最小权重完美匹配来选择要复制的配对。这是 D1 考纲中最具挑战性的部分，需要仔细的逻辑推理。
In an exam, you will likely be asked to state the odd vertices, determine the pairings of minimal extra weight, and then give the total length of the optimal route, which is the sum of original weights plus the duplicated edges.
考试中，很可能要求你写出奇度顶点，确定使额外权最小的配对方式，然后给出最优路线的总长度，即原有权重之和加上复制边的权重。
12. Applying Graph Theory | 图论应用
Graph theory is not only abstract; it directly models real systems. Postal delivery rounds, refuse collection, school bus routing, network cabling, circuit board design, and even scheduling of tasks can be optimised using the algorithms you learn. Recognising when to use a minimal spanning tree rather than a shortest path, or when the Chinese postman problem applies, is a key skill.
图论不仅仅是抽象的；它直接对真实系统进行建模。邮递路线、垃圾回收、校车路线安排、网络布线、电路板设计，甚至是任务调度都可以用你所学的算法进行优化。识别何时使用最小生成树而不是最短路径，或者何时适用中国邮差问题，是一项关键技能。
On Edexcel papers, questions often involve interpreting the context, reducing a scenario to vertices and edges, assigning appropriate weights, and then selecting and executing the correct algorithm. Clear labelling, methodical tables, and explicit conclusions are essential for full marks. Graph theory equips you with powerful optimisation tools that extend far beyond the A-level classroom.
在爱德思试卷中，题目常常涉及解读情境，将场景简化为顶点和边，赋予合适的权重，然后选择并执行正确的算法。清晰的标注、有条理的表格和明确的结论是获得满分的必要条件。图论为你提供了强大的优化工具，其应用远不止于 A-Level 课堂。
Published by TutorHao | Decision Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图