Graph Theory Essentials for GCSE Maths | GCSE 数学：图论考点精讲

📚 Graph Theory Essentials for GCSE Maths | GCSE 数学：图论考点精讲

Graph theory is a fascinating branch of mathematics that studies networks of points connected by lines. While not always a core part of every GCSE specification, it frequently appears in problem-solving, decision maths modules, and extension papers. Understanding graphs can help you model real-world situations like delivery routes, social networks, and electrical circuits. This guide covers the key concepts you need to master graph theory at GCSE level, from basic definitions to algorithms like Kruskal’s and Dijkstra’s.

图论是数学中一个迷人的分支，研究由点与线连接而成的网络。虽然图论不总是每个GCSE大纲的核心内容，但它经常出现在问题解决、决策数学模块和拓展试卷中。理解图有助于你对现实世界的情况进行建模，例如配送路线、社交网络和电路。本指南涵盖你在GCSE阶段需要掌握的图论关键概念，从基本定义到克鲁斯卡尔算法和迪杰斯特拉算法。

1. What is a Graph? | 什么是图？

A graph is a collection of vertices (or nodes) linked by edges (or arcs). Unlike the coordinate graphs used in algebra, these graphs model connections — the positions of vertices are not fixed, and only the relationships matter. Graphs can be undirected, where edges have no direction, or directed, where each edge points from one vertex to another. Weighted graphs assign a number (weight) to each edge, often representing distance, time, or cost.

图是由顶点（或节点）通过边（或弧）连接而成的集合。与代数中使用的坐标图不同，这类图是对连接关系进行建模——顶点的位置不固定，只有关系才重要。图可以是无向的，即边没有方向；也可以是有向的，即每条边从一个顶点指向另一个顶点。加权图为每条边分配一个数字（权重），通常表示距离、时间或成本。

A simple graph has no loops (edges connecting a vertex to itself) and no multiple edges between the same pair of vertices. In GCSE problems, you will mostly work with simple, connected and weighted graphs.

简单图没有环（连接顶点自身的边），也不存在同一对顶点之间的多条边。在GCSE问题中，你接触的大多是简单、连通且加权的图。

2. Vertices, Edges and Degrees | 顶点、边和度数

The degree of a vertex is the number of edges incident to it. In a directed graph, we distinguish between in-degree and out-degree, but at GCSE level, we mostly consider undirected graphs and total degree. Loops, if present, count twice towards the degree.

顶点的度数是指与该顶点相连的边的条数。在有向图中，我们区分入度和出度，但在GCSE阶段，我们主要研究无向图和总度数。如果存在环，环在计算度数时按2计。

The Handshaking Lemma states that the sum of the degrees of all vertices is twice the number of edges. This holds because every edge contributes exactly 2 to the total degree sum.

握手引理指出，所有顶点的度数之和等于边数的两倍。这是因为每条边恰好为总度数贡献2。

sum of degrees = 2 × number of edges

A direct consequence is that the number of vertices with odd degree must be even. This is a common exam check — if you count three odd-degree vertices, you know a mistake has been made.

一个直接推论是，奇度顶点的个数必定为偶数。这是一个常见的考试检查点——如果数出三个奇度顶点，那一定是出错了。

Vertex	Degree
A	3
B	2
C	3
D	2

In the table above, vertices A and C have odd degree 3, which is an even count of two odd vertices. The Handshaking Lemma holds: sum = 3+2+3+2 = 10, and there are five edges.

在上表中，顶点A和C的度数都是奇数3，奇度顶点数为偶数2。握手引理成立：总和 = 3+2+3+2 = 10，共有5条边。

3. Paths and Circuits | 路径与回路

A path is a sequence of distinct vertices where each consecutive pair is joined by an edge. In a path, no vertex is repeated (except possibly the start and end if they are the same, but then it becomes a circuit). A circuit (or cycle) is a closed path where the start and end vertices coincide, and no other vertex is repeated.

路径是一系列互不相同的顶点，其中每一对相邻顶点之间都由边连接。在路径中，顶点不允许重复（除非起点和终点重合，但这成了回路）。回路（或环）是一条闭合路径，起点和终点相同，且其他顶点不重复。

In a simple graph, the length of a path is the number of edges it contains. The shortest path between two vertices is particularly important in applications. Graph theory problems often ask you to list all possible paths or find a path with certain properties.

在简单图中，路径的长度是指它所包含的边数。两个顶点之间的最短路径在应用中尤为重要。图论问题常要求列出所有可能的路径，或寻找具有特定性质的路径。

4. Connected and Disconnected Graphs | 连通图与非连通图

A graph is connected if there is a path between every pair of vertices. If a graph is not connected, it splits into connected components, and vertices in different components cannot be reached from one another. A bridge (or cut-edge) is an edge whose removal disconnects the graph.

如果任意两个顶点之间都存在路径，则称该图是连通的。如果图不连通，它会分裂成若干连通分量，不同分量中的顶点无法相互到达。桥（或割边）是指删除后会使图不再连通的那条边。

