IB数学AI 图论 Kruskal Dijkstra 最短路径 考点

IB数学AI 图论 Kruskal Dijkstra 最短路径 考点

Graph theory is one of the most distinctive topics in the IB Mathematics Applications and Interpretation (AI) syllabus. Unlike algebra or calculus, which build on years of prior learning, graph theory introduces a completely new way of thinking about mathematical structures and their real-world applications. 图论 (graph theory) 是 IB 数学 AI 课程中最具特色的主题之一。与代数和微积分不同，图论引入了一种全新的思维方式，用于理解数学结构及其在现实世界中的应用。

In the IB AI syllabus, graph theory appears in both Standard Level (SL) and Higher Level (HL), with HL students expected to handle more complex algorithms and proofs. 在 IB AI 课程中，图论同时出现在 SL 和 HL 两个级别中，HL 学生需要掌握更复杂的算法和证明。The topic spans graph terminology, types of graphs, connectivity, trees, spanning trees, shortest paths, and classical problems like the Chinese postman problem and the traveling salesman problem. 这一主题涵盖了图的基本术语、图的类型、连通性、树、生成树、最短路径，以及经典问题如中国邮递员问题和旅行商问题。

What Is a Graph? 什么是图？

A graph is a mathematical structure consisting of vertices (nodes) and edges (lines connecting them). In IB context, think of vertices as cities and edges as roads. 图是由顶点（节点）和边（连接线）组成的数学结构。在 IB 语境中，可以把顶点想象成城市，边想象成连接城市的道路。

Formally, a graph G is defined as an ordered pair G = (V, E), where V is a set of vertices and E is a set of edges. Each edge connects two vertices. 从形式上讲，图 G 定义为一个有序对 G = (V, E)，其中 V 是顶点集合，E 是边集合，每条边连接两个顶点。The edge between vertices u and v can be written as {u, v} for undirected edges or (u, v) for directed edges. 无向边可以写作 {u, v}，有向边写作 (u, v)。

Graphs can be classified into several types: 图可以分为以下几种类型：

• Simple graphs 简单图: No loops and no multiple edges between the same pair of vertices. 没有自环，也没有重复边。
• Directed graphs (digraphs) 有向图: Edges have a direction, going from one vertex to another. 边有方向性。
• Weighted graphs 加权图: Each edge carries a numerical weight, representing distance, cost, or time. 每条边带有数值权重，代表距离、成本或时间。
• Complete graphs 完全图: Every pair of vertices is connected by an edge. Denoted as K_n for n vertices. 每对顶点之间都有边相连，用 K_n 表示。
• Trees 树: Connected graphs with no cycles. A tree with n vertices always has exactly n - 1 edges. 无环连通图。n 个顶点的树恰好有 n - 1 条边。

Graph Representation 图的表示方法

In IB AI exams, you need to be comfortable with two main representations of graphs: adjacency matrices and adjacency lists. IB AI 考试中，你需要熟练掌握两种图的表示方法：邻接矩阵和邻接表。

Adjacency Matrix 邻接矩阵: An n x n matrix where entry (i, j) is the weight of the edge from vertex i to vertex j. For unweighted graphs, it is 1 if an edge exists and 0 otherwise. For undirected graphs, the matrix is symmetric. 一个 n x n 矩阵，其中第 (i, j) 项表示从顶点 i 到顶点 j 的边的权重。对于无权图，有边则为 1，无边则为 0。对于无向图，矩阵是对称的。

Adjacency List 邻接表: A collection of lists, one for each vertex, listing all vertices adjacent to it. More space-efficient for sparse graphs. 为每个顶点维护一个列表，列出所有与其相邻的顶点。对于稀疏图来说，空间效率更高。

Minimum Spanning Tree 最小生成树

A spanning tree of a connected graph is a subgraph that includes all vertices and is a tree (no cycles). A minimum spanning tree (MST) is the spanning tree with the smallest total edge weight. IB AI 考试中，生成树和最小生成树是核心考点。连通图的生成树是一个包含所有顶点的无环子图。最小生成树（MST）是总边权最小的生成树。

Applications of MSTs include designing efficient networks, such as laying cables or pipelines at minimum cost. MST 的应用包括设计高效网络，例如以最小成本铺设电缆或管道。

Kruskal's Algorithm Kruskal算法

