Introduction: What is Graph Theory?引言：什么是图论？

Graph Theory is a branch of mathematics studying graphs as abstract structures. It was initiated by Leonhard Euler in 1735 when he solved the famous Seven Bridges of Königsberg problem. 图论（Graph Theory）是数学的一个分支，研究图（Graph）这种数学结构。图论由瑞士数学家欧拉在1735年创立，当时他解决了著名的柯尼斯堡七桥问题。

The Seven Bridges of Königsberg柯尼斯堡七桥问题

In 18th-century Königsberg (now Kaliningrad), a river split the city with two islands and seven bridges connecting the land areas. The question: Is there a walk that crosses each bridge exactly once and returns to the start? 在18世纪的柯尼斯堡（现在的加里宁格勒），有一条河流经过城市，河中有两个小岛，总共有七座桥连接这些陆地。问题是：是否可能从某一块陆地出发，恰好经过每座桥一次，最后回到起点？

Euler’s insight:欧拉的洞察： Model each land mass as a vertex and each bridge as an edge, turning the real-world problem into a mathematical one. 将每块陆地看作一个点（顶点），每座桥看作一条线（边），这样就将实际问题转化为数学问题。

Graph theory is widely used in:图论现在广泛应用于：

  • Computer network design计算机网络设计
  • Social network analysis社交网络分析
  • Transportation route planning交通路线规划
  • Chemical molecular structures化学分子结构
  • Project management and scheduling项目管理和任务调度
  • Database design数据库设计

Basic Definitions基本定义

Graph图（Graph）

A graph G = (V, E) consists of:一个图 G = (V, E) 由以下两部分组成：

  • Vertex set V:顶点集合 V： a finite non-empty set of vertices (nodes)有限非空的顶点（节点）集合
  • Edge set E:边集合 E： the set of edges connecting vertices连接顶点的边的集合

Notation:记号： |V| = n (number of vertices)（顶点数）， |E| = m (number of edges)（边数）

Basic Terminology基本术语

  • Vertex (Node):顶点（Vertex/Node）： basic unit of a graph, often drawn as a circle图中的基本单元，通常用圆圈表示
  • Edge:边（Edge）： a line connecting two vertices, representing a relation连接两个顶点的线，表示顶点间的关系
  • Adjacent:相邻： two vertices are adjacent if they are connected by an edge如果两个顶点之间有边连接，则称它们相邻
  • Incident:关联： relation between an edge and its end vertices边与其端点之间的关系
  • Degree:度（Degree）： number of edges connected to a vertex与一个顶点相连的边的数量，deg(v)

Handshaking Lemma握手定理（Handshaking Lemma）

In any graph, the sum of all vertex degrees equals twice the number of edges:在任何图中，所有顶点的度数之和等于边数的两倍：

∑v∈V deg(v) = 2|E|

Corollary:推论： The number of odd-degree vertices in any graph is even.任何图中，度数为奇数的顶点个数必须是偶数。

Example: A Simple Graph示例：简单图

A
B
C

Graph图 G = (V, E), where:，其中：

  • V = {A, B, C}
  • E = {(A,B), (A,C), (B,C)}
  • deg(A) = deg(B) = deg(C) = 2
  • Check Handshaking Lemma:验证握手定理： 2 + 2 + 2 = 6 = 2 × 3

Graph Representations图的表示方法

1. Adjacency Matrix1. 邻接矩阵（Adjacency Matrix）

For a graph with n vertices, the adjacency matrix is an n × n matrix A where:对于有 n 个顶点的图，邻接矩阵是一个 n × n 的矩阵 A，其中：

A[i][j] = 1 if there is an edge between i and j, otherwise 0如果顶点 i 和 j 之间有边，否则为 0

Example示例

For the triangle graph above, the adjacency matrix is:对于上面的三角形图，邻接矩阵为：

ABC
A011
B101
C110

2. Adjacency List2. 邻接表（Adjacency List）

Maintain, for each vertex, a list of all its adjacent vertices.为每个顶点维护一个列表，包含与该顶点相邻的所有顶点。

Example示例

  • A: [B, C]
  • B: [A, C]
  • C: [A, B]

