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

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

Graph theory is a fundamental topic in the IB Mathematics: Applications and Interpretation (AI) syllabus, particularly at Higher Level. It provides a powerful framework for modelling networks, connectivity, and optimisation problems. In the IB exams, you are expected to define basic concepts, apply algorithms like Kruskal’s and Dijkstra’s, and interpret results in context. This revision guide breaks down the key examination points, complete with definitions, theorems, and worked examples to help you master the subject.

图论是 IB 数学：应用与解释 (AI) 大纲中的基础课题，尤其是在高水平 (HL) 中。它为网络建模、连通性和最优化问题提供了强有力的框架。在 IB 考试中，你需要能够定义基本概念，应用如 Kruskal 和 Dijkstra 算法，并在上下文中解释结果。本复习指南分解了关键考点，包括定义、定理和解题示例，助你掌握这一主题。

1. Basic Terminology | 基本术语

A graph G is defined as an ordered pair G = (V, E) where V is a set of vertices (nodes) and E is a set of edges (links) connecting pairs of vertices.

图 G 定义为一个有序对 G = (V, E)，其中 V 是顶点（节点）集，E 是连接顶点对的边（链接）集。

In IB, we usually focus on simple graphs – no loops and no multiple edges between the same pair of vertices.

在 IB 中，我们通常关注简单图——没有环，且同一对顶点之间没有多重边。

The order of a graph is the number of vertices, denoted |V| or n. The size is the number of edges, |E|.

图的阶是顶点数，记作 |V| 或 n。大小是边数，记作 |E|。

Two vertices are adjacent if they are joined by an edge. An edge is incident to its endpoints.

如果两个顶点由一条边连接，则它们是邻接的。一条边关联于它的端点。

The degree of a vertex v, deg(v), is the number of edges incident to it. (A loop, if present, contributes 2 to the degree.)

顶点 v 的度，deg(v)，是关联于它的边数。（如果存在环，则环对度的贡献为 2。）

A degree sequence lists the degrees of all vertices in non‑increasing order.

度序列以非递增顺序列出所有顶点的度。

2. Handshaking Lemma | 握手引理

The handshaking lemma states that for any graph, the sum of the degrees of all vertices is exactly twice the number of edges: ∑ deg(v) = 2|E|.

握手引理指出，对于任何图，所有顶点的度之和恰好是边数的两倍：∑ deg(v) = 2|E|。

An immediate consequence is that the number of odd‑degree vertices must be even. This serves as a quick check when solving construction problems.

一个直接推论是，奇度顶点的个数必须是偶数。这是在解决构图问题时的一个快速检验。

In directed graphs, the sum of in‑degrees equals the sum of out‑degrees, both equal to the number of directed edges.

在有向图中，入度之和等于出度之和，都等于有向边的数量。

3. Adjacency and Incidence Matrices | 邻接矩阵与关联矩阵

The adjacency matrix A of a graph with n vertices is

Published by TutorHao | IB Mathematics Revision Series | aleveler.com

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