📚 IGCSE Mathematics: Graph Theory Key Concepts | IGCSE 数学：图论 考点精讲
Graph theory is a fascinating area of IGCSE Mathematics that models relationships and networks using vertices and edges. Mastering the key concepts – from tree algorithms to shortest paths and route inspection – will give you the confidence to tackle exam questions methodically. This revision guide covers all essential topics, with clear explanations, step-by-step algorithms, and practical tips.
图论是 IGCSE 数学中一个迷人的领域，它使用顶点和边来对关系与网络进行建模。掌握核心概念——从树的算法到最短路径和路线检查——将使你有信心有条理地应对考试问题。本复习指南涵盖了所有必考要点，并配有清晰的解释、分步算法和实用技巧。
1. Basic Terminology of Graphs | 图的基本术语
A graph consists of vertices (or nodes) and edges (lines that connect pairs of vertices). If the edges have numbers associated with them, called weights, the diagram is called a network. Graphs can be used to represent roads, pipelines, computer connections, and many other real-world systems.
图由顶点（或节点）和边（连接顶点对的线）组成。如果边带有数值（称为权重），则该图被称为网络。图可用于表示道路、管道、计算机连接以及许多其他现实世界中的系统。
2. Vertices, Edges and Degree | 顶点、边与度
The degree (or valency) of a vertex is the number of edges incident to it. A loop (an edge that connects a vertex to itself) contributes 2 to the degree. In a simple graph there are no loops and no multiple edges between the same pair of vertices.
顶点的度（或价）是指与该顶点相连的边的数目。环（连接顶点自身的边）对度的贡献为 2。在简单图中，既没有环，也没有在相同顶点对之间的多重边。
3. Handshaking Lemma | 握手引理
mediate consequence is that any graph must have an even number of vertices with odd degree.
握手引理指出，图中所有顶点的度数之和等于边数的两倍。用符号表示即 ∑ deg(v) = 2E。一个直接的推论是，任何图中度数为奇数的顶点个数必定为偶数。
4. Types of Graphs | 图的类型
Important types of graphs you will meet include: a connected graph (there is a path between every pair of vertices); a tree (a connected graph with no cycles); a complete graph Kn (every pair of vertices is connected by exactly one edge); and a directed graph or digraph (edges have directions, indicated by arrows).
你会遇到的重要图类型包括：连通图（每对顶点之间都存在路径）；树（一个无环的连通图）；完全图 Kn（每对顶点之间恰好由一条边相连）；以及有向图（边具有方向，用箭头表示）。
5. Trees and Spanning Trees | 树与生成树
A tree is a connected graph that contains no cycles. A spanning tree of a connected graph is a subgraph that includes all the vertices and is also a tree. A network may have many different spanning trees; the one with the smallest total weight is called a minimum spanning tree (MST).
树是一个不含圈的连通图。一个连通图的生成树是一个包含所有顶点的子图，并且自身也是一棵树。一个网络可以有许多不同的生成树；总权重最小的那棵被称为最小生成树 (MST)。
6. Minimum Spanning Trees – Kruskal's Algorithm | 最小生成树 – Kruskal 算法
Kruskal's algorithm builds an MST by repeatedly adding the unused edge with the smallest weight, provided it does not create a cycle. Steps: [1] List all edges in ascending order of weight. [2] Select the edge with the smallest weight that does not form a cycle. [3] Repeat until all vertices are connected (a tree with (V-1) edges has been formed).
Kruskal 算法通过反复添加权重最小且未使用的边来构建最小生成树，条件是添加后不形成圈。步骤：[1] 将所有边按权重升序排列。 [2] 选择不形成圈的权重最小的边。 [3] 重复直到所有顶点都被连接（形成一棵具有 (V-1) 条边的树）。
7. Minimum Spanning Trees – Prim's Algorithm | 最小生成树 – Prim 算法
Prim's algorithm grows an MST from a starting vertex. Steps: [1] Choose any starting vertex. [2] Consider all edges connecting the current tree to vertices not yet in the tree; select the edge with the smallest weight. [3] Add that edge and the new vertex to the tree. [4] Repeat until all vertices are included. Prim's algorithm is especially useful when the network is dense, and it can be implemented efficiently using a table.
Prim 算法从一个起始顶点开始逐步生长出最小生成树。步骤：[1] 选择任意一个起始顶点。 [2] 考虑当前树连接到尚未在树中的顶点的所有边；选择权重最小的边。 [3] 将该边和新顶点加入树中。 [4] 重复直到所有顶点都被包含。当网络稠密时 Prim 算法特别有用，并且可以用表格高效实现。
8. Dijkstra's Algorithm for Shortest Path | 最短路径 Dijkstra 算法
Dijkstra's algorithm finds the shortest path from a start vertex to all other vertices in a weighted graph with non-negative weights. It works by assigning temporary labels showing the shortest distance found so far, and then making the smallest temporary label permanent at each stage. Steps: [1] Label the start vertex with permanent label 0. [2] For all vertices directly reachable from the latest permanently labelled vertex, update their temporary labels if a shorter route is found. [3] Choose the smallest temporary label and make it permanent. [4] Repeat until the destination vertex obtains a permanent label. You can then trace back to find the route.
Dijkstra 算法用于在具有非负权重的加权图中找出从起始顶点到所有其他顶点的最短路径。它的工作原理是：用临时标签标出到目前为止找到的最短距离，然后在每个阶段将最小的临时标签变为永久标签。步骤：[1] 给起始顶点标上永久标签 0。 [2] 对于从最新获得永久标签的顶点可以直接到达的所有顶点，如果找到了更短的路径，就更新它们的临时标签。 [3] 选择最小的临时标签并将其变为永久标签。 [4] 重复直到目标顶点获得永久标签。然后你可以回溯找出路径。
9. Route Inspection Problem (Chinese Postman) | 路线检查问题（中国邮递员问题）
The route inspection problem asks for the shortest closed walk that traverses every edge at least once. If every vertex has even degree, the network is Eulerian and any Eulerian circuit has length equal to the sum of all edge weights. If there are odd-degree vertices, you must repeat some edges. Identify all odd vertices, find the shortest paths between each pair of them, and then pair them up so that the total extra distance added is minimised. The total route length is the sum of all edge weights plus the total length of repeated paths.
路线检查问题要求找出至少遍历每条边一次的最短闭途径。如果每个顶点的度数都是偶数，网络是欧拉图，任何欧拉回路的长度就等于所有边权重之和。如果存在奇度顶点，则必须重复某些边。找出所有奇度顶点，确定每对奇度顶点之间的最短路径，然后将它们配对，使得增加的额外总距离最小。总路线长度等于所有边权重之和加上重复路径的总长度。
10. Travelling Salesman Problem – Upper and Lower Bounds | 旅行商问题 – 上界与下界
The travelling salesman problem (TSP) seeks the shortest Hamiltonian cycle (visiting every vertex exactly once and returning to the start). Since checking all possible tours is impractical for larger networks, we find upper and lower bounds. An upper bound is the length of any valid tour (e.g. from the nearest neighbour algorithm). A lower bound is found by deleting a vertex, finding the MST of the remaining network, and adding the weights of the two shortest edges from the deleted vertex to the MST. The optimum tour lies between these bounds.
旅行商问题 (TSP) 寻找最短的哈密顿回路（访问每个顶点恰好一次并返回起点）。由于对于较大的网络检查所有可能的巡回路线是不切实际的，我们会找出上界和下界。上界是任意一条可行巡回路线的长度（例如由最近邻算法得到的路线）。下界通过以下方法求得：删除一个顶点，找出剩余网络的最小生成树，然后将从被删除顶点出发的两条最短边的权重加到该最小生成树上。最优回路的长度就介于这些界限之间。
11. Nearest Neighbour Algorithm | 最近邻算法
The nearest neighbour algorithm quickly produces an upper bound for the TSP. Steps: [1] Choose a starting vertex. [2] Move to the nearest unvisited vertex. [3] Repeat step 2 until all vertices have been visited. [4] Return directly to the start vertex. The total weight of this tour is an upper bound. For a better upper bound, you can repeat the algorithm from different starting vertices and take the smallest total.
最近邻算法可以快速得出旅行商问题的一个上界。步骤：[1] 选择一个起始顶点。 [2] 移动到最近的未访问顶点。 [3] 重复步骤 2 直到所有顶点都已访问。 [4] 直接返回起始顶点。该巡回路线的总权重就是一个上界。为了得到更好的上界，你可以从不同的起始顶点重复该算法，并取最小的总权重。
12. Tips for Exam Success | 考试技巧
Always show your working clearly: list edges in order for Kruskal, draw a table for Prim, and carefully update boxes for Dijkstra. When solving a route inspection problem, highlight the odd vertices and clearly state which paths are being repeated. For TSP, remember that the nearest neighbour algorithm gives an upper bound, while the deleted-vertex MST method provides a lower bound. Check your arithmetic and ensure that the number of edges in a spanning tree is V − 1. Finally, practise past paper questions to become fluent in all these algorithms.
务必清晰地展示解题过程：对于 Kruskal 算法要按顺序列出边，对于 Prim 算法要画出表格，对于 Dijkstra 算法要仔细更新方格。在解决路线检查问题时，要标出奇度顶点并清楚地说明哪些路径被重复了。对于旅行商问题，请记住最近邻算法给出的是上界，而删除顶点最小生成树法给出的是下界。检查你的算术，并确保生成树中的边数为 V − 1。最后，练习历年真题以熟练掌握所有这些算法。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图