3. Incidence Matrix3. 关联矩阵（Incidence Matrix）

For a graph with n vertices and m edges, the incidence matrix is an n × m matrix where M[i][j] = 1 if vertex i is incident to edge j.对于有 n 个顶点和 m 条边的图，关联矩阵是 n × m 矩阵，其中 M[i][j] = 1 如果顶点 i 与边 j 关联。

Types of Graphs图的类型

Directed vs Undirected有向图与无向图

  • 无向图（Undirected Graph）：边没有方向，表示对称关系
  • 有向图（Directed Graph/Digraph）：边有方向，表示非对称关系

Visual Comparison图解对比

Undirected Graph无向图
A B C

Edges have no orientation; relations are symmetric.边没有方向，表示双向关系。

Directed Graph有向图
A B C

边有方向，表示单向关系

简单图与多重图

  • 简单图（Simple Graph）：
    • 任意两个顶点之间最多有一条边
    • 没有自环（从顶点到自己的边）
  • 多重图（Multigraph）：允许多条边连接同一对顶点
  • 伪图（Pseudograph）：既允许多重边，也允许自环

特殊图类型

  • 完全图 Kn：n 个顶点，任意两个顶点都有边连接
  • 空图 Nn：n 个顶点，没有任何边
  • 路径图 Pn：n 个顶点排成一条路径
  • 圈图 Cn：n 个顶点排成一个圈
  • 轮图 Wn：圈图 Cn 加上一个连接到所有顶点的中心顶点

特殊图类型可视化

完全图 K₄
1 2 3 4

每个顶点都与其他顶点相连

路径图 P₄
1 2 3 4

顶点排成一条直线

圈图 C₄
1 2 3 4

顶点排成一个圈

轮图 W₄
1 2 3 4 5

圈图加中心顶点

二分图 K₂,₃
A B X Y Z

两个独立集合间的连接

完全图的边数

完全图 Kn 的边数为：

|E| = C(n,2) = n(n-1)/2

例如：K4 有 6 条边，K5 有 10 条边。

Graph Connectivity图的连通性

Connectivity Definitions连通性定义

  • Connected graph:连通图： every pair of vertices has a path between them任意两个顶点之间都存在路径
  • Connected component:连通分量： a maximal connected subgraph最大的连通子图
  • Strongly connected (digraph):强连通（有向图）： there is a directed path between every pair of vertices任意两个顶点之间都存在有向路径

Connectivity Measures连通度

  • Vertex connectivity κ(G):点连通度 κ(G)： minimum number of vertices whose removal disconnects G删除最少多少个顶点可以使图不连通
  • Edge connectivity λ(G):边连通度 λ(G)： minimum number of edges whose removal disconnects G删除最少多少条边可以使图不连通
  • Relation:关系： κ(G) ≤ λ(G) ≤ δ(G)，where δ(G) is the minimum degree其中 δ(G) 是最小度数

Paths and Cycles路径和回路

Basic Definitions基本定义

  • Walk:步（Walk）： alternating sequence of vertices and edges (repetition allowed)顶点和边的交替序列，可以重复
  • Trail:迹（Trail）： walk with no repeated edges不重复边的步
  • Path:路径（Path）： walk with no repeated vertices不重复顶点的步
  • Circuit:回路（Circuit）： trail whose start and end vertices are the same起点和终点相同的迹
  • Cycle:圈（Cycle）： path whose start and end vertices are the same (except the endpoints)起点和终点相同的路径（除了起终点）

Path Length路径长度

The length of a path is the number of edges it contains. The distance between two vertices is the length of a shortest path between them.路径的长度是路径中边的数量。两点间的距离是连接它们的最短路径的长度。

Example示例

In the graph, from vertex A to vertex C:在图中，从顶点 A 到顶点 C：

  • Direct path: A → C, length 1直接路径：A → C，长度为 1
  • Indirect path: A → B → C, length 2间接路径：A → B → C，长度为 2
  • Distance d(A,C) = 1距离 d(A,C) = 1

Euler Paths and Circuits欧拉路径和回路

