图论简明索引

0. 前言

图论作为计算机专业离散数学系列课程的重要一环，在本科时我就上过一学期的课程。研究生刚好碰到机会重新速览了一遍图论，在此做一个笔记，叫做简明索引。简明是因为内容浅尝辄止，只涉及到最基本的概念和最常见的问题，我认为可以看作是算法和数据结构知识的理论导引；索引是因为这里只是概念、问题和解决方案的罗列，省去了严格的证明，甚至对于（我认为）常见的、著名的算法，也略去不表。

我以这样的方式来组织这个索引：概念定义(Concept Definition)和问题(Problem)。这也和图论的历史发展和课程组织有关，它们往往是问题驱动的，从一个非常实际的问题出发，抽象出概念，然后从数学上解决，最终又应用于实际。这也是为什么图在算法和数据结构里面占据非常重要的地位，因为其对客观事物的抽象涵盖得太广，应用得太广。

1.概念

1.1 图的基本概念

图将客观事物抽象成节点，将事物间的关系抽象成边。

Definition 1.1.1 (图) 图 \(G\) 由非空结点集合 \(V=\{v_1,v_2,...,v_n\}\) 和边集合 \(E=\{e_1,e_2,...,e_m\}\) 组成，其中每条边可用一个结点对表示，即 \(e_i=(v_{i1},v_{i2}),i=1,2,...,m\) . 这样的一个图 \(G\) 可表示为 \(G=<V,E>\) .

由这个定义我们引出一系列术语：

有向边和无向边：若表示边的节点对是有序对，则称该边是有向边；若是无序对，则称该边是无向边。
有向图和无向图：若图的所有边都是有向边，则称该图为有向图；若所有边都是无向边，则称该图为无向图。
关联：称边与表示其的节点对中的每个节点相关联。
邻接：称关联于同一条边的两个节点相邻接；称关联于同一个节点的两条边相邻接。
环：称两端关联于同一节点的边为环。
孤立点：称不与任何节点邻接的节点为孤立点。