Kruskal's algorithm is a greedy algorithm for finding the MST of a connected, weighted graph. Kruskal 算法是一种贪心算法，用于在连通加权图中寻找 MST。The algorithm works as follows: 算法步骤如下：

1. Sort all edges in ascending order of weight. 将所有边按权重升序排列。
2. Start with an empty set of edges for the tree. 初始化一个空的边集合。
3. Consider edges one by one: add the edge to the tree if it does not create a cycle. 逐一考察每条边：如果加入后不形成环，就将其加入树中。
4. Stop when you have added exactly V - 1 edges, where V is the number of vertices. 当你添加了恰好 V - 1 条边后停止，其中 V 是顶点数。

In the IB exam, you will typically be asked to state the order in which edges are selected and to calculate the total weight of the MST. 在 IB 考试中，你通常需要说明边的选择顺序，并计算 MST 的总权重。A common exam technique is to list edges and cross out those that would create a cycle. 常见的考试技巧是列出所有边，划掉那些会形成环的边。

Kruskal's algorithm works particularly well for sparse graphs and is guaranteed to find the MST. Kruskal 算法特别适用于稀疏图，并且保证能找到 MST。The key insight is the cut property: the minimum-weight edge crossing any cut of the graph must belong to the MST. 关键原理是割性质：跨越图中任意割的最小权重边必定属于 MST。

Prim's Algorithm Prim算法

Prim's algorithm is another greedy approach to finding the MST, but it builds the tree vertex by vertex rather than edge by edge. Prim 算法是另一种寻找 MST 的贪心方法，但它是一个顶点一个顶点地构建树，而非一条边一条边地添加。

The algorithm starts with any vertex and repeatedly adds the cheapest edge connecting the current tree to a vertex not yet in the tree. 算法从任意顶点开始，反复添加连接当前树与尚未加入树的顶点的最便宜边。Prim's algorithm is often more intuitive when working with adjacency matrices, which IB students frequently encounter in Paper 1. 当使用邻接矩阵时，Prim 算法通常更直观，这也是 IB 学生在试卷一中经常遇到的。

Key differences between Kruskal and Prim: Kruskal sorts all edges first, then adds the cheapest non-cycle-forming edge. Prim grows the tree outward from a starting vertex by always picking the cheapest connection. Kruskal 和 Prim 的关键区别：Kruskal 先对所有边排序，然后添加最便宜且不形成环的边。Prim 从起始顶点向外扩展，总是选择最便宜的连接。

Shortest Path Algorithms 最短路径算法

While MSTs minimize total connection cost, shortest path problems minimize the distance between a specific pair of vertices (or from one vertex to all others). 虽然 MST 最小化总连接成本，但最短路径问题最小化特定顶点对之间（或从一个顶点到所有其他顶点）的距离。

Dijkstra's Algorithm Dijkstra算法

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. Dijkstra 算法在具有非负边权的加权图中，找到从源顶点到所有其他顶点的最短路径。

The algorithm maintains a set of vertices whose shortest distance from the source is known. It works as follows: 算法维护一个已知最短距离的顶点集合。工作步骤如下：

1. Assign a distance of 0 to the source vertex and infinity to all others. 给源顶点赋距离 0，其他顶点赋无穷大。
2. Mark all vertices as unvisited. 将所有顶点标记为未访问。
3. For the current vertex, consider all its unvisited neighbors and calculate their tentative distances. Update if a shorter path is found. 对于当前顶点，考察所有未访问的邻居并计算试探距离。如果找到更短路径则更新。
4. Mark the current vertex as visited. Select the unvisited vertex with the smallest tentative distance as the new current vertex. 将当前顶点标记为已访问。选择具有最小试探距离的未访问顶点作为新的当前顶点。
5. Repeat until all vertices are visited. 重复直到所有顶点都已访问。

In IB exams, you are often asked to construct a table showing the working of Dijkstra's algorithm, with columns for each vertex tracking the shortest distance and the preceding vertex on the path. 在 IB 考试中，你通常需要构建一个表格来展示 Dijkstra 算法的运算过程，每个顶点对应一列，记录最短距离和路径上的前驱顶点。

Important limitation: Dijkstra's algorithm does NOT work with negative edge weights. If a graph contains negative weights, use the Bellman-Ford algorithm instead (HL only). 重要限制：Dijkstra 算法不适用于负边权。如果图包含负权重，需要使用 Bellman-Ford 算法（仅 HL）。

Eulerian and Hamiltonian Paths 欧拉路径与哈密顿路径

