IGCSE CIE Mathematics: Graph Theory Essentials | IGCSE CIE 数学：图论考点精讲

📚 IGCSE CIE Mathematics: Graph Theory Essentials | IGCSE CIE 数学：图论考点精讲

In IGCSE CIE Mathematics, graph theory appears as a fascinating applied topic that bridges abstract reasoning and real-world problem solving. This article covers the essential concepts, definitions, and algorithms you need to master, including vertices, edges, Eulerian and Hamiltonian paths, trees, spanning trees, and the famous Travelling Salesman Problem.

在 IGCSE CIE 数学中，图论是一门迷人的应用课题，连接着抽象推理与现实世界的解决问题。本文涵盖了你需要掌握的基本概念、定义和算法，包括顶点、边、欧拉路径与哈密顿路径、树、生成树以及著名的旅行商问题。

1. Basic Terminology: Vertices, Edges, and Degree | 基本术语：顶点、边与度

A graph consists of vertices (or nodes) connected by edges (or arcs). The degree of a vertex is the number of edges incident to it. Understanding these building blocks is the first step in mastering graph theory.

图由顶点（或节点）通过边（或弧）连接而成。顶点的度是指与该顶点相连的边的数量。理解这些基本构件是掌握图论的第一步。

Graphs can be simple (no loops or multiple edges) or complex. In IGCSE, we mostly deal with simple graphs.
图可以是简单的（没有环或多重边）或复杂的。在 IGCSE 中，我们主要处理简单图。

The Handshaking Lemma states that the sum of the degrees of all vertices equals twice the number of edges. This is a fundamental property often tested in exams.
握手引理指出，所有顶点的度数之和等于边数的两倍。这是一个常考的基本性质。

2. Types of Graphs: Undirected, Directed, and Connected | 图的类型：无向图、有向图与连通图

Edges can be undirected (no arrow) or directed (one-way arrow). A graph is connected if there is a path between every pair of vertices. Disconnected graphs have at least two vertices with no path between them.

边可以是无向的（无箭头）或有向的（单向箭头）。如果每对顶点之间都存在一条路径，则图是连通的。非连通图至少有两个顶点之间没有路径。

Weighted graphs assign a numerical value (weight) to each edge, representing distance, cost, or time. Many optimisation problems use weighted graphs.
加权图为每条边分配一个数值（权重），代表距离、成本或时间。许多优化问题都使用加权图。

A complete graph has every pair of distinct vertices connected by a unique edge. It is denoted by Kₙ where n is the number of vertices.
完全图的每对不同顶点都由一条唯一边连接。它用 Kₙ 表示，其中 n 是顶点数。

3. Eulerian Paths and Circuits | 欧拉路径与欧拉回路

An Eulerian path (or trail) visits every edge exactly once, while an Eulerian circuit (or cycle) starts and ends at the same vertex. For an undirected graph, exactly zero or two vertices of odd degree are needed for an Eulerian path; zero odd-degree vertices yield an Eulerian circuit.

欧拉路径（或迹）恰好经过每条边一次，而欧拉回路（或圈）起点和终点相同。对于无向图，欧拉路径需要恰好有 0 个或 2 个奇度顶点；0 个奇度顶点会形成欧拉回路。

A famous example is the Königsberg Bridge problem. The landmasses are vertices, and bridges are edges. Since all four vertices have odd degree, no Eulerian path exists.
著名的例子是柯尼斯堡桥问题。陆地是顶点，桥是边。由于所有四个顶点都是奇度，因此不存在欧拉路径。

To determine if a graph has an Eulerian circuit, simply list the degree of each vertex and check for odd counts.
要判断图是否有欧拉回路，只需列出每个顶点的度，检查奇度个数。

4. Hamiltonian Paths and Cycles | 哈密顿路径与哈密顿圈

A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle does the same but returns to the starting vertex. Unlike Eulerian problems, there is no simple degree condition for Hamiltonian graphs – the problem is generally much harder.

哈密顿路径恰好经过每个顶点一次；哈密顿圈同样如此但会返回起点。与欧拉问题不同，哈密顿图没有简单的度条件——这个问题通常困难得多。

For small graphs, you can use trial and improvement or systematic listing. IGCSE questions often ask you to find a Hamiltonian cycle in a given weighted graph.
对于小图，你可以使用试错法或系统列举。IGCSE 题目经常要求你在给定的加权图中找到一个哈密顿圈。

5. Trees and Their Properties | 树及其性质

A tree is a connected graph with no cycles. It has exactly n−1 edges if there are n vertices. Trees are used to model hierarchical relationships, such as organisation charts or file systems.

树是一种无圈的连通图。如果有 n 个顶点，则恰好有 n−1 条边。树用于模拟层次关系，例如组织架构图或文件系统。

