📚 IB Mathematics: Further Applications of Graph Theory | IB数学：图论的进一步应用解析
Graph theory begins with simple ideas — vertices, edges, paths and circuits — but its real power lies in solving complex practical problems. In IB Mathematics AI HL, graph theory moves beyond definitions into algorithms, optimisation and decision-making.
图论始于顶点、边、路径和回路这些简单概念，但它的真正力量在于解决复杂的实际问题。在IB数学AI HL中，图论的学习不止于定义，而会深入到算法、优化与决策问题。
This article explores the further applications of graph theory: matrix representations, minimum spanning trees, shortest paths, route inspection, travelling salesmen and complexity. These tools are not just exam topics; they are the language of modern networks.
本文将深入探讨图论的进一步应用：矩阵表示、最小生成树、最短路径、路线巡检、旅行商问题以及算法复杂度。这些工具不仅是考试考点，更是现代网络世界的通用语言。
1. From Graphs to Networks: Real-World Modelling | 从图到网络：真实世界建模
A graph G = (V, E) consists of a set V of vertices and a set E of edges. When each edge carries a numerical value, such as distance, cost or time, the graph is called a weighted graph. Weighted graphs allow us to model many real-world systems.
一个图 G = (V, E) 由顶点集 V 和边集 E 组成。当每条边带有一个数值，例如距离、成本或时间时，这个图被称为加权图。加权图使我们能够对许多现实系统建模。
In an undirected graph, edges are two-way; in a directed graph, each edge has a direction. Road networks are usually modelled as directed weighted graphs because one-way streets and turn restrictions matter. Airline networks are directed when flight routes are not symmetric.
在无向图中，边是双向的；在有向图中，每条边具有方向。公路网络通常被建模为有向加权图，因为单行道和转向限制非常重要。航空网络在航线不对称时也以有向图形式表示。
Graphs are therefore not just abstract drawings. By choosing vertices and edge weights carefully, we can represent transportation systems, communication networks, social relationships, and biological pathways in a single mathematical structure.
因此，图并非只是抽象的图形。通过仔细选择顶点和边权，我们可以用同一个数学结构来表示交通系统、通信网络、社交关系和生物通路。
2. Adjacency and Weighted Matrices | 邻接矩阵与加权矩阵
An adjacency matrix is a compact way to store a graph. For a graph with n vertices, the adjacency matrix A is an n × n matrix in which the entry at row i and column j records whether there is an edge from vertex i to vertex j. For an unweighted graph, this entry is 1 or 0.
邻接矩阵是存储图的紧凑方式。对于有 n 个顶点的图，邻接矩阵 A 是一个 n × n 矩阵，其中第 i 行第 j 列的元素记录从顶点 i 到顶点 j 是否存在边。对于无权图，该元素为 1 或 0。
For a weighted graph, the matrix entry is the weight of the edge, and a special symbol such as 0 or ∞ is used when no edge exists. Weighted matrices are essential for computer implementations of algorithms because they turn visual information into arithmetic.
对于加权图，矩阵中的元素就是边的权重，当边不存在时用 0 或 ∞ 等特殊符号表示。加权矩阵对于算法的计算机实现至关重要，因为它把视觉信息转化为算术运算。
One powerful result is that the entry in row i and column j of the matrix Aⁿ gives the number of walks of length n from vertex i to vertex j. This allows us to count routes in a network without drawing each possibility.
一个重要的结论是：矩阵 Aⁿ 中第 i 行第 j 列的元素，表示从顶点 i 到顶点 j 的长度为 n 的路径数量。这使我们不必逐一画出每种可能，就能计算网络中的路径条数。
Consider the simple directed graph below with vertices A, B and C, and edges A→B, A→C and B→A.
考虑下面这个简单有向图：顶点为 A、B、C，边为 A→B、A→C 和 B→A。
| A | 0 | 1 | 1 |
| B | 1 | 0 | 0 |
| C | 0 | 0 | 0 |
Using powers of this adjacency matrix, we can count walks of two or more steps. Matrix methods also extend to dominance in tournaments, where A + A² is used to rank competitors based on direct and indirect defeats.
利用该邻接矩阵的幂，我们可以计算两步或更多步的路径数量。矩阵方法还可以推广到竞赛图中的优势排名：通过 A + A² 来根据直接和间接胜负对参赛者排序。
3. Minimum Spanning Trees: Kruskal and Prim | 最小生成树：Kruskal 与 Prim
A spanning tree of a connected graph includes all vertices and exactly enough edges so that the graph remains connected and contains no cycles. A minimum spanning tree (MST) is a spanning tree with the smallest possible total edge weight.
连通图的生成树包含全部顶点，并且只使用恰好足够的边使图保持连通且不产生回路。最小生成树（MST）是总边权最小的生成树。
Kruskal’s algorithm sorts all edges by increasing weight and adds each edge to the tree unless it creates a cycle. This process continues until every vertex is connected. It is a greedy algorithm: at each stage it makes the locally cheapest choice.
Kruskal 算法将所有边按权重从小到大排序，并逐条加入生成树，除非这条边会形成回路。这个过程持续到所有顶点连通为止。这是一种贪心算法：每一步都做出当前代价最小的选择。
Prim’s algorithm starts from any chosen vertex and repeatedly adds the cheapest edge that connects a new vertex to the growing tree. Unlike Kruskal, Prim does not need to sort every edge at the start, and it is often easier to apply when the graph is dense.
Prim 算法从任意一个选定顶点开始，反复添加连接新顶点与当前生长树的最便宜边。与 Kruskal 不同，Prim 无需一开始对所有边排序，在稠密图中通常更容易使用。
| Algorithm | Starting Point | Key Idea | Typical Use |
| Kruskal | Any edge list | Pick smallest edge if no cycle | Sparse graphs |
| Prim | Any vertex | Grow tree by cheapest connection | Dense graphs |
Both algorithms produce an optimal MST, and their correctness follows from the cut property: the lightest edge crossing any cut must belong to some minimum spanning tree.
两种算法都能得到最优的最小生成树，其正确性基于割性质：跨越任意一个割的最轻边必定属于某棵最小生成树。
4. Shortest Path: Dijkstra’s Algorithm | 最短路径：Dijkstra 算法
Dijkstra’s algorithm finds the shortest path from a starting vertex to every other vertex in a weighted graph with non-negative weights. It is widely used in GPS navigation, network routing and logistics.
Dijkstra 算法用于在所有权重非负的加权图中，从起点出发寻找到达其他所有顶点的最短路径。它被广泛应用于GPS导航、网络路由和物流运输。
The algorithm begins by giving the starting vertex a permanent label of 0 and all other vertices a temporary label of infinity. At each step, the smallest temporary label becomes permanent, and all neighbours of that vertex receive updated temporary labels.
算法首先把起点标记为永久标签 0，把所有其他顶点标记为临时标签无穷大。每一步中，最小的临时标签变为永久标签，同时该顶点的所有邻居都会更新临时标签。
The update rule is fundamental: for a vertex u with permanent label P(u) and an edge from u to v of weight w, the temporary label of v improves if P(u) + w is smaller than the current label of v.
更新规则非常关键：对于具有永久标签 P(u) 的顶点 u，以及从 u 到 v、权重为 w 的边，如果 P(u) + w 小于 v 当前标签，那么 v 的临时标签就应更新为更小的值。
Dijkstra’s algorithm is efficient and exact, but it fails when negative edge weights are present. In such cases, more general methods such as the Bellman-Ford algorithm may be required, although these are generally not assessed in IB Mathematics.
Dijkstra 算法高效且精确，但当图中存在负权边时它就不适用了。在这种情况下，可能需要 Bellman-Ford 等更一般的方法，不过这些通常不在IB数学考试范围内。
5. Route Inspection: The Chinese Postman Problem | 路线巡检：中国邮递员问题
The route inspection problem asks for the shortest closed route that traverses every edge of a graph at least once and returns to the starting point. It is historically called the Chinese Postman Problem, named after the Chinese mathematician Mei-Ko Kwan.
路线巡检问题要求找到一条最短的闭环路线，使得它经过图中每条边至少一次，并最终回到起点。这个问题历史上被称为中国邮递员问题，以华人数学家管梅谷的名字命名。
If every vertex has even degree, the graph has an Eulerian circuit, so the optimal route is simply the sum of all edge weights. No edge needs to be duplicated.
如果所有顶点的度数都是偶数，图中存在欧拉回路，因此最优路线就是所有边权重之和。此时不需要重复走任何边。
When some vertices have odd degree, the postman must repeat certain edges so that the duplicated edges make every vertex even. The goal is to choose the cheapest possible set of duplicate edges.
当存在奇数度顶点时，邮递员必须重复走某些边，使所有顶点在加入重复边后都变为偶数度。目标是选择总成本最小的重复边集合。
The solution is found by selecting the odd-degree vertices and pairing them up according to their shortest paths. The total duplicated length is the minimum total matching cost among all pairings of the odd vertices.
解法的关键是找出所有奇数度顶点，并按照它们之间的最短路径进行配对。被重复行走的总长度，就是所有奇数度顶点配对方案中的最小总匹配成本。
This problem has practical applications in street sweeping, mail delivery, refuse collection and inspection of power lines.
这个问题在街道清扫、邮件投递、垃圾收集和电力线路巡检中都有实际应用。
6. The Travelling Salesman Problem and Upper Bounds | 旅行商问题与上界
The travelling salesman problem (TSP) asks for the shortest Hamiltonian cycle in a weighted graph: a cycle that visits every vertex exactly once and returns to the starting vertex. Unlike the Chinese postman problem, the TSP is extremely difficult to solve exactly for large graphs.
旅行商问题（TSP）要求在加权图中寻找最短的哈密顿回路：一条恰好访问每个顶点一次并返回起点的回路。与中国邮递员问题不同，旅行商问题在大型图中极难精确求解。
One simple way to obtain an upper bound, or a route that is no worse than a certain length, is the nearest neighbour algorithm. Starting at one vertex, we repeatedly move to the nearest unvisited vertex until all vertices have been visited, then return to the start.
获得上界（即一条长度不超过某个值的可行路线）的简单方法是最近邻算法。从某个顶点出发，反复移动到最近的未访问顶点，直到所有顶点都被访问，最后返回起点。
The nearest neighbour algorithm is fast but can produce a poor tour. In IB examination questions, it is often used to find an initial upper bound, and students are asked to improve it by trial or by using alternative starting vertices.
最近邻算法很快，但可能产生较差的路线。在IB考试中，它常被用来寻找初始上界，并要求学生通过尝试或选择不同起点来改进路线。
Because the TSP is NP-hard, no efficient algorithm is known to solve it exactly for all graphs. This is why upper bounds are valuable: they provide practical, feasible route lengths that can be implemented immediately.
由于旅行商问题是NP难问题，目前还没有已知的高效算法能够对所有图精确求解。因此上界很有价值：它提供了可实际使用、马上可行的路线长度。
7. Lower Bounds for the Travelling Salesman Problem | 旅行商问题的下界
A lower bound tells us that no Hamiltonian cycle can be shorter than a certain value. If a candidate route is only slightly longer than the lower bound, we know it is close to optimal even without exhausting all possibilities.
下界告诉我们，任何哈密顿回路都不可能短于某个数值。如果某条候选路线只比下界长一点点，那么即使不穷举所有可能，我们也能知道它接近最优。
One standard lower bound is obtained by removing a chosen vertex v from the graph. Consider the remaining graph with all vertices except v. The minimum spanning tree of this reduced graph has weight M. The shortest possible Hamiltonian cycle must contain two edges incident to v; call the sum of the two smallest edges incident to v as s.
一个标准下界是去掉某个选定顶点 v 得到的。考虑去掉 v 后剩余顶点构成的图，其最小生成树权重记为 M。最短的哈密顿回路一定包含两条与 v 相连的边；把 v 的所有关联边中最小的两条边之和记为 s。
Lower bound = M + s
Why is this valid? If we remove v from any Hamiltonian cycle, the remaining edges form a path through all other vertices. This path is a spanning tree, so its weight is at least M. The two edges removed from v together weigh at least s.
为什么这是有效的？如果从任意哈密顿回路中删去 v，剩余边形成一条经过所有其他顶点的路径。这条路径是一棵生成树，因此其权重至少为 M。而与 v 相连的这两条边合计至少为 s。
Thus the true optimal tour has length at least M + s. This lower bound can be compared with an upper bound to evaluate the quality of a candidate route in network design problems.
因此，真正的最优回路长度至少为 M + s。这个下界可以与某个上界比较，用来评估网络设计问题中候选路径的质量。
8. Complexity and Algorithmic Thinking | 算法复杂度与算法思维
Graph algorithms differ dramatically in difficulty. Minimum spanning trees and shortest paths can be found in polynomial time, meaning they can be solved efficiently even for large networks.
图算法在难度上差异很大。最小生成树和最短路径问题可以在多项式时间内求解，这意味着即使网络规模较大，它们仍然可以被高效解决。
The travelling salesman problem, by contrast, belongs to a class of problems called NP-hard. No known algorithm can guarantee an optimal answer in polynomial time for all instances. As the number of vertices grows, the search space expands factorially.
相比之下，旅行商问题属于被称为NP难的问题类别。目前没有已知算法能在多项式时间内保证对所有实例都给出最优解。随着顶点数增加，搜索空间会按阶乘方式爆炸式增长。
In IB Mathematics, this distinction is important. For easy problems, we use exact algorithms. For hard problems, we use heuristics to generate upper bounds and clever reasoning to generate lower bounds.
在IB数学中，这种区别非常重要。对于容易的问题，我们使用精确算法；对于困难的问题，我们使用启发式算法生成上界，并用巧妙的推理生成下界。
Algorithmic thinking also includes evaluating efficiency. The notation O(E log V) describes how the running time of an algorithm grows with the number of edges E and vertices V. This helps engineers choose algorithms that will run quickly on real networks.
算法思维还包括评估效率。记号 O(E log V) 描述算法运行时间如何随边数 E 和顶点数 V 增长。这帮助工程师选择在真实网络上运行较快的算法。
9. Applications in Science and Technology | 在科学技术中的应用
Graph theory is not confined to mathematics. In social networks, users are vertices and friendships are edges. Algorithms such as PageRank treat the web as a directed graph and rank pages by considering random walks through this graph.
图论不仅限于数学。在社交网络中，用户是顶点，好友关系是边。PageRank 等算法将网络视为有向图，并通过在图上的随机游走来对网页排名。
In bioinformatics, genome assembly uses de Bruijn graphs. Short DNA fragments are represented as edges, and reconstructing the genome becomes an Eulerian path problem in a very large graph.
在生物信息学中，基因组拼接使用 de Bruijn 图。短DNA片段被表示为边，而重构基因组就变成了在大型图中寻找欧拉路径的问题。
In sports analytics, tournament graphs show the outcome of every pair of competitors. The dominance matrix A + A² can rank players not only by direct wins but also by wins over strong opponents, giving a fairer ranking system.
在体育数据分析中，竞赛图展示每对参赛者的胜负结果。优势矩阵 A + A² 不仅根据直接胜利排名，还根据战胜强手的间接表现排名，从而提供更合理的排序体系。
Graph theory also supports electrical circuit design, scheduling problems, chemical molecule studies and artificial intelligence planning. Understanding graph algorithms gives students a powerful toolkit for modelling and solving modern problems.
图论还支撑着电路设计、调度问题、化学分子研究和人工智能规划。理解图算法，为学生提供了一套强大的工具，用于建模和解决现代问题。
Graph theory is one of the most applicable topics in IB Mathematics. From finding efficient postal routes to evaluating the quality of a travelling salesman tour, the ideas of graphs, matrices and algorithms are essential for future mathematicians, engineers and data scientists.
图论是IB数学中最具应用价值的主题之一。从寻找高效的邮递路线到评估旅行商路径的质量，图、矩阵与算法的思想对未来的数学家、工程师和数据科学家都至关重要。
Published by TutorHao | IB Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导