Euler Path and Circuit欧拉路径和回路

  • Euler trail:欧拉迹： a trail that uses every edge exactly once经过图中每条边恰好一次的迹
  • Euler circuit:欧拉回路： an Euler trail that starts and ends at the same vertex起点和终点相同的欧拉迹
  • Eulerian graph:欧拉图： a connected graph containing an Euler circuit存在欧拉回路的连通图

Euler’s Theorem欧拉定理

A connected graph has an Euler circuit iff连通图存在欧拉回路的充要条件： every vertex has even degree.图中每个顶点的度数都是偶数。

A connected graph has an Euler path iff连通图存在欧拉路径的充要条件： it has exactly 0 or 2 odd-degree vertices.图中恰好有 0 个或 2 个奇度顶点。

  • 0 odd-degree vertices: Euler circuit exists0 个奇度顶点：存在欧拉回路
  • 2 odd-degree vertices: Euler path exists2 个奇度顶点：存在欧拉路径（从一个奇度顶点到另一个）

Solution to the Seven Bridges Problem柯尼斯堡七桥问题的解答

Model the city as a graph: 4 vertices (land masses), 7 edges (bridges).将问题转化为图：4 个顶点（陆地），7 条边（桥）。

Graph model of the seven bridges柯尼斯堡七桥图模型
A B C D deg(A)=3 deg(B)=3 deg(C)=3 deg(D)=5

Degrees of each vertex:每个顶点的度数为：

  • 顶点 A：度数 3（奇数）
  • 顶点 B：度数 3（奇数）
  • 顶点 C：度数 3（奇数）
  • 顶点 D：度数 5（奇数）

结论：有 4 个奇度顶点，根据欧拉定理，不存在欧拉路径，因此无法解决七桥问题。

Hamilton Paths and Cycles哈密顿路径和回路

Hamilton Path and Cycle哈密顿路径和回路

  • Hamilton path:哈密顿路径： visits every vertex exactly once经过图中每个顶点恰好一次的路径
  • Hamilton cycle:哈密顿回路： Hamilton path that returns to the start经过每个顶点恰好一次并回到起点的路径
  • Hamiltonian graph:哈密顿图： contains a Hamilton cycle存在哈密顿回路的图

哈密顿图的判定

与欧拉图不同，判定哈密顿图没有简单的充要条件，但有一些充分条件：

Dirac's Theorem狄拉克定理（Dirac's Theorem）

Let G be a simple graph with n ≥ 3 vertices. If every vertex has degree at least n/2, then G is Hamiltonian.设 G 是有 n ≥ 3 个顶点的简单图，如果每个顶点的度数都不小于 n/2，则 G 是哈密顿图。

Ore's Theorem奥尔定理（Ore's Theorem）

Let G be a simple graph with n ≥ 3 vertices. If for any two non-adjacent vertices u and v, deg(u) + deg(v) ≥ n, then G is Hamiltonian.设 G 是有 n ≥ 3 个顶点的简单图，如果对于任意两个不相邻的顶点 u 和 v，都有 deg(u) + deg(v) ≥ n，则 G 是哈密顿图。

Traveling Salesman Problem (TSP)旅行推销员问题（TSP）

Given n cities and pairwise distances, find the shortest tour that visits each city exactly once and returns to the start. This is finding the shortest Hamilton cycle in a weighted complete graph.给定 n 个城市和城市间的距离，找到访问所有城市恰好一次并回到起点的最短路径。这本质上是在加权完全图中寻找最短哈密顿回路。

Complexity:复杂度： NP-complete; no known polynomial-time algorithm.这是一个 NP-完全问题，目前没有多项式时间算法。

Trees树

Definition of Tree树的定义

Tree: a connected, acyclic graph. The following statements are equivalent:树是连通且无圈的图。以下命题等价：

  • G is a treeG 是树
  • G is connected and acyclicG 连通且无圈
  • G is connected and |E| = |V| − 1G 连通且 |E| = |V| - 1
  • G is acyclic and |E| = |V| − 1G 无圈且 |E| = |V| - 1
  • Exactly one path between any two verticesG 中任意两个顶点间恰有一条路径

Properties of Trees树的性质

  • A tree with n vertices has exactly n − 1 edgesn 个顶点的树恰好有 n-1 条边
  • Every tree has at least two leaves (degree 1)树中至少有两个叶子节点（度数为1的顶点）
  • Removing any edge disconnects a tree删除任意一条边都会使树不连通
  • Adding any edge to a tree creates exactly one cycle添加任意一条边都会产生唯一的圈