A spanning tree of a graph is a subgraph that includes all vertices and is a tree. Every connected graph has at least one spanning tree.
图的生成树是一个包含所有顶点的子图，并且是一棵树。每个连通图至少有一个生成树。

6. Minimum Spanning Tree: Kruskal’s Algorithm | 最小生成树：Kruskal 算法

Kruskal’s algorithm builds a minimum spanning tree by repeatedly adding the shortest edge that does not create a cycle. This is a standard IGCSE examination technique, often presented in a table of edges with weights.

Kruskal 算法通过反复添加不形成环的最短边来构建最小生成树。这是 IGCSE 考试中的标准技术，通常以边和权重的表格形式出现。

Steps: 1) List all edges in ascending order of weight. 2) Select the smallest edge that connects two different trees (i.e. does not create a cycle). 3) Repeat until all vertices are connected.

步骤：1) 按权重升序列出所有边。2) 选择连接两棵不同树（即不形成环）的最小边。3) 重复直到所有顶点都连通。

Total weight = sum of selected edge weights

总权重 = 所选边权重之和

7. Minimum Spanning Tree: Prim’s Algorithm | 最小生成树：Prim 算法

Prim’s algorithm starts from an arbitrary vertex and grows the tree by adding the cheapest edge from the current tree to a new vertex. It can be implemented using a table or a matrix representation.

Prim 算法从任意一个顶点开始，通过添加从当前树到新顶点的最便宜边来逐步扩展树。它可以使用表格或矩阵表示来实现。

Step / 步骤	Action / 操作
1	Choose start vertex A, add it to tree. / 选择起始顶点 A，加入树。
2	Examine edges from A, pick smallest (say to B). Add B. / 检查 A 的边，选择最小边（如到 B）。加入 B。
3	Now examine edges from {A, B} to remaining vertices, pick the smallest. / 现在检查从 {A, B} 到其余顶点的边，选择最小的。

8. Travelling Salesman Problem (TSP) | 旅行商问题 (TSP)

The TSP aims to find the shortest possible route that visits every vertex exactly once and returns to the start. For small graphs, you can list all Hamiltonian cycles and compare total weights.

旅行商问题旨在找出访问每个顶点恰好一次并返回起点的最短路径。对于小图，你可以列出所有哈密顿圈并比较总权重。

IGCSE questions often involve finding an upper bound (using nearest neighbour) or a lower bound for the TSP.
IGCSE 题目通常涉及寻找上界（使用最近邻法）或下界。

The nearest neighbour algorithm: start at a vertex, repeatedly go to the nearest unvisited vertex, then return to start. This gives a feasible route, an upper bound for the optimal solution.
最近邻算法：从一个顶点出发，反复前往最近的未访问顶点，然后返回起点。这给出一个可行路线，即最优解的上界。

9. Shortest Path: Dijkstra’s Algorithm | 最短路径：Dijkstra 算法

Dijkstra’s algorithm finds the shortest path from a source vertex to all others in a weighted graph with non-negative edges. It uses labelling and permanent/ temporary marks, a key skill for IGCSE students.

Dijkstra 算法在非负权边的加权图中找到从源顶点到所有其他顶点的最短路径。它使用标注和永久性/临时性标记，这是 IGCSE 学生需要掌握的关键技能。

Algorithm: 1) Label start vertex with distance 0 (permanent). 2) Update neighbours with shortest distance so far. 3) Choose the smallest temporary label, make it permanent. 4) Repeat until destination is permanently labelled.

算法：1) 给起点标注距离 0（永久）。2) 用目前的最短距离更新邻居。3) 选择最小的临时标注，将其变为永久。4) 重复直到目的地被永久标注。

10. Exam Tips and Common Pitfalls | 考试技巧与常见误区

When tackling graph theory problems, always draw clear diagrams and list edges systematically. Show all steps for Kruskal or Prim clearly, indicate order of edge selection, and calculate total weight accurately.

解答图论问题时，始终绘制清晰的图表，系统地列出边。清楚地展示 Kruskal 或 Prim 的所有步骤，标明选择边的顺序，并准确计算总权重。

Avoid mixing up Eulerian and Hamiltonian concepts. Eulerian = edges, Hamiltonian = vertices. / 避免混淆欧拉与哈密顿概念。欧拉针对边，哈密顿针对顶点。
When applying nearest neighbour for TSP, remember to return to the start. Many candidates forget the final edge. / 对 TSP 应用最近邻法时，记得返回起点。许多考生会忘记最后一条边。
In Dijkstra, double-check that you are using the correct order and that all temporary labels are updated before choosing the next permanent vertex. / 在 Dijkstra 中，仔细检查顺序是否正确，以及在选择下一个永久顶点之前所有临时标注是否已更新。

Published by TutorHao | IGCSE CIE Mathematics Revision Series | aleveler.com

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

IGCSE CIE Mathematics: Graph Theory Essentials | IGCSE CIE 数学：图论 考点精讲