Definition 1.1.2 (子图) 两个图 \(G=<V,E>,G\'=<V\',E\'>\) 如果满足 \(V\'\subseteq V, E\'\subseteq E\) , 则称 \(G\'\) 是 \(G\) 的子图。如果 \(V\'\subset V, E\'\subset E\) ，则称 \(G\'\) 是 \(G\) 的真子图。如果 \(V\'=V, E\'\subseteq E\) ，则称 \(G\'\) 是 \(G\) 的生成子图。

Definition 1.1.3 (图的同构) 两个图 \(G=<V,E>,G\'=<V\',E\'>\) ，如果他们的节点间存在一一映射，且该映射也反映在表示边的节点对中，则称两图是同构的。

Definition 1.1.4 (节点的度) 在有向图中，以节点 \(v\) 为起点的边的条数称为 \(v\) 的出度；以 \(v\) 为终点的边的条数称为 \(v\) 的入度；入度与出度之和称为度。在无向图中，与 \(v\) 关联的边的条数称为度。

1.2 图的分类

除1.1中按边的类型可将图分为有向图和无向图外，我们还可以按照其他标准对图进行分类：

多重图和简单图：如果一个节点对对应多条边，则称这些边为多重边。包含多重边的图称为多重图；不包含多重边的图称为简单图。
有权图和无权图：如果图中的边附有权值，则称该图为有权图；否则称为无权图。

1.3 通路与回路

路是一组比较容易混淆的概念，是否允许重复边，是否允许重复节点，需要辨析清楚，因为有一系列的问题其实就是在探讨符合某种特殊要求的路是否存在，如果存在怎么求。

Definition 1.3.1 (通路) 在图 \(G=<V,E>\) 种，边序列 \((v_0,v_1),(v_1,v_2),(v_2,v_3),...,(v_{k-1},v_k)\) 称作一条通路，简记作 \((v_0,v_1,...,v_k)\) 。

对应地，针对上述定义也延伸出一系列术语：

起点和终点： \(v_0\) 称作通路的起点， \(v_k\) 称作通路的终点。
长度：通路中边的数目称为通路的长度。

对于普通的通路而言，我们对其中的边和点的重复性没有任何限制。为引出这些限制，我们特别定义：

简单通路：没有重复边的通路称为简单通路。
基本通路：没有重复节点的通路称为基本通路。

基本通路一定是简单通路，反之不成立。

Definition 1.3.2 (回路) 起点和终点相同的通路称为回路。

同样，普通的回路对边和点没有重复性的要求，我们特别定义：

简单回路：没有重复边的回路称为简单回路。
基本回路：除起点和终点外没有重复点的回路称为基本回路。

特别地，我们除了一些重复性要求外，还关注着路对于图的遍历性质，比如走遍图的每个点或每条边。寻找这些有趣的性质的路则催生了一系列的问题。

Definition 1.3.3 (欧拉通路) 如果一个通路通过 \(G\) 中的每条边恰好一次，称该通路为欧拉通路。

欧拉通路其实就是遍历所有边的简单通路。特别地，如果一个欧拉通路恰好是一个回路，那么称其为欧拉回路。存在欧拉回路的图叫欧拉图。

Definition 1.3.4 (汉密尔顿通路) 如果一个通路通过 \(G\) 中的每个节点恰好一次，称该通路为汉密尔顿通路。

汉密尔顿通路其实就是遍历左右节点的基本通路，且注意汉密尔顿通路不需要经过所有的边。特别地，如果一个汉密尔顿通路恰好是一个回路（起点/终点认为只经过一次），那么称其为汉密尔顿回路。存在汉密尔顿回路的图叫汉密尔顿图。

1.4 连通性

Definition 1.4.1 (可达性) 从节点 \(v_i\) 到节点 \(v_j\) 间如果存在一条通路，则称从 \(v_i\) 到 \(v_j\) 是可达的。

Definition 1.4.2 (连通性) 如果图的任意两点间可达，则称该图为连通图，否则称为非连通图。

对于无向图来说，连通性的概念比较简单，而对于有向图，由于可达性本身是有方向的，连通性则根据其方向也可以具体分为不同的连通程度。

强连通：任何两节点间双向可达。
单向连通：任何两节点间至少一个方向可达。
弱连通：任何两节点间只有忽略了所有边的方向性才可达。

无向图中的连通性可以看作是节点的一个等价类划分。

同样连通的图，脆弱性（或说健壮性）还有区别，这种脆弱性体现在一些关键的节点或边上。

Definition 1.4.3 (割点) 若删去一个点后，图的连通分支数增加，则称该点为图的一个割点

Definition 1.4.4 (点割集) 若删去一个点集后，图的连通分支数增加，则称该点集为图的一个点割集。含有k割顶点的点割集称为k-点割集。若该点集中减少任何一个点都不再是点割集，则称其为极小点割集。图中含点数最少的点割集称为图的最小点割集

Definition 1.4.5 (连通度) 一个图的连通度定义为最小点割集的点的个数。即最少需要去掉多少个点才能增加连通分支的个数

同样的，割边、边割集、边连通度的定义类似。

1.5 树

Definition 1.5.1 (树) 无回路的连通图称为树。

对于无回路的非联通图，每个连通分支可以看作一个树，因此称为森林。

树中度为1的节点称为叶节点，度大于1的节点称为分支结点。

对于树，有非常多的等价表述

Theorem 1.5.1 对于图 \(G=<V,E>, |V|=n, |E|=m\) 下面的命题互相等价：

\(G\) 是树 ( \(G\) 连通且无回路)

\(G\) 的每对节点间恰有一条基本通路

\(G\) 连通且 \(m=n-1\)

\(G\) 无回路且 \(m=n-1\)

\(G\) 连通且 \(G\) 的每一条边都是割边

\(G\) 无回路且在\(G\) 的任何不邻接的节点之间加上一条边，则恰形成一个回路

\(G\) 连通且\(G\) 的每个度大于1的节点都是割点

上面定义的树并没有根的概念，但一般我们会引入根以及节点之间的层级关系(亲子关系)。

Definition 1.5.2 (有向树) 有向图形成的树称为有向树。

Definition 1.5.3 (外向树) 满足以下条件的有向树 \(T\) 称为外向树：

\(T\) 有且只有一个入度为0的节点，称为\(T\) 的根

\(T\) 的其他节点入度均为1

\(T\) 中出度为0的节点称为叶节点

随之而来的还有其他的术语，例如树的高度，节点的深度，二叉树，完全树等，这里略。

1.6 二分图

Definition 1.6.1 (二分图) 设无向图 \(G=<V,E>\) 中， \(V\) 的两个非空子集 \(V_1, V_2\) 满足

\(V_1\cap V_2=\empty, V_1\cup V_2=V\)

\(\forall e=(v_i,v_j)\in E, v_i\in V_1, v_j\in V_2\)

则称 \(G\) 为二分图。

如果 \(E=V_1\times V_2\) ，则称 \(G\) 为完全二分图，记作 \(K_{|V_1|,|V_2|}\) 。

很多二分图长得并不像二分图，例如节点数大于1的树就是二分图，其奇数层和偶数层节点形成了划分。那么有没有更直接的办法判断一个图是不是二分图呢？

Theorem 1.6.1 (二分图的充要条件) 图 \(G\) 是二分图充分必要条件是 \(G\) 的所有回路长度是偶数。

二分图的应用问题往往涉及到另一概念，二分图的匹配。

Definition 1.6.2 (匹配) 设 \(G=<V,E>\) 是二分图， \(V_1, V_2\) 是两个互补的节点集合， \(V_1=\{v_1,...,v_k\}\) ，若 \(V_2\) 存在 \(k\) 个不同的节点 \(\{v_1\',...,v_k\'\}\subseteq V_2\) ，使得边 \((v_i,v_i\')\in E (i=1,...,k)\) ，则称 \(E\'=\{(v_1,v_1\'),...,(v_k,v_k\')\}\subseteq E\) 是 \(V_1\) 到 \(V_2\) 的一个匹配。特别地，如果有 \(|V_1|=|V_2|\) ，则该匹配称为完美匹配。

1.7 平面图

Definition 1.7.1 (平面图) 一个图可以画在平面上并且使得不同的边互不交叠，那么称该图为平面图；否则称为非平面图。

\(K_5\) ，\(K_{3,3}\) 是最重要的非平面图，证明略。

Definition 1.7.2 (平面图的面) 设 \(G\) 是平面图，则 \(G\) 把整个平面划分成若干区域，这些区域称为 \(G\) 的平面 (也称为域)。其中面积无限的面称为无限面或外部面，其余的称为有限面或内部面。面的集合一般表示为 \(F\) .

对平面图 \(G\) 的每一个面 \(f\in F\) ，围绕 \(f\) 的边界所构成的闭路长度称为面 \(f\) 的度，记作 \(d(f)\) .

关于平面图最重要的结论就是欧拉公式

Theorem 1.7.1 (欧拉公式) 设 \(G=<V,E>\) 是连通平面图，其中 \(|V|=n,|E|=m,|F|=r\) 则 \(n-m+r=2\) .

由欧拉公式我们可以得到两个关于平面图的性质，若 \(G\) 是连通平面图\(|V|=n,|E|=m\) ：

若 \(n\ge 3\) ，则 \(m\le 3n-6\)
若 \(G\) 无环无多重边，则 \(min_{v\in V} d(v) \lt 5\)

Definition 1.7.3 (同胚) 设 \(G_1,G_2\) 是两个图，若 \(G_1,G_2\) 在增加或忽略一些次数为2的点后同构，则称 \(G_1,G_2\) 同胚

Definition 1.7.4 (对偶图) 给定平面图 \(G=<V,E>\) 具有面 \(F=\{f_1,...,f_n\}\) ，若有图 \(G^*=<V^*,E^*>\) 满足下面的条件：

对于 \(G\) 的任意面 \(f_i\) 的内部有且仅有一个节点 \(v_i^*\in V^*\)

对于 \(G\) 的面 \(f_i,f_j\) 的公共边界 \(e_k\) ，有且仅有一条边 \(e_k^*\in E^*\) ，使得 \(e_k^*=(v_i^*,v_j^*)\) ，且 \(e_k^*\) 与 \(e_k\) 相交. (\(v_i^*\) 在 \(f_i\) 内，\(v_j^*\) 在 \(f_j\) 内)

当且仅当 \(e_k\) 只是一个面 \(f_i\) 的边界时， \(v_i^*\) 上有且仅有一个环 \(e_k^*\in E^*\) 且与 \(e_k\) 相交

则称 \(G^*\) 是 \(G\) 的对偶图

对偶图其实就是把平面图的面作为节点构造出来的，它具有以下特征

任何平面图的对偶图必然是连通图
平面图的对偶图也是平面图

1.8 有向无环图

Definition 1.8.1 (DAG) 无环的有向图称为有向无环图，简称DAG

Definition 1.8.2 (AOV，AOE) 用顶点表示活动，用弧表示活动间优先关系的有向图称为Activity On Vertex network (AOV网)；用带权边表示活动的则称为Activity On Edge network (AOE网)

Definition 1.8.3 (关键路径AOE) AOE网表达的活动完成的整个实践取决于从源点到汇点的最长路径长度，该长度最长的路径叫做关键路径

1.9 网络流

Definition 1.9.1 (网络流图) 设 \(G=<V,E>\) 是一个带权有向图，称其为网络流图，如果其满足以下条件：

仅有一个入度为0的顶点 \(s\) ，称为源点或出发点

仅有一个出度为0的顶点 \(t\) ，称为汇点或结束点

每条边 \((u,v)\in E\) 有一个非负权值 \(c(u,v)\) ，称为该边的容量

网络流图来源于实际问题中的网络流，因此也有一系列与实际对应非常强烈的术语：

流量：流网络的每条边上给定一个实数 \(0\le f(u,v) \le c(u,v)\) ，称为该边上的流量
饱和：满足 \(f(u,v)=c(u,v)\) 的边称为饱和边
可行流：如果有一组流量满足条件：(1) 源点的流出量=汇点的流入量=整个网络的流量 (2) 每个中间点的流入量等于流出量；那么该组流量称为整个网络的一个可行流
最大流：所有可行流中，总流量最大的一个流叫做最大流
割：流网络中顶点的一个划分称为割，如果源点和汇点分属两个划分出的点集，记作 \(CUT(S,T)\)
正向割边，逆向割边：在割 \(CUT(S,T)\) 中，从 \(S\) 的某点到 \(T\) 的某点的边称为正向割边，反之称为逆向割边
割的容量：割中所有正向割边的容量之和

Definition 1.9.2 (残留网络) 给定一个流网络 \(G\) 及其上的流量 \(f\) ，网络 \(G\) 关于 \(f\) 的残留网络 \(G^*\) 与 \(G\) 有相同的顶点集，而网络 \(G\) 中的每一条边对应于 \(G^*\) 中的1条边或2条边：设 \((v,w)\) 是 \(G\) 的一条边，则

若 \(f(v,w) \gt 0\) ，则 \((w,v)\) 是 \(G^*\) 中的一条边，该边的容量为 \(c^*(w,v)=f(u,v)\)

若 \(f(v,w)\lt c(u,v)\) ，则 \((v,w)\) 是 \(G^*\) 中的一条边，该边的容量为 \(c^*(v,w)=c(v,w)-f(v,w)\)

残留网络中的术语：

增广路径：从源点到汇点的一条简单路径称为增广路径
正向边，逆向边：方向与增广路径一致，称该边为正向边，反之称为逆向边

2. 问题

2.1 一笔画问题 (欧拉图)

一笔画问题被抽象为寻找欧拉回路的问题。

Problem 2.1 (一笔画问题) 给定无向连通图 \(G\) ，判断 \(G\) 是否为欧拉图。若是，找出一条欧拉回路。

该问题已经从图论的角度彻底解决，首先我们解决存在性。

Theorem 2.1.1 (欧拉回路的存在性) 无向连通图 \(G\) 是欧拉图的充分必要条件是 \(G\) 的每个顶点的度都是偶数。

找到一条欧拉回路的算法也已经被发现。

Theorem 2.1.2 (欧拉回路的构造算法; Fleury算法) 从任一节点出发，反复地根据下面的条件从未经过的边集合中选取边：

与当前节点关联。

除非无别的边可选，否则不选取使得经过的边集成为割的边；如果选了这样的边，则算法终止。

一个简单的推论是两不同节点间存在欧拉通路的充分必要条件是这两个节点的度为基数，其余节点的度为偶数。这个问题可通过在两节点之间加一条边化归为一笔画问题。

2.2 中国邮递员问题

Problem 2.2 (中国邮递员问题) 给定非负有权无向连通图 \(G\) ，找到一条回路 \(C\) ，使其通过每条边最少一次，且权值和最小。

该问题是一笔画问题的扩展。如果图是欧拉图，则欧拉回路就是最优回路。

如果不存在欧拉回路，则其中必存在有奇数度的节点，且这类的节点一定大于等于2个。因此有些边需要再重复一次，使奇数边的端点变为偶数边的节点。

管梅谷首次提出基于上述想法的奇偶点图上作业法(1962), Edmonds Johnson给出复杂度为 \(O(|V|^2|E|)\) 的有效算法，这里略去。

2.3 汉密尔顿图问题

Problem 2.3 (汉密尔顿图) 给定无向连通图 \(G\) ，判断 \(G\) 是否为汉密尔顿图。若是，找出一条汉密尔顿回路。

目前汉密尔顿回路的存在性还没有得到有效的充分必要条件，且已经证明该问题是一个NP-hard问题。但是有非常多的相关定理给出一些充分条件或必要条件，这里略去。

2.4 旅行售货员问题 (TSP)

Problem 2.4 (Traveling Salesman Problem) 在非负加权无向完全图中求最短长度的汉密尔顿圈。

该问题是汉密尔顿图问题的扩展。该问题同样是NP-hard问题。

2.5 图的遍历问题

Problem 2.5 (图的遍历) 给定连通图 \(G\) 和出发点 \(v\) ，访遍图中所有的顶点，且每个顶点只访问一次。

分为深度优先遍历(DFS)和广度优先遍历(BFS)，在图的搜索算法中还有基于启发式的遍历方法，但是基本思想都可以归类到DFS或BFS。具体算法略。

2.6 图的表示

总的来说，图在数据结构里有邻接矩阵，邻接表等。邻接矩阵虽然从存储的角度来看效率并不高，但是在数学的角度上看有很多有趣的性质。例如，对角线可以判断环是否存在， \(l\) 次幂的对角线可以判断 \(l\) 长通路/回路的个数，行和/列和可以计算出度/入度，可达性矩阵等。

还有其他的矩阵可以刻画图，例如：

关联矩阵：与邻接矩阵等价，刻画点与边之间的关联关系。
拉普拉斯矩阵： \(L=D-W\) ，其中 \(D\) 是图的度矩阵（对角矩阵，对角线上的元素是节点的度）， \(W\) 是图的邻接矩阵。
相似矩阵：任意两点之间的权重值组成的矩阵，权重来源于距离度量，有\(\epsilon\) 邻近法， \(K\) 邻近法和全连接法。可以选择不同的核函数定义权重，最常见的是全连接+高斯径向核RBF。

2.7 树的遍历问题

图的遍历在树上的特化，这里延伸出了先序、中序、后序三种遍历手段，略。

2.8 最小生成树问题

Problem 2.8 (最小生成树问题) 在带权连通图中求权值和最小的生成树

两个方向的贪心算法：加边，破圈。

2.9 二分图的匹配问题

Problem 2.9 (二分图的匹配问题) 给定二分图 \(G\) ，找出其中的一个最大匹配

匹配的存在性是一个重要的课题，这里给出一个充分必要条件和一个充分条件。

Theorem 2.9.1 (匹配存在的充要条件) 二分图 \(G\) 中存在从 \(V_1\) 到 \(V_2\) 的匹配，当且仅当 \(V_1\) 中任意 \(K\) 个顶点与 \(V_2\) 中的 \(K\) 个顶点都相邻，其中 \(K=1,2,...,|V_1|\) .

Theorem 2.9.2 (匹配存在的充分条件) 二分图 \(G\) 如果存在正整数 \(t\) 满足：

\(\forall v\in V_1, d(v)\ge t\)

\(\forall v\in V_2, d(v) \le t\)

则 \(G\) 中存在 \(V_1\) 到 \(V_2\) 的匹配。

匹配的存在性解决后，则是寻找匹配的算法，即匈牙利算法，此处略。

2.10 图的平面性判定问题

Problem 2.10 (图的平面性判定问题) 判断一个连通图是否是平面图

理论上有一个充要条件，但是实际应用困难

Theorem 2.10.1 (平面性的充要条件；Kuratowski定理) 一个图是非平面图当且仅当它包含与 \(K_5\) 或者 \(K_{3,3}\) 同胚的子图

实际操作起来，我们先进行一些预处理：

若 \(G\) 非连通，只需检验每个连通分支
若 \(G\) 中存在割点 \(v\) ，可把 \(G\) 从割点处分离，构成若干个不含割点的连通子图，称为块。 \(G\) 是平面图当且仅当每个块是平面图
移去环和重边
“消去”度为2的节点

经过这一系列预处理后：

若 \(m \lt 9\) 或 \(n \le 5\) ，则 \(G\) 是平面图
若 \(m \gt 3n-6\) ，则 \(G\) 是非平面图
否则用DMP算法进一步判断

DMP算法此处略。

2.11 最短路径问题

Problem 2.11 (最短路径问题) 求带权连通图中任意两点之间的最短路径。

对于权值非负的连通图，运用Dijkstra算法。

对于一般的图，运用Bellman-Ford算法。

2.12 拓扑排序问题

Problem 2.12 (拓扑排序问题) 给定有向无环图 \(G=<V,E>\) ，找到一个顶点序列，使得 \(\forall e=(u,v)\in E\) ， \(u\) 在序列中的位置先于 \(v\)

拓扑排序可以由贪心算法完成，反复选择入度为0的顶点并删除之。

2.13 最大流问题

Problem 2.13 (最大流问题) 给定流网络 \(G\) ，找到一个最大可行流

最大流问题的理论依据是最大流定理

Theorem 2.13.1 (最大流定理) 可行流 \(f\) 为最大流，当且仅当不存在关于 \(f\) 的增广路径

根据最大流定理可设计出一个最基本的求最大流的方法 (Ford-Fulkerson方法)：

初始时将 \(f\) 设置为零流
构建残留网络，寻找增广路径增广，再修改残留网络，重复此过程直至无法找到增广路径

2.14 最小割问题

Problem 2.14 (最小割问题) 给定流网络 \(G\) ，找到一个容量最小的割

该问题的求解涉及到割与流的关系

Theorem 2.14.1 若 \(f\) 是流网络的一个流， \(CUT(S,T)\) 是任意一个割，那么 \(f\) 的值等于正向割边的流量与负向割边的流量之差

该定理的推论：网络的任何流不超过任何割的容量。

进一步地，

Theorem 2.14.2 在任何网络中，如果 \(f\) 是一个流， \(CUT(S,T)\) 是一个割，且 \(f\) 的值等于 \(CUT(S,T)\) 的容量，那么 \(f\) 是一个最大流，且 \(CUT(S,T)\) 是一个最小割

Theorem 2.14.3 (最大流最小割定理) 在任何网络中，最大流的值等于最小割的容量

秒客网