Rooted Tree根树（Rooted Tree）

指定一个顶点作为根的树。根树具有层次结构：

  • 父节点：上一层的相邻顶点
  • 子节点：下一层的相邻顶点
  • 叶子节点：没有子节点的顶点
  • 内部节点：有子节点的顶点
  • 高度：从根到最远叶子的距离

根树示例

Root
A
B
C
D
E
F
根节点
内部节点
内部节点
叶子节点

红色：根节点 | 青色：内部节点 | 蓝色：叶子节点
高度 = 2（从根到叶子的最大距离）

二叉树

每个顶点最多有两个子节点的根树。二叉树广泛应用于：

  • 数据结构（二叉搜索树、堆）
  • 表达式解析
  • 决策树
  • 霍夫曼编码

Spanning Trees生成树

生成树

连通图 G 的生成树是包含 G 所有顶点的树形子图。

  • 包含所有 n 个顶点
  • 恰好有 n-1 条边
  • 连通且无圈

生成树的数量

凯莱公式：完全图 Kn 的生成树数量为 nn-2。

例如：K4 有 42 = 16 棵生成树。

最小生成树算法

对于加权图，寻找总权重最小的生成树：

Kruskal 算法

  1. 将所有边按权重从小到大排序
  2. 初始化森林（每个顶点为一棵树）
  3. 依次选择最小权重的边，如果不形成圈则加入
  4. 重复直到有 n-1 条边
Kruskal算法演示
原图（带权重）
A B C D 1 2 3 4

排序：1→2→3→4

选择过程
A B C D ①选择 ②选择 ③选择 ④跳过

绿色：选中 | 红色：跳过（形成圈）

最小生成树
A B C D

总权重：1+2+3=6

算法步骤：

  1. 按权重排序：1, 2, 3, 4
  2. 选择边(A,B)权重1 ✓
  3. 选择边(A,C)权重2 ✓
  4. 选择边(B,D)权重3 ✓
  5. 跳过边(C,D)权重4（会形成圈）

Prim 算法

  1. 从任意顶点开始
  2. 重复选择连接已选顶点和未选顶点的最小权重边
  3. 将新顶点加入生成树
  4. 直到包含所有顶点

Planar Graphs平面图

平面图

平面图是可以在平面上绘制且边不相交（除了在顶点处）的图。

  • 平面嵌入：图在平面上的具体绘制
  • 面：由边围成的区域，包括外部无限面

欧拉公式

对于连通平面图：V - E + F = 2

其中 V 是顶点数，E 是边数，F 是面数。

平面图的判定

库拉托夫斯基定理

图是平面图当且仅当它不包含与 K5 或 K3,3 同胚的子图。

应用：三房三井问题

三栋房子需要连接到三个公用设施（水、电、气），能否做到连线不相交？

三房三井问题图解
房1 房2 房3 水 电 气 ✗ ✗

答案：不可能。这等价于判断完全二分图 K3,3 是否为平面图，根据库拉托夫斯基定理，K3,3 不是平面图。

红色：房子 | 青色：公用设施 | ✗：不可避免的交叉点

Graph Coloring图的着色

图着色

图的着色是为图的顶点分配颜色，使得相邻顶点有不同颜色。

  • 色数 χ(G)：给图 G 着色所需的最少颜色数
  • k-着色：使用最多 k 种颜色的着色

著色的性质

  • χ(Kn) = n（完全图需要 n 种颜色）
  • χ(Cn) = 3（n ≥ 3 且 n 为奇数），χ(Cn) = 2（n 为偶数）
  • χ(G) ≤ Δ(G) + 1，其中 Δ(G) 是最大度数

四色定理

任何平面图都可以用最多四种颜色进行顶点着色。

这是第一个通过计算机辅助证明的重要数学定理（1976年）。

着色问题的应用

  • 地图着色：为地图上的区域着色使相邻区域颜色不同
  • 课程安排：为课程安排时间段，冲突课程不能同时
  • 寄存器分配：编译器中的寄存器分配优化
  • 频率分配：无线电频率分配避免干扰