An Eulerian trail is a path that uses every edge of a graph exactly once. An Eulerian circuit (or tour) is an Eulerian trail that starts and ends at the same vertex. 欧拉路径是恰好使用图中每条边各一次的路径。欧拉回路是起点和终点相同的欧拉路径。

A connected graph has an Eulerian circuit if and only if every vertex has an even degree. It has an Eulerian trail (but not a circuit) if exactly two vertices have odd degree. 一个连通图存在欧拉回路当且仅当每个顶点的度数均为偶数。如果恰好有两个顶点度数为奇数，则存在欧拉路径（但不是回路）。

A Hamiltonian path visits every vertex of a graph exactly once. A Hamiltonian cycle is a Hamiltonian path that returns to the starting vertex. 哈密顿路径恰好访问图中每个顶点各一次。哈密顿回路是回到起点的哈密顿路径。

Unlike Eulerian paths, there is no simple necessary and sufficient condition for the existence of Hamiltonian paths — this is one of the great unsolved problems in computer science (the P versus NP problem). 与欧拉路径不同，哈密顿路径的存在性没有简单的充要条件，这是计算机科学中著名的未解问题之一（P vs NP 问题）。

Chinese Postman Problem 中国邮递员问题

The Chinese postman problem asks: what is the shortest route that traverses every edge of a graph at least once, starting and ending at the same vertex? 中国邮递员问题问的是：遍历图中每条边至少一次，且起点和终点相同的最短路线是什么？

For Eulerian graphs (all vertices even degree), the optimal route is simply an Eulerian circuit with total length equal to the sum of all edge weights. 对于欧拉图（所有顶点的度数均为偶数），最优路线就是欧拉回路，总长度等于所有边权之和。

For non-Eulerian graphs, you must identify the odd-degree vertices, pair them up to minimize the added distance, and duplicate those paths. 对于非欧拉图，你需要找出奇度顶点，将它们配对以最小化添加的距离，并复制这些路径。This is an essential IB AI SL/HL exam topic — expect to be asked to find the optimal postman route and state the total distance. 这是 IB AI SL/HL 的重要考点，你需要能够找到最优邮递员路线并给出总距离。

Traveling Salesman Problem 旅行商问题

The traveling salesman problem (TSP) seeks the shortest Hamiltonian cycle in a complete weighted graph — the shortest route visiting every vertex exactly once and returning to the start. 旅行商问题（TSP）在完全加权图中寻找最短哈密顿回路，即恰好访问每个顶点各一次并返回起点的最短路线。

TSP is an NP-hard problem, meaning there is no known efficient algorithm for solving all instances. 旅行商问题是 NP 难题，目前没有已知的能有效求解所有实例的算法。For small graphs, IB students are expected to find the optimal solution by listing all possible Hamiltonian cycles (n - 1)! / 2 for a complete graph of n vertices. 对于小图，IB 学生需要通过列举所有可能的哈密顿回路来找到最优解（n 个顶点的完全图有 (n - 1)! / 2 条回路）。

For larger graphs, IB focuses on heuristic methods: 对于较大的图，IB 关注启发式方法：

• Nearest neighbor algorithm 最近邻算法: Start at any vertex and repeatedly visit the nearest unvisited vertex. Fast but not guaranteed to find the optimal solution. 从任意顶点开始，反复访问最近的未访问顶点。速度快但不保证找到最优解。
• Deleted vertex method 删除顶点法: Remove one vertex, find the MST of the remaining graph, then reconnect the deleted vertex using its two cheapest edges. Used to find a lower bound. 删除一个顶点，求剩余图的 MST，然后用两条最便宜的边重新连接被删除的顶点。用于求下界。

IB Exam Tips IB考试技巧

Here are the most common traps and tips for IB graph theory questions: 以下是 IB 图论题中最常见的陷阱和技巧：

1. Show your working clearly. 清晰展示运算过程。 Most graph theory questions require you to list edges in the order selected or show a table of distances. The working often carries more marks than the final answer. 大多数图论题要求你按选择顺序列出边，或展示距离表。运算过程往往比最终答案占更多分数。

2. Know your notation. 熟悉你的符号。 Use K_n for complete graphs, C_n for cycle graphs, v for number of vertices, e for number of edges. IB examiners expect precise notation. IB 考官期望精确的符号。