Connectedness is a vital property when modelling networks: for example, a road network must be connected so that you can travel between any two towns. When finding spanning trees or designing efficient networks, you often start from a connected graph.

连通性在建立网络模型时至关重要：例如，道路网络必须是连通的，这样你才能在任意两个城镇之间通行。在寻找生成树或设计高效网络时，你通常从一个连通图开始。

5. Trees and Spanning Trees | 树与生成树

A tree is a connected graph that contains no cycles. Trees have a very neat property: if a tree has V vertices, it always has exactly V − 1 edges. Adding any new edge to a tree creates a cycle; removing any edge disconnects it. A spanning tree of a connected graph is a subgraph that includes all the vertices and is itself a tree.

树是一种不含回路的连通图。树有一个非常整洁的性质：如果一棵树有V个顶点，那么它恰好有V − 1条边。向树添加任意新边都会产生回路；删除任意边都会使其不连通。连通图的生成树是包含所有顶点并且自身构成一棵树的子图。

Number of edges in a tree = V − 1

Finding a minimum spanning tree (MST) is a key problem: among all spanning trees of a weighted graph, which one has the smallest total weight? Two famous algorithms — Kruskal’s and Prim’s — solve this efficiently.

寻找最小生成树（MST）是一个关键问题：在加权图的所有生成树中，哪一棵的总权重最小？两种著名的算法——克鲁斯卡尔算法和普里姆算法——可以高效解决此问题。

6. Eulerian Graphs | 欧拉图

An Eulerian trail is a path that visits every edge of a graph exactly once. If the trail starts and ends at the same vertex, it is called an Eulerian circuit or Eulerian tour. A graph that possesses an Eulerian circuit is called an Eulerian graph. The historical Königsberg bridge problem asked whether one could walk across all seven bridges exactly once, leading Euler to discover the following conditions.

欧拉迹是一条恰好经过图中每条边一次的路径。如果该迹的起点和终点相同，则称为欧拉回路或欧拉环游。拥有欧拉回路的图称为欧拉图。历史上柯尼斯堡桥问题询问是否可以一次且仅一次走完七座桥，欧拉由此发现了如下条件。

For an undirected graph:

An Eulerian trail exists if and only if exactly 0 or 2 vertices have odd degree.
若且唯若恰好有0个或2个奇度顶点，则存在欧拉迹。
An Eulerian circuit exists if and only if every vertex has even degree.
若且唯若每个顶点的度数均为偶数，则存在欧拉回路。

These theorems give a quick way to check whether a graph can be drawn without lifting your pen and without retracing any edge.

这些定理提供了一种快速方法，用来检查一个图是否可以不抬笔且不重复任何边地一笔画出。

7. Hamiltonian Graphs | 哈密顿图

A Hamiltonian path visits each vertex exactly once, and a Hamiltonian circuit is a Hamiltonian path that returns to the starting vertex. Unlike Eulerian problems, there is no simple necessary and sufficient condition for Hamiltonicity. However, some sufficient conditions exist: for example, Ore’s theorem states that if for every pair of non-adjacent vertices the sum of their degrees is at least V, then the graph is Hamiltonian.

哈密顿路径恰好访问每个顶点一次，哈密顿回路是一条返回起点的哈密顿路径。与欧拉问题不同，哈密顿性没有简单的充要条件。但存在一些充分条件：例如，奥尔定理指出，如果每一对不相邻顶点的度数之和至少为V，则该图是哈密顿图。

At GCSE level, you may be asked to find a Hamiltonian cycle in a small graph by inspection, or to understand the difference between Eulerian and Hamiltonian concepts. The travelling salesman problem — finding the shortest Hamiltonian cycle — is a famous hard problem that builds on this idea.

在GCSE阶段，你可能会被要求通过观察找出小图中的一个哈密顿圈，或者理解欧拉概念与哈密顿概念的区别。旅行商问题——寻找最短的哈密顿圈——正是基于这一思想的著名难题。

8. Minimum Spanning Tree: Kruskal’s Algorithm | 最小生成树：克鲁斯卡尔算法

Kruskal’s algorithm builds a minimum spanning tree by repeatedly adding the cheapest edge that does not form a cycle. It is a greedy algorithm, and it works on any connected weighted graph.

克鲁斯卡尔算法通过反复添加不会构成回路的最便宜边来构建最小生成树。它是一种贪心算法，适用于任何连通加权图。

List all edges in order of increasing weight.
按权重从小到大的顺序列出所有边。
Select the edge with the smallest weight that does not create a cycle with the already selected edges.
选择权重最小且与已选边不构成回路的一条边。
Repeat step 2 until you have selected exactly V − 1 edges.
重复第2步，直到恰好选出V − 1条边。
The selected edges form a minimum spanning tree.
被选出的边构成一棵最小生成树。