Bipartite Graphs二分图

二分图

二分图是顶点集可以分为两个不相交集合的图，使得每条边的两个端点分别在不同集合中。

记作 G = (X ∪ Y, E)，其中 X ∩ Y = ∅，每条边连接 X 中的顶点和 Y 中的顶点。

二分图的判定

图是二分图当且仅当它不包含奇长度的圈。

算法：使用 BFS 或 DFS 进行 2-着色，如果成功则是二分图。

完全二分图

完全二分图 Km,n：一个集合有 m 个顶点，另一个集合有 n 个顶点，任意两个不同集合的顶点都有边连接。

  • 顶点数：m + n
  • 边数：m × n
  • 每个 X 中的顶点度数为 n
  • 每个 Y 中的顶点度数为 m

匹配理论

匹配：边的集合，其中任意两条边都不共享顶点。

霍尔定理（Hall's Theorem）

二分图 G = (X ∪ Y, E) 存在饱和 X 的匹配当且仅当对于 X 的任意子集 S，都有 |N(S)| ≥ |S|，其中 N(S) 是 S 的邻域。

应用：工作分配问题

有 n 个工人和 m 个工作，每个工人只能胜任某些工作。能否给每个工人分配一个工作？

建模为二分图匹配问题，使用霍尔定理或匈牙利算法求解。

Graph Algorithms图的算法

图的遍历算法

深度优先搜索（DFS）

  1. 从起始顶点开始
  2. 尽可能深地访问邻接的未访问顶点
  3. 当无法继续时，回溯到上一个顶点
  4. 重复直到所有可达顶点都被访问
DFS 执行步骤演示
图结构
A B C D

连接关系：A-B, A-C, B-D

DFS访问过程
A B C D ① ② ③ ④

访问序列：A→B→D→C（深度优先）

DFS步骤：

  1. 从A开始，标记A为已访问
  2. 访问A的邻居B，标记B为已访问
  3. 访问B的邻居D，标记D为已访问
  4. D无未访问邻居，回溯到A，访问C

特点：尽可能深地探索每个分支

应用：连通性检测、拓扑排序、强连通分量

广度优先搜索（BFS）

  1. 从起始顶点开始，加入队列
  2. 从队列中取出顶点，访问其所有未访问的邻居
  3. 将新访问的顶点加入队列
  4. 重复直到队列为空
BFS 执行步骤演示
图结构
A B C D

连接关系：A-B, A-C, B-D

BFS访问过程
A B C D 层0 层1 层2

访问序列：A→B,C→D（广度优先）

BFS步骤：

  1. 从A开始，将A加入队列：[A]
  2. 访问A，将其邻居B,C加入队列：[B,C]
  3. 访问B，将其邻居D加入队列：[C,D]
  4. 访问C，访问D，队列为空，结束

特点：按层级逐步扩展，适合寻找最短路径

应用：最短路径（无权图）、层次遍历

最短路径算法

Dijkstra 算法

适用：非负权重的加权图，单源最短路径

  1. 初始化：起点距离为0，其他为∞
  2. 选择距离最小的未访问顶点
  3. 更新其邻居的距离
  4. 重复直到所有顶点被访问

时间复杂度：O((V + E) log V)（使用优先队列）

Floyd-Warshall 算法

适用：所有顶点对之间的最短路径

使用动态规划，考虑是否经过中间顶点k能缩短路径：

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

时间复杂度：O(V³)

图算法可视化

在实际应用中，图算法常用于：

  • 网络路由
    使用最短路径算法优化数据传输
  • 社交网络分析
    找到影响力最大的用户、社区检测
  • 地图导航
    GPS导航中的最短路径规划
  • 推荐系统
    基于图的协同过滤算法

总结

图论是一个丰富而实用的数学分支，其核心概念包括：

  • 基础概念：图、顶点、边、度数、连通性
  • 特殊图类：树、二分图、平面图、完全图
  • 路径理论：欧拉路径、哈密顿路径、最短路径
  • 算法应用：图遍历、最小生成树、图着色、匹配

掌握这些概念和算法，能够解决网络、调度、优化等众多实际问题。