3. Verify the degree condition. 验证度数条件。 Before applying Eulerian or Chinese postman problem methods, always check the degrees of vertices. This is the number one mistake in IB exams. 在应用欧拉路径或中国邮递员问题方法之前，务必检查顶点度数。这是 IB 考试中最常见的错误。

4. For Dijkstra, always update predecessors. 对于 Dijkstra，始终更新前驱。 The shortest path itself (not just its length) is often required. You need to be able to trace back from the destination to the source. 往往不仅需要最短距离，还需要最短路径本身。你需要能够从终点回溯到起点。

5. Distinguish between upper and lower bounds. 区分上界和下界。 For TSP: lower bound = deleted vertex method. Upper bound = nearest neighbor. The optimal tour lies between them. 对于 TSP：下界 = 删除顶点法，上界 = 最近邻法。最优路径介于两者之间。

6. Calculator use. 计算器使用。 The TI-Nspire and Casio fx-9860GII have graph theory functions that can check your work, but you must show manual working on Paper 2 as well. TI-Nspire 和 Casio fx-9860GII 有图论功能可以检查你的答案，但在试卷二中也需要展示手动运算过程。

常见考试题型 Common Exam Question Types

Based on past IB papers, here are the most frequent question patterns: 根据历年 IB 真题，以下是最常见的问题模式：

Type 1: "Use Kruskal's algorithm to find the minimum spanning tree and state its total weight." 用 Kruskal 算法求最小生成树并给出总权重。This appears on nearly every exam. List edges in order, stop when you have v - 1 edges, sum the weights. 这几乎出现在每一份试卷中。按顺序列出边，达到 v - 1 条时停止，求和。

Type 2: "Find the shortest path from A to G using Dijkstra's algorithm." 用 Dijkstra 算法求 A 到 G 的最短路径。Set up a table with columns for each vertex. Show all updates. 为每个顶点设置列。展示所有更新。

Type 3: "Determine if the graph is Eulerian, semi-Eulerian, or neither." 判断图是欧拉图、半欧拉图还是两者皆非。Count the degree of each vertex. 0 odd vertices = Eulerian. Exactly 2 odd = semi-Eulerian. 计算每个顶点的度数：0 个奇数 = 欧拉图，恰好 2 个奇数 = 半欧拉图。

Type 4: "Solve the Chinese postman problem for this network." 求解该网络的中国邮递员问题。Identify odd vertices, find all pairings, calculate total added distance for each pairing, choose the minimum. 找出奇度顶点，找到所有配对，计算每种配对的总添加距离，选择最小值。

Type 5 (HL): "Find a lower bound for the TSP and compare it to the nearest neighbor upper bound." 求 TSP 的下界并与最近邻上界比较。Use deleted vertex method for the lower bound; apply nearest neighbor for the upper bound. State your conclusion about the optimal tour length. 使用删除顶点法求下界，使用最近邻法求上界。陈述关于最优路径长度的结论。

Connecting to the Bigger Picture 联系更广阔的图景

Graph theory is not just an exam topic — it is one of the most practical areas of mathematics. 图论不仅仅是考试主题，它还是数学中最实用的领域之一。Google's PageRank algorithm uses directed graphs. Social networks are analyzed using graph centrality measures. GPS navigation systems implement variants of Dijkstra's algorithm millions of times per day. 谷歌的 PageRank 算法使用有向图。社交网络使用图中心性度量进行分析。GPS 导航系统每天数百万次地执行 Dijkstra 算法的变体。

For IB students, mastering graph theory means developing algorithmic thinking — the ability to follow and apply precise step-by-step procedures to solve problems. This skill transfers directly to computer science, engineering, logistics, and data science. 对于 IB 学生来说，掌握图论意味着培养算法思维，即遵循和应用精确的逐步程序来解决问题的能力。这项技能直接迁移到计算机科学、工程、物流和数据科学领域。

Whether you are SL or HL, the graph theory section of the IB AI exam rewards careful, systematic working. Practice past paper questions until the algorithms become second nature. 无论你是 SL 还是 HL，IB AI 考试中的图论部分都奖励仔细、系统化的运算过程。练习历年真题，直到算法成为你的第二天性。

🛍️ 微信小店好物推荐

fx-991CN X 中文版计算器-老王推荐

¥168.00 🛒 微信小店购买

🎓 需要一对一辅导？

📱 16621398022 同微信

关注公众号 tutorhao 获取更多学习资源

📚 更多资源 →

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