📚 Graph Theory and Its Real-World Applications | 图论及其实际应用
Graph theory is one of the most visually intuitive yet mathematically profound topics in the IB Mathematics curriculum. It provides a framework for modelling relationships between objects using vertices and edges, enabling us to solve problems in computer science, transportation, social networks, and beyond. This article explores the key concepts of graph theory, its algorithms, and its practical applications, all aligned with the IB syllabus.
图论是IB数学课程中最具视觉直观性但又蕴含深刻数学思想的话题之一。它通过顶点和边来建模对象之间的关系，使我们能够解决计算机科学、交通运输、社交网络等领域的问题。本文将深入探讨图论的核心概念、相关算法及其实际应用，全面对标IB考纲。
1. Basic Definitions and Terminology | 基本定义与术语
In mathematics, a graph G = (V, E) consists of a set V of vertices (or nodes) and a set E of edges (or arcs). Each edge connects a pair of vertices, and edges can be either directed or undirected. An undirected edge represents a symmetric relationship, while a directed edge indicates a one-way relationship from one vertex to another.
在数学中，图 G = (V, E) 由一组顶点（或节点）V 和一组边（或弧）E 组成。每条边连接一对顶点，边可以是有向的或无向的。无向边表示对称关系，而有向边表示从一个顶点到另一个顶点的单向关系。
A simple graph has no loops (edges connecting a vertex to itself) and no multiple edges between the same pair of vertices. A weighted graph assigns a numerical value to each edge, representing cost, distance, time, or capacity. A complete graph Kₙ has every pair of distinct vertices connected by an edge.
简单图没有环（连接顶点自身的边），同一对顶点之间也不存在多条边。赋权图为每条边赋予一个数值，代表成本、距离、时间或容量。完全图 Kₙ 中每一对不同顶点之间都有一条边相连。
The degree of a vertex is the number of edges incident to it. In a directed graph, we distinguish between in-degree (edges entering a vertex) and out-degree (edges leaving a vertex). The Handshaking Lemma states that the sum of all vertex degrees equals twice the number of edges.
顶点的度是与该顶点关联的边的数量。在有向图中，我们区分入度（进入顶点的边数）和出度（离开顶点的边数）。握手引理指出，所有顶点的度数之和等于边数的两倍。
∑deg(v) = 2 × |E|
This lemma is a powerful tool in solving problems, as it allows us to verify the consistency of degree sequences and edge counts.
该引理在解题中是一个强有力的工具，它使我们能够验证度序列与边数之间的一致性。
2. Paths, Cycles and Connectivity | 路径、回路与连通性
A path in a graph is a sequence of distinct vertices connected by edges. A trail is a walk with no repeated edges, while a circuit is a closed trail. A cycle is a closed path with no repeated vertices except the starting and ending vertex, which must be the same.
图中的路径是由边连接的互不相同顶点序列。迹是没有重复边的行走，回路是闭合的迹。回路（环）是指除起点和终点相同外，没有重复顶点的闭合路径。
A graph is connected if there exists a path between every pair of vertices. If a connected graph has n vertices and exactly n − 1 edges, it is a tree — the simplest connected structure with no cycles. Trees are fundamental in computer science and network design.
如果任意两个顶点之间都存在路径，则该图是连通的。如果一个连通图有 n 个顶点且恰好有 n − 1 条边，则它是一棵树——即没有回环的最简连通结构。树在计算机科学和网络设计中具有基础性的重要地位。
An Eulerian path traverses every edge exactly once, while a Hamiltonian path visits every vertex exactly once. A graph has an Eulerian circuit if and only if all vertices have even degree. This condition is a classic result that connects graph structure to traversability.
欧拉路径恰好经过每条边一次，而哈密顿路径恰好经过每个顶点一次。一个图存在欧拉回路的充要条件是所有顶点的度都为偶数。这一条件是将图的结构与可遍历性联系起来的经典结论。
3. Adjacency Matrices | 邻接矩阵
An adjacency matrix is a square matrix A where Aᵢⱼ = 1 if there is an edge from vertex i to vertex j, and 0 otherwise. For an undirected graph, the matrix is symmetric. For a weighted graph, Aᵢⱼ equals the weight of the edge.
邻接矩阵是一个方阵 A，其中若从顶点 i 到顶点 j 存在边，则 Aᵢⱼ = 1，否则为 0。对于无向图，该矩阵是对称的。对于赋权图，Aᵢⱼ 等于该边的权重。
One of the most powerful results is that the entry (i, j) of Aⁿ gives the number of walks of length n from vertex i to vertex j. This property is frequently tested in IB examinations and is used in problems involving counting routes or connectivity analysis.
最重要的结论之一是：Aⁿ 的第 (i, j) 项给出了从顶点 i 到顶点 j 长度为 n 的行走数量。这一性质是IB考试的常考内容，广泛用于路径计数和连通性分析问题。
For example, consider a graph representing a small transport network. The adjacency matrix can be raised to various powers to determine the number of possible routes between stations, accounting for intermediate stops.
例如，考虑一个表示小型交通网络的图。通过将邻接矩阵提升到不同次幂，可以计算站点之间可能路线的数量，计入中途停靠的情况。
4. Trees and Minimum Spanning Trees | 树与最小生成树
A spanning tree of a connected graph is a subgraph that includes all vertices and is a tree. The minimum spanning tree (MST) is the spanning tree with the smallest possible total edge weight. MSTs are essential in network design, such as laying cables or pipes with minimal cost.
连通图的生成树是包含所有顶点且为一棵树的子图。最小生成树（MST）是总边权最小的生成树。MST 在网络设计中至关重要，例如以最低成本铺设电缆或管道。
Kruskal’s algorithm is a greedy approach to finding the MST. It repeatedly selects the cheapest edge that does not create a cycle, until all vertices are connected. The correctness of this algorithm relies on the cut property of graphs.
克鲁斯卡尔算法是寻找最小生成树的贪心方法。它反复选择不会形成环的最廉价边，直至所有顶点连通。该算法的正确性依赖于图的割集性质。
Prim’s algorithm is an alternative approach that grows the tree from a starting vertex, always adding the cheapest edge connecting the tree to a vertex outside it. Both algorithms have a time complexity of O(E log V) with appropriate data structures.
普里姆算法是另一种方法，它从起始顶点开始生长树，始终添加连接树外顶点与树的最廉价边。在合适的数据结构下，两种算法的时间复杂度均为 O(E log V)。
5. Shortest Path Problems | 最短路径问题
The shortest path problem seeks the route between two vertices with the smallest total weight. This has direct applications in GPS navigation, internet routing, and logistics optimisation.
最短路径问题旨在寻找两个顶点之间总权重最小的路径。这在GPS导航、互联网路由和物流优化中有着直接的应用。
Dijkstra’s algorithm is the most well-known method for solving the single-source shortest path problem on graphs with non-negative edge weights. The algorithm maintains a set of visited vertices and updates tentative distances iteratively.
迪杰斯特拉算法是解决非负边权图中单源最短路径问题最著名的方法。该算法维护一个已访问顶点集合，并迭代更新暂定距离。
For graphs with negative weights, the Bellman-Ford algorithm must be used instead, as Dijkstra’s algorithm would fail. The Floyd-Warshall algorithm, on the other hand, finds the shortest paths between all pairs of vertices simultaneously.
对于带有负权边的图，必须使用贝尔曼-福特算法，因为迪杰斯特拉算法无法处理。而弗洛伊德-沃舍尔算法则能同时求出所有顶点对之间的最短路径。
6. Eulerian Trails and Circuits | 欧拉迹与欧拉回路
An Eulerian trail is a trail that visits every edge exactly once. A graph contains an Eulerian trail if and only if it is connected and has exactly zero or two vertices of odd degree. If there are zero odd-degree vertices, the trail is a circuit and starts and ends at the same vertex.
欧拉迹是恰好经过每条边一次的迹。一个图含有欧拉迹当且仅当它是连通的且恰好有零个或两个奇度顶点。若不存在奇度顶点，该迹即为回路，起点与终点相同。
The classic problem of the Seven Bridges of Königsberg, solved by Leonhard Euler in 1736, was the origin of graph theory. Euler proved that it was impossible to walk through the city crossing each of the seven bridges exactly once, because all four landmasses had odd degree.
1736年莱昂哈德·欧拉解决的柯尼斯堡七桥问题是图论的起源。欧拉证明了不可能穿过这座城市且恰好经过七座桥各一次，因为四块陆地都有奇度。
This concept is applied today in route planning for mail delivery, street sweeping, and garbage collection, where the goal is to traverse each street at least once with minimal backtracking.
这一概念如今应用于邮件投递、街道清扫和垃圾收集的路线规划中，其目标是以最少的重复路线经过每条街道至少一次。
7. Hamiltonian Paths and Cycles | 哈密顿路径与回路
A Hamiltonian cycle is a cycle that visits every vertex exactly once and returns to the starting vertex. Unlike the Eulerian case, there is no simple necessary and sufficient condition for the existence of a Hamiltonian cycle — this makes the problem considerably harder.
哈密顿回路是恰好访问每个顶点一次并返回起点的回路。与欧拉情形不同，哈密顿回路的存在性没有简单的充要条件——这使得该问题困难得多。
Dirac’s theorem provides a sufficient condition: if every vertex in a simple graph with n ≥ 3 vertices has degree at least n⁄2, then the graph contains a Hamiltonian cycle. Ore’s theorem generalises this result by considering the degrees of non-adjacent vertices.
迪拉克定理给出了一个充分条件：若一个具有 n ≥ 3 个顶点的简单图中每个顶点的度至少为 n⁄2，则该图包含哈密顿回路。奥勒定理通过考虑不相邻顶点的度数推广了这一结论。
The famous Traveling Salesman Problem (TSP) seeks the shortest Hamiltonian cycle in a weighted complete graph. Despite its simple statement, TSP is NP-hard, meaning no efficient algorithm is known. This problem has applications in microchip manufacturing, DNA sequencing, and delivery route optimisation.
著名的旅行商问题（TSP）是在赋权完全图中寻找最短的哈密顿回路。尽管表述简单，TSP是NP难问题，即已知没有高效算法。该问题在芯片制造、DNA测序和配送路线优化中均有应用。
8. Planar Graphs and the Four Colour Theorem | 平面图与四色定理
A planar graph is one that can be drawn in the plane without any edges crossing. The K₅ complete graph and the K₃,₃ utility graph are classic examples of non-planar graphs. Euler’s formula for planar graphs states that V − E + F = 2, where F is the number of faces.
平面图是可以在平面上绘制且没有任何边相交的图。完全图 K₅ 和公用设施图 K₃,₃ 是非平面图的经典例子。平面图的欧拉公式为 V − E + F = 2，其中 F 为面数。
The Four Colour Theorem states that any planar map can be coloured with at most four colours such that no two adjacent regions share the same colour. This was the first major theorem to be proven using a computer, in 1976 by Appel and Haken.
四色定理指出，任何平面地图最多用四种颜色着色，即可确保相邻区域颜色不同。这是第一个借助计算机证明的重要定理，由阿佩尔和哈肯于1976年完成。
This theorem has applications in mapping, scheduling, and frequency assignment in mobile networks, where overlapping coverage areas must be assigned distinct frequencies to avoid interference.
该定理在地图绘制、排课安排和移动网络频率分配中均有应用，例如必须为重叠覆盖区域分配不同频率以避免干扰。
9. Network Flows | 网络流
In a flow network, each directed edge has a capacity, and the goal is to maximise the flow from a source vertex s to a sink vertex t without exceeding any edge capacity. Flow conservation requires that, for any intermediate vertex, inflow equals outflow.
在流量网络中，每条有向边具有容量，目标是最大化从源点 s 到汇点 t 的流量，且不超过任何边的容量。流量守恒要求任意中间顶点的流入量等于流出量。
The Max-Flow Min-Cut Theorem states that the maximum flow in a network equals the total capacity of the minimum cut — the smallest-capacity set of edges whose removal disconnects s from t. This profound result links optimisation to structural analysis.
最大流最小割定理指出，网络中的最大流量等于最小割的总容量——即移除后断开 s 与 t 的最小容量边集。这一深刻结论将优化与结构分析联系起来。
The Ford-Fulkerson algorithm computes the maximum flow by repeatedly finding augmenting paths and increasing flow along them. Network flows model real-world systems such as water pipelines, electrical grids, data traffic, and transportation networks.
福特-富尔克森算法通过反复寻找增广路径并沿其增加流量来计算最大流。网络流可建模现实系统，如水管网络、电网、数据流量和交通网络。
10. Graph Colouring | 图着色
Graph colouring assigns colours to vertices such that no two adjacent vertices share the same colour. The chromatic number of a graph is the minimum number of colours required. This is a deeply studied problem with both theoretical and practical significance.
图着色是指为顶点着色，使得任意两个相邻顶点的颜色不同。图的色数是最少所需的颜色数量。这是一个在理论和实践上都具有重要意义的研究课题。
In a special case, if a graph is bipartite — meaning its vertices can be partitioned into two sets with no edges within either set — it has chromatic number 2 or 1. Bipartite graphs frequently model relationships such as jobs-to-workers or courses-to-classrooms.
特殊情况下，如果图是二分图——即顶点能被划分为两个集合，且任一集合内没有边——则其色数为 2 或 1。二分图常用于建模工作与工人、课程与教室之间的关系。
Applications of graph colouring include exam timetabling, where no student should have two exams at the same time; radio frequency assignment; and register allocation in compilers, where variables must be stored in registers without conflicts.
图着色的应用包括考试排考（任何学生不应在同一时间参加两场考试）、无线电频率分配、以及编译器中的寄存器分配（变量必须无冲突地分配至寄存器）等。
11. Real-World Applications | 实际应用
In computer networking, graph theory underlies routing protocols, network topology design, and distributed algorithms. The internet itself is a graph, where routers are vertices and connections are edges, with protocols like OSPF using shortest-path algorithms.
在计算机网络领域，图论是路由协议、网络拓扑设计和分布式算法的基础。互联网本身就是一个图，路由器是顶点、连接是边，OSPF 等协议就使用了最短路径算法。
In social network analysis, graph theory measures influence, community structure, and information spread. Connectivity metrics such as betweenness centrality identify key influencers, while clustering coefficients reveal tight-knit groups within a network.
在社交网络分析中，图论用于衡量影响力、社区结构和信息传播。介数中心性等连通性指标能识别关键影响力人物，聚类系数则揭示网络内部联系紧密的群体。
In biology, graphs model metabolic pathways, food webs, and phylogenetic relationships. In chemistry, molecular structures are represented as graphs where atoms are vertices and bonds are edges.
在生物学中，图用于建模代谢路径、食物网和系统发育关系。在化学中，分子结构表示为图，其中原子是顶点、化学键是边。
In urban planning, graph theory optimises traffic flow, public transportation networks, and emergency response routes. The use of MST algorithms minimises the cost of connecting new infrastructure while ensuring full coverage.
在城市规划中，图论优化交通流线、公共交通网络和应急响应路线。最小生成树算法在确保全覆盖的同时，最小化新基础设施的连接成本。
12. Exam Tips and Common Mistakes | 考试技巧与常见错误
When solving graph theory problems, first identify which type of graph property is being tested: connectivity, traversability, weighting, or planarity. Draw a clear diagram even if the problem seems simple — visualisation helps avoid structural mistakes.
解决图论问题时，首先要判断考查的是哪类图属性：连通性、可遍历性、赋权还是平面性。即使问题看似简单也要画清晰的图——可视化有助于避免结构性错误。
For adjacency matrix questions, remember that the (i,j) entry of Aⁿ counts walks, not simple paths. Walks may revisit vertices and edges, which is a common point of confusion. Always verify whether the question asks for walks, trails, or paths.
对于邻接矩阵题，记住 Aⁿ 的第 (i,j) 项计数的是行走而非简单路径。行走可以重复顶点和边，这是常见的混淆点。务必确认题目要求的是行走、迹还是路径。
When applying Kruskal’s algorithm, sort edges before starting and carefully check for cycle formation. When using Dijkstra’s algorithm, tick off vertices in order of finalised distance and update all neighbours after each step. Precision in these procedural details earns full marks.
应用克鲁斯卡尔算法时，先对边排序，并仔细检查是否形成环。使用迪杰斯特拉算法时，按确认距离的顺序标记顶点，并在每一步后更新所有邻居。这些程序性细节的精确性将带来满分。
Finally, practise problems from past papers and pay attention to the wording of the questions — whether they ask for a drawing, a matrix, a proof, or a calculation. Clear, step-by-step working is essential for maximising marks in exam conditions.
最后，练习历年真题并注意题目措辞——题目要求的是作图、写矩阵、证明还是计算。清晰的逐步作答过程对于在考试中最大化得分至关重要。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导