To avoid cycles, you can shade or list the chosen edges and check whether adding the next edge would connect two vertices already in the same component. A table or a sorted list helps keep track.

为避免回路，你可以将已选边涂色或列表，并检查添加下一条边是否会连通两个已在同一连通分量中的顶点。使用表格或排序清单有助于追踪。

9. Minimum Spanning Tree: Prim’s Algorithm | 最小生成树：普里姆算法

Prim’s algorithm takes a different approach: it grows a tree from an arbitrary starting vertex by always adding the cheapest edge that connects the current tree to a vertex not yet in the tree.

普里姆算法采用不同的方法：从任意一个起始顶点出发，逐步生长一棵树，每次添加一条连接当前树与尚未加入树的顶点的最便宜边。

Choose any vertex to start. Mark it as in the tree.
任选一个顶点作为起点，将其标记为已加入树中。
Look at all edges connecting the tree to vertices outside the tree. Pick the edge with the smallest weight.
考察连接树与外部顶点的所有边，选出权重最小的一条。
Add that edge and the new vertex to the tree.
将该边和新的顶点加入树中。
Repeat steps 2–3 until all vertices are in the tree.
重复第2至3步，直到所有顶点都加入树中。

Prim’s algorithm is often presented using a table or matrix, especially when the graph is dense. Both Kruskal’s and Prim’s algorithms always produce a correct minimum spanning tree.

普里姆算法经常借助表格或矩阵来呈现，尤其当图较为稠密时。克鲁斯卡尔算法和普里姆算法都能保证给出正确的最小生成树。

10. Shortest Path: Dijkstra’s Algorithm | 最短路径：迪杰斯特拉算法

Dijkstra’s algorithm finds the shortest path from a chosen source vertex to all other vertices in a weighted graph with non-negative weights. It uses temporary labels (distances) that get updated and eventually become permanent.

迪杰斯特拉算法可以在权重非负的加权图中，找到从选定的源顶点到其他所有顶点的最短路径。它使用临时标签（距离），这些标签会被更新并最终固定为永久标签。

Assign the source vertex a permanent label of 0 and all other vertices temporary labels of ∞.
给源顶点分配永久标签0，其他所有顶点分配临时标签∞。
From the most recently permanently labelled vertex, update the temporary labels of its unvisited neighbours by taking the sum of the permanent label at the current vertex and the edge weight. If this sum is smaller than the existing temporary label, replace it.
从最新获得永久标签的顶点出发，更新其未访问邻居的临时标签：计算当前顶点的永久标签与边权重之和；若该和小于现有临时标签，则替换之。
Find the vertex with the smallest temporary label, make it permanent, and repeat step 2 from this vertex.
找出临时标签最小的顶点，将其设为永久，并从该顶点重复第2步。
Continue until all vertices have permanent labels. Then you can read off the shortest path backwards from the destination.
持续进行直到所有顶点拥有永久标签。然后你就可以从终点反向读出最短路径。

A common exam question asks you to fill in a table showing the order of permanent labels and the route. Be methodical, and always record the vertex from which each label was updated.

常见的考题要求填写一个表格，展示永久标签的顺序和路径。务必有条不紊，并始终记录每个标签是从哪个顶点更新而来的。

11. Applications and Exam Tips | 应用与应试技巧

Graph theory is not just abstract; it powers GPS navigation, internet routing, and circuit board design. In GCSE exams, questions often embed graphs in real-world contexts — road maps, cable laying, or delivery rounds. Be sure to label your working clearly, especially when applying algorithms step by step.

图论并非纯抽象；它支撑着GPS导航、互联网路由和电路板设计。在GCSE考试中，题目常将图嵌入真实情境——公路地图、电缆铺设或投递路线。请务必清晰标注解答步骤，特别是在逐步应用算法时。

Common pitfalls include:

Forgetting to check for cycles in Kruskal’s algorithm.
在克鲁斯卡尔算法中忘记检查回路。
Updating temporary labels incorrectly in Dijkstra’s algorithm.
在迪杰斯特拉算法中错误地更新临时标签。
Misidentifying Eulerian conditions — not all odd-degree graphs lack an Eulerian trail (exactly two odd degrees give a trail).
错误判断欧拉条件——并非所有含有奇度顶点的图都没有欧拉迹（恰好两个奇度顶点时存在迹）。
Confusing Hamiltonian cycles with Eulerian circuits.
将哈密顿圈与欧拉回路混淆。

When presenting your solution, show a trace of the algorithm: list sorted edges for Kruskal, maintain a table for Prim or Dijkstra, and state the final tree or path clearly. Practice with plenty of past paper questions to build confidence.

在呈现解答时，要展示算法的跟踪过程：为克鲁斯卡尔列出排序后的边，为普里姆或迪杰斯特拉维护表格，并清晰地写出最终的树或路径。通过大量历年真题练习，建立自信。

Published by TutorHao | Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Graph Theory Essentials for GCSE Maths | GCSE 数学：图论考点精讲