图论基础

图论基础概念

有限图：顶点数和边数有限的图称为有限图。
平凡图：只有一个顶点的图。
零图：一个没有边的图被称为零图。
n阶图：顶点数为n的图。
$(n,m)$图：顶点数为 𝑛 的图，边数为 𝑚 的图
边的重数：连接两个相同顶点的边的条数
环：端点重合为一点的边
简单图：无环无重边的图；其余的图称为复合图
顶点 𝑢 与 𝑣 相邻接
- 顶点 𝑢 与 𝑣 间有边相连接
- 𝑢 与 𝑣 称为边的两个端点
- 通常规定一个顶点与自身是邻接的
顶点 𝑢 与边 𝑒 相关联：顶点 𝑢 是边 𝑒 的端点
边 $e_1$与边 $e_2$相邻接：边 $e_1$ 与边 $e_2$ 有公共端点
途径：有限非空序列 $ w = v_0e_1v_1e_2v_2 \ldots e_kv_k $，$ e_i $ 端点 $ v_{i-1}, v_i $。途径长度为边数；$ v_0, v_k $ 分别为起点终点。
迹：边不重复的途径。
路：顶点不重复的途径。
闭途径、闭迹与圈：起点终点重合的途径、迹、路。闭迹也称为回路。长度为 $ k $ 的圈称为$k$圈，$𝑘$ 为奇数（偶数）时称为奇（偶）圈
顶点间距离：$ u, v $ 间最短路长度 $ d(u, v) $。
顶点间的连通性：$ u, v $ 间存在途径。
连通图：连通图中任意两点连通。若图 $ G $ 不连通，则其补图连通。
连通分支：非连通图极大连通部分。连通分支个数，称为分支数。
图的直径：$ d(G) = \max \{d(u, v) | u, v \in V \}$。

Peterson图

Peterson图是K5的线图的补图。Petersen图的同构多种多样，其自同构有120种。

图同构

同构图：顶点数相同，边数相同，结构相同

数学定义： 两个图 $ G_1 = (V_1, E_1) $ 和 $ G_2 = (V_2, E_2) $ 是同构的，如果存在一个双射 $ f: V_1 \rightarrow V_2 $，使得对于所有 $ u, v \in V_1 $，$ (u, v) \in E_1 $ 当且仅当 $ (f(u), f(v)) \in E_2 $。且 $xy$ 和 $m(x)m(y)$ 重数相同，称$G_1, G_2$ 同构。关键在于找到这个双射。

几种典型的图

完全图

$n$个顶点的完全图：$n$阶完全图，用$K_n$表示

$𝐾_𝑛$ 的边数为 $\frac{n(n-1)}{2}$

偶图

点集可以分解为两个子集 $𝑋$ 和 $𝑌$，使得每条边的一个端点在 $𝑋$ 中，另一个在 $𝑌$ 中

性质：

偶图中没有环与三角形，可以有重边。
完全偶图：$𝑋 (𝑌)$ 的每个顶点与 $𝑌 (𝑋)$ 的每个顶点相连，任取 $𝑋, 𝑌$ 中各一点均有边相连
$k$正则偶图：每个顶点度数均为$k$，$k$正则偶图的两个顶点子集包含顶点个数相等。

补图

$对于一个简单图 G=(V, E) , 令集合 E_{1}=\{u v \mid u \neq v, u, v \in V\} 称图 H=\left(V, E_{1} \backslash E\right) 为 G 的补图$

注意：

只有简单图才能定义补图
图和其补图顶点集合相同
任意一对顶点相邻的充分必要条件是它们在补图中不相邻
𝑛 阶简单图边数与其补图边数之和等于 $𝐾_𝑛$ 的边数 $\frac{n(n-1)}{2}$

自补图

如果 𝐺 与其补图同构，则称 𝐺 为自补图。并不是任意一个简单图都是自补图

定理

$若 𝑛 阶图 𝐺 是自补图，则有 𝑛 = 4𝑘 或 4𝑘 + 1$

利用 𝑛 阶图边数与其补图边数之和为 $𝐾_𝑛$ 的边数

顶点的度

顶点度：在图 $ G $ 中，顶点 $ v $ 的度 $ d(v) $ 是指与 $ v $ 关联的边的数目。

握手定理

握手定理：

$任意图中所有顶点的度的和等于边数的 2 倍$

推论：

任何图中，奇点个数为偶数
正则图的阶数和度数不同时为奇数

图的度序列

图 $G$ 的各个点的度 $d_1, d_2, \ldots, d_n$ 构成的递增非负整数组 $(d_1, d_2, \ldots, d_n)$ 称为 $G$ 的度序列。

一个图的度序列与序列中元素排列无关。
每个图对应唯一一个度序列。
同构的图具有相同的度序列。

度序列判别定理

定理：

非负整数组 $(d_1, d_2, \ldots, d_n)$ 是图的度序列的充分必要条件是该序列中元素的总和为偶数。

充分性：构造对应度序列的图

数组中为奇数的数字个数必为偶数

若 $𝑑_i$ 为偶数，则在与之对应的点作 $\frac{𝑑_𝑖}{2}$ 个环

对于剩下的偶数个奇数，两两配对后分别在每配对点间先连一条边，然后在每个顶点做环

必要性：握手定理得到，一个图的度数和为偶数。

图序列

一个非负整数组如果是某简单图的度序列，我们称它为可图序列，简称图序列

存在问题：什么样的非负整数组是图序列？(彻底解决)
计数问题：一个图序列对应多少不同构的图？（解决的不好）
构造问题：如何画出图序列对应的所有不同构图？（没有解决）

图序列判别定理（Havel-Hakimi 定理）

定理：

给定一个非负整数序列 $(d_1, d_2, \ldots, d_n)$，其中 $d_1 \geq d_2 \geq \ldots \geq d_n$，则该序列是图序列的充分必要条件是：对于序列 $(d_2 - 1, d_3 - 1, \ldots, d_{d_1+1} - 1, d_{d_1+2}, \ldots, d_n)$，它也是一个图序列。

度的性质

定理：

$一个简单图 𝐺 的 n 个点的度不能互不相同，也就是必有两个点度数相等$

证明：鸽笼原理

情形 1：图 $G$ 没有孤立点

在没有孤立点的情况下，每个顶点的度数 $d(v)$ 必须满足 $1 \leq d(v) \leq n - 1$。

根据鸽笼原理，由于有 $n$ 个顶点和 $n - 1$ 个可能的度数，至少有两个顶点的度数相同。

情形 2：图 $G$ 只有一个孤立点

假设 $G_1$ 是图 $G$ 去掉孤立点后的部分。

在 $G_1$ 中，每个非孤立顶点的度数 $d(v)$ 满足 $1 \leq d(v) \leq n - 2$。

同样根据鸽笼原理，由于 $G_1$ 有 $n - 1$ 个顶点和 $n - 2$ 个可能的度数，至少有两个顶点的度数相同。

情形 3：图 $G$ 有两个以上的孤立点

如果图 $G$ 有两个或更多的孤立点，那么在这些孤立点之间不存在边。

在这种情况下，定理显然成立，因为孤立点的度数为 0，而其他非孤立点的度数至少为 1。

因此，至少有两个顶点的度数相同（即，孤立点的度数相同）。

子图

如果图 $ H $ 的顶点集 $ V(H) $ 是图 $ G $ 的顶点集 $ V(G) $ 的子集，并且 $ H $ 的边集 $ E(H) $ 是 $ G $ 的边集 $ E(G) $ 的子集，则称 $ H $ 为 $ G $ 的子图，记为 $ H \subseteq G $。

如果 $ H $ 不等于 $ G $，则称 $ H $ 为 $ G $ 的真子图。

点导出子图：

对于 $ V’ \subseteq V(G) $，以 $ V’ $ 为顶点集，包括所有两个端点都在 $ V’ $ 中的 $ G $ 的边所组成的图，称为 $ G $ 的点导出子图，记为 $ G(V’) $。

边导出子图：

对于 $ E’ \subseteq E(G) $，以 $ E’ $ 为边集，由 $ E’ $ 中所有端点构成的点集所组成的图，称为 $ G $ 的边导出子图，记为 $ G(E’) $。

生成子图：

如果图 $ G $ 的一个子图包含 $ G $ 的所有顶点，则称该子图为 $ G $ 的一个生成子图。

简单图的生成子图数量：

对于一个具有 $ m $ 条边的简单图 $ G $，它有 $ 2^m $ 个生成子图。
图运算

删点: $ G - V $ - 删除顶点集 $ V $ 中的顶点及相关联的边。
删边: $ G - E $ - 删除边集 $ E $ 中的边，不删除顶点。
并运算: $ G + H $ - 将两个图中的点和边合并成新图，适用于不相交的图。
交运算
差运算: $ G - H $ - 从 $ G $ 中删除 $ H $ 中的边得到新图。
对称差运算（环和）: $ G \Delta H = (G \cup H) - (G \cap H) $ - 两个图的并集与交集的差集。
联运算: 未具体定义，将两个不相交图的每个顶点相互连接。

积运算

在图论中，积运算是将两个图组合成一个新的图的方法。具体定义如下：

定义：设 $ G_1 = (V_1, E_1) $ 和 $ G_2 = (V_2, E_2) $ 是两个图。
操作：构造一个新的图，其顶点集为 $ V = V_1 \times V_2 $，即两个顶点集的笛卡尔积。
连接规则：对于 $ V $ 中的任意两点 $ u = (u_1, u_2) $ 和 $ v = (v_1, v_2) $，当满足以下条件之一时，将 $ u $ 和 $ v $ 连接：
- $ u_1 = v_1 $ 且 $ u_2 $ 与 $ v_2 $ 在 $ G_2 $ 中相邻；
- $ u_2 = v_2 $ 且 $ u_1 $ 与 $ v_1 $ 在 $ G_1 $ 中相邻。
结果：通过这种方式构造的新图称为 $ G_1 $ 与 $ G_2 $ 的积图，记为 $ G_1 \times G_2 $。
举例：可以用于定义超立方体

合成运算

合成运算是图论中另一种将两个图组合成新图的方法。具体定义如下：

定义：设 $ G_1 = (V_1, E_1) $ 和 $ G_2 = (V_2, E_2) $ 是两个图。
操作：构造一个新的图，其顶点集为 $ V = V_1 \times V_2 $，即两个顶点集的笛卡尔积。
连接规则：对于 $ V $ 中的任意两点 $ u = (u_1, u_2) $ 和 $ v = (v_1, v_2) $，当满足以下条件之一时，将 $ u $ 和 $ v $ 连接：
- $ u_1 $ 与 $ v_1 $ 在 $ G_1 $ 中相邻；
- $ u_1 = v_1 $ 且 $ u_2 $ 与 $ v_2 $ 在 $ G_2 $ 中相邻。
结果：通过这种方式构造的新图称为 $ G_1 $ 与 $ G_2 $ 的合成图，记为 $ G_1 [G_2] $。

偶图判定定理

定理：

$一个图是偶图当且当它不包含奇圈$

必要性
假设 $ G $ 是一个偶图 $ (X, Y) $，且 $ C = v_0v_1 \ldots v_kv_0 $ 是 $ G $ 中的一个圈。不失一般性，我们假定 $ v_0 \in X $。那么，根据偶图的定义，$ v_{2i} \in X $ 且 $ v_{2i+1} \in Y $。因此，$ v_k \in Y $。所以，$ C $ 是一个偶圈。

充分性
在图 $ G $ 中任意选取一个点 $ u $，我们定义集合 $ V $ 的分类如下：

$ X = \{ x | d(u, x) = 2k, x \in V(G) \} $

$ Y = \{ y | d(u, y) = 2k + 1, y \in V(G) \} $
我们需要证明的是 $ X $ 中的任意两点 $ v $ 和 $ w $ 不邻接。
假设 $ v $ 和 $ w $ 是 $ X $ 中的任意两个顶点。设 $ P $ 是一条最短的 $ (u, v) $ 路径，而 $ Q $ 是一条最短的 $ (u, w) $ 路径。设 $ z $ 是 $ P $ 和 $ Q $ 的最后一个交点。

由于 $ P $ 和 $ Q $ 是最短路径，$ P $ 和 $ Q $ 中从 $ u $ 到 $ z $ 的段长度相同，因此它们的奇偶性也相同。又因为 $ P $ 和 $ Q $ 的长度均为偶数，所以 $ P $ 和 $ Q $ 中从 $ z $ 到 $ v $ 的段和从 $ z $ 到 $ w $ 的段奇偶性也相同。
如果 $ v $ 与 $ w $ 邻接，那么我们可以得到一个奇圈，这与 $ G $ 是偶图的事实相矛盾。因此，$ v $ 和 $ w $ 不邻接。这证明了 $ G $ 是一个偶图。

图的代数表示

代数表示主要有邻接矩阵、关联矩阵

邻接矩阵

定义：$\text { 设 } G \text { 为 } n \text { 阶图, } V=\left\{v_{1}, \cdots, v_{n}\right\} \text {, 邻接矩阵 } A(G)=\left(a_{i j}\right)$。其中$a_{ij}$是$v_i$,$v_j$之间的边数。

性质：

其具有非负性与对称性
同一图的不同形式的邻接矩阵是相似矩阵
如果 $𝐺$ 为简单图，$𝐴(𝐺)$ 为布尔矩阵

定理： $G$ 连通的充分必要条件是 $A(G)$ 不与矩阵 $\left(\begin{array}{l}A_{11}, 0 \\ 0, A_{22}\end{array}\right)$ 相似, 非连通图的邻接矩阵一定能够写成准对角矩阵形式。

定理：$\text { 记 } A^{k} \text { 的元素为 }\left\{a_{i j}^{k}\right\}, a_{i j}^{k} \text { 为 } v_{i} \text { 到 } v_{j} \text { 长度为 } k \text { 的途径条数 }$。

推论：对简单图, $A^{2}$ 的元素 $a_{i i}^{2}$ 是 $v_{i}$ 的度数; $A^{3}$ 的元素 $a_{i i}^{3}$ 是含 $v_{i}$ 的三角形个数的 2 倍

最短路算法

Dijkstra算法

算法流程：

初始化：所有结点都未被访问，将源点的距离设为0，其他结点的距离设为$\infty$
循环$n$次：
- 找到表中还没被访问的、距离不为$\infty$的结点。如果没有，则退出循环。
- 将该结点设置为已被访问
- 更新表中的距离为$min(「到结点j的距离」,「到结点i的距离」+「结点i到j的距离」)$
  
  如果有路径数组，则需要在更新最短距离的同时更新路径。如果到节点i的距离+结点i到j的距离更小，则paths[j]=i

算法的时间复杂度为$O(n^2)$

伪代码：

#初始化
Distance_Matrix=...#邻接矩阵
min_distance=[infinity _ for i in range(n)]
visited=[false _ for i in range(n)]
paths=[None _ for i in range(n)]

#初始化到start节点的距离为0
min_distance[start]=0
for time in range(n):
  #找出还没被访问的且距离最小的节点的索引
  index=get_next_node_index(visited,min_distance)
  if index=None:#如果没有这样的节点，则说明不是连通的，退出循环
    break
  
  #更新路径表和距离表
  for next_node_index in range(n):
    if Distance_Matrix[index][next_node_index]!=infinity:#找到了一个和当前点邻接的结点
      if min_distance[next_node_index]<Distance_Matrix[index][next_node_index]+distance[index]:
        min_distance[next_node_index]=Distance_Matrix[index][next_node_index]+distance[index]
        paths[next_node_index]=index

Bellman-Ford最短路算法

算法流程：

初始化：将源点的距离设为0，其他结点的距离设为$\infty$。path数组初始化为null。
循环$n-1$次：对所有的边$e(i,j)$，如果$d(j)>d(i)+e(i,j)$。（d[i]是源点到i点的最短距离）
- $d(j)=d(i)+e(i,j)$
- $path[j]=i$
第$k$次得到的$d$数组是源点经过至多$k$个中间点，到其他点的最小值。

算法复杂度：$O(mn)$

伪代码：

distance=[infinity _ for i in range(n)]
paths=[None _ for i in range(n)]

#初始化到start节点的距离为0
min_distance[start]=0
for time in range(1,n-1):
  for [i,j] in all_edges:#对所有边中的每一条边都执行下述操作
    if distance[j]>distance[i]+D[i][j]:
      distance[j]=distance[i]+D[i][j]
      path[j]=i

改进的Bellman-Ford最短路算法

如果$d(i)$上一次没有改变，则这一次不需要执行$d(j)>d(i)+c(i,j)$。（要改变上一次就改变了）

改进后的算法流程：

初始化：将源点的距离设为0，其他结点的距离设为$\infty$。path数组初始化为null。
将源点$s$加入队列$q$当中。
如果队列不为空，则：
1. 取出队列顶部的结点$i$
2. 对所有以$i$为起点的边$e(i,j)$，如果$d(j)>d(i)+e(i,j)$。
  - $d(j)=d(i)+e(i,j)$
  - $path[j]=i$
  - 如果队列$q$中不含有$j$，则$q.push_back(j)$

树

不含圈的图称为无圈图。树是连通的无圈图。森林也是无圈图。

树叶：树叶是一度的顶点。

树的六种等价定义

𝑇 是树
𝑇 是含有 𝑛 − 1 条边的无圈图
𝑇 中任意两点连通，且有 𝑛 − 1 条边
𝑇 连通，且任意边都是割边

割边：删掉该边图就不连通了

任意两点仅有一条路
𝑇 无圈，加入任意一条边后，𝑇 有且仅有一个圈

定理

[!Note]

具体的证明看课件：graph-5.pdf。

树与森林都是偶图

因为它们不包含奇圈，也就是圈长度为0
每棵非平凡树至少有两片树叶

反证法：如果不是，则要么不存在最长路（两端点度为1），要么树中存在圈
图 𝐺 是树当且仅当 𝐺 中任意两点都被唯一的路连接。
设$T$是$(n,m)$树，有$m=n-1$。多了就有圈，少了就不连通。推论：具有 $k$ 个分支的森林有 $𝑛 − 𝑘$ 条边。
每个$n$阶连通图的边数至少为$n-1$
任意树$T$两个不邻接结点加上一条边后，可得到唯一圈。
设$G$是树且$\Delta \geq k$，$G$至少有$k$个一度结点。$\Delta$指的是树中度最大的顶点的度。
若森林 $G$ 有 $2 k$ 个奇数度顶点, 则 $G$ 中有 $k$ 条边不重合的路 $P_{1}, \cdots, P_{k}$ 满足 $E(G)=\bigcup_{i} E\left(P_{i}\right)$
树的度序列的充分必要条件：设 $S=\left\{d_{1}, \cdots, d_{n}\right\}$ 满足: $d_{1} \geq \cdots \geq d_{n} \geq 1, \sum d_{i}=2(n-1)$ , 存在树 $T$ 度序列为 $S$ 。

树的中心

图的顶点的离心率：$e(v) = \max\{d(u, v)|u \in V\}$。（一个顶点与其他顶点之间的最大距离）
图的半径：$r = \min\{e(v)|v \in V\}$。（所有顶点的离心率的最小值）
图的中心点：离心率等于半径的点。
图的中心：中心点的集合。

定理：树的中心由一个点或两个相邻点组成。

生成树

概念

若图 $𝐺$ 的一个生成子图𝑇 是树，称它为 $𝐺$ 的一棵生成树。

生成树的边称为树枝，𝐺 中非生成树的边称为弦
在连通边赋权图 $𝐺$ 中总权值最小的生成树，称为最小生成树
生成树一般不唯一
$s$到所有节点的最短路构成一棵树

定理

每个连通图 $𝐺$ 至少包含一棵生成树。推论：若 $𝐺$ 是 $(𝑛,𝑚)$ 连通图，则 $𝑚 ≥ 𝑛 − 1$。

可以用破圈法求生成树
记图$G$中生成树的个数为$ \tau(G) $, 有$ \tau(G)=\tau(G-e)+\tau(\text { G.e })$。

图 $𝐺$ 中，删掉边 $𝑒$ 后，把 $𝑒$ 的两个端点重合，得到的图记为 $𝐺.e$
设 $G$ 是顶点集合为 $V(G)=\left\{v_{1}, \cdots, v_{n}\right\}$ 的图, 设 $A=\left(a_{i j}\right)$ 是 $G$ 的邻接矩阵, $C=\left(c_{i j}\right)$ 是 $n$ 阶方阵, 其中:
$c_{i j}=\left\{\begin{array}{ll} d\left(v_{i}\right) & i=j \\ -a_{i j} & i \neq j \end{array}\right.$
则 $G$ 的生成树棵数为 $C$ 的任意一个余子式的值。

定理中的矩阵 $𝐶$ 又称为图的 Laplace 矩阵，定义为 $𝐶 = 𝐷(𝐺) − 𝐴(𝐺)$。其中：$𝐷(𝐺)$ 为度对角矩阵，即主对角元为对应顶点度数，其余元素为 0；$𝐴(𝐺)$ 是邻接矩阵

最小生成树算法

Kruskal算法

算法流程：

选择权值最小边 $𝑒_1$
若已经选定边 $𝑒_1, 𝑒_2, · · · , 𝑒_𝑘$ , 则从 $𝐸 − {𝑒_1, 𝑒_2, · · · , 𝑒_𝑘 }$ 中选择最小边 $𝑒_𝑘+1$, 使$𝑒_1, 𝑒_2, · · · , 𝑒_𝑘$ 无圈。
不能增加边时，停止

管梅谷破圈法

算法流程：

从任意圈开始，去掉圈中权值最大的一条边
不断破圈，直到 $G$ 中没有圈为止

Prim算法

任选一个顶点$u$，选择与$u$关联的权值最小的边作为最小生成树的第一条边$e_1$
在与已经选取边只有一个公共端点的边中，选取权值最小的边。直到选取$n-1$条边为止

根树

概念

每条边都有一个方向的树称为有向树。

以 $𝑣$ 为终点和起点的边数称为 $𝑣$ 的入度和出度
入度与出度之和称为点 $𝑣$ 的度

一棵有向树，如果恰有一个顶点的入度为 0，其余顶点入度为 1，这样的的树称为根树。

入度为 0 的点称为树根
出度为 0 的点称为树叶
入度为 1，出度大于 1 的点称为内点
内点和树根统称为分支点
顶点 $𝑣$ 到树根的距离称为 $𝑣$ 的层数
最大层数称为树高
对于根树，由其中节点及其后代导出的子图，称为子根树

几种不同类型的根树

m元树

对于根树，若每个分支点至多𝑚 个儿子，称为𝑚 元根树；若每个分支点恰有 𝑚 个儿子，称它为完全 𝑚 元树。

定理：在完全 $𝑚$ 元树中，若树叶数为 $𝑡$ , 分支点数为 $𝑖$ , 则$(m-1)i=t-1$。

有序树与完全树

对于根树$𝑇$，若规定了每层顶点的访问次序，这样的根树称为有序树：一般次序为从左至右。

二叉树

$𝑚$ 元树中，应用最广泛的是二元树。

有序树转化为二元树的方法：

从根开始，保留每个父亲同其最左边儿子的连线，撤销与别的儿子的连线
兄弟间用从左至右的有向边连接
直接位于给定结点下面的儿子，作为左儿子，对于同一水平线上与给定结点右邻的结点，作为右儿子

二元树的遍历：找到一种方法，每个结点恰好访问一次。有三种常用遍历方法：先序遍历、中序遍历、后序遍历。

最优二叉树

设 $T$ 是二元树, 若对所有 $t$ 片树叶赋权 $w_{i}(1 \leq i \leq t)$ , 权值为 $w_{i}$ 的树叶层数记为 $L\left(w_{i}\right)$ , 称 $W(T)=\sum_{i=1}^{t} w_{i} L\left(w_{i}\right)$ 为该二元树的权。

$𝑊 (𝑇 )$ 最小的二元树称为最优二元树。

Huffman 算法：

令 $S=\left\{w_{1}, \cdots, w_{t}\right\}$
从 $S$ 中取出两个权值最小者 $w_{i}, w_{j}$
画结点 $v_{i}, v_{j}$ , 权值 $w_{i}, w_{j}$ , 画 $v_{i}$, $v_{j}$ 的父亲 $v$ ，权值 $w_{i}+w_{j}$
$S \leftarrow\left(S-\left\{w_{i}, w_{j}\right\}\right) \cup\left\{w_{i}+w_{j}\right\}$
如果 $S$ 只含一个元素, 停止, 否则转第二步

最小Steiner树

给出一个图$G=(V,E)$，和一个终端顶点集合$N$。

Steiner树问题：找到一个$G$的子树$T$，覆盖所有的$N$，并且权值和最小。

当$N=V$的时候，是最小生成树问题
当$|N|=2$的时候，是最短路径问题

与最小生成树问题不同，Steiner树问题允许在树中添加图中未标记为终端顶点的其他顶点（称为Steiner顶点），以帮助降低总权重。

Steiner树是一个NP完全问题，因为其可以和X3C问题（已知的NP完全问题）一一对应。

X3C问题：有一个集合X，它包含n个元素，以及一个集合S，它包含一些3个元素的子集，这些子集都是X的子集。X3C问题的目标是找到一个子集S’，它是S的子集，并且S’中的每个子集都是X的一个恰好覆盖，即每个子集都恰好覆盖X中的一个元素，并且每个元素都被恰好一个子集覆盖

所以需要用近似算法来解决Steiner树问题。

Metric闭包

以$u$和$v$之间的最短距离作为顶点$u$和$v$之间的边的权值，就可以得到metric闭包。

在metric闭包中：

边的权重满足三角不等式：$d(A, C) \leq d(A, B) + d(B, C)$
最小Steiner树在图中的成本等于最小Steiner树在其metric闭包中的成本

而在Metric闭包中，最小生成树的成本不超过两倍的最小Steiner树的成本，所以可以用最小生成树去近似最小Steiner树。参考文章

图的连通性

割边与割点

割边（桥）：若$w(G-e)>w(G)$，则称$e$为$G$的一条割边。

割点：若 $E(G)$ 可划分为两个非空子集 $E_1, E_2$，使 $G(E_1)$ 和 $G(E_2)$ 以点 $v$ 为公共顶点，称 $v$ 为 $G$ 的割点。

$w(G)$表示图$G$的连通分支数

定理

$𝑒$ 是图 $𝐺$ 的割边当且仅当 $e$ 不在 $G$ 的任何圈中
- 推论：$𝑒$ 为连通图 $𝐺$ 的一条边，若 $𝑒$ 含于 $𝐺$ 的某圈中，则 $𝐺$ − $𝑒$ 连通
无环非平凡图 $G$，$v$ 是 $G$ 的割点，当且仅当 $w(G - v) > w(G)$。
$v$ 是树 $T$ 的割点，当且仅当 $v$ 是分支点。
一个顶点 $v$ 是无环连通图 $G$ 的割点，当且仅当满足以下条件：$V(G - v)$ 可以划分为两个非空子集 $V_1, V_2$，对于所有 $x \in V_1, y \in V_2$，顶点 $v$ 在每一条连接 $x$ 与 $y$ 的路上。

块

没有割点的连通图称为块图，简称块。

满足如下性质的 $𝐺$ 的子图 $𝐵$ 称为 $𝐺$ 的块：

它本身是块
没有真包含 $𝐵$ 的 $𝐺$ 的块存在

定理

若简单图 $𝐺$ 满足 $|𝑉(𝐺)| \geq 3$，则 $𝐺$ 是块的充要条件为其中任意两顶点位于同一圈上。
$v$ 是 $𝐺$ 的割点当且仅当 $v$ 至少属于 $𝐺$ 的两个不同块。

点割集和边割集

点割集

给定连通图 $G$，设 $V’ \subseteq V$，若 $G - V’$ 不连通，称 $V’$ 为 $G$ 的一个点割集：

含有 $k$ 个顶点的点割集称为k顶点割。
点数最少的顶点割称为最小顶点割。

若 $G$ 有顶点割，最小顶点割的顶点数称为 $G$ 的点连通度，否则称 $𝑛 − 1$ 为其点连通度。$G$ 的点连通度记为 $\kappa(G)$。

若不连通，$\kappa(G) = 0$。
若 $\kappa(G) \geq k$，称 $G$ 是k连通的：

边割集

最小边割集所含边数称为图的边连通度，记为 $\lambda(G)$。

若 $G$ 不连通，则定义 $\lambda(G) = 0$。
若 $\lambda(G) \geq k$，称 $G$ 是k边连通的。

定理

Whitney定理：对任意图 $G$，有 $\kappa(G) \leq \lambda(G) \leq \delta(G)$。

其中$\kappa(G)$是点连通度，$\lambda(G)$是边连通度，图的最小度数是$\delta(G)$。
对任意 $(n, m)$连通图$G$, 有 $\kappa(G) \leq\lfloor 2 m / n\rfloor$
设$G$是$(n, m)$单图, 若 $\delta(G) \geq\lfloor n / 2\rfloor$ , 则 $G$ 连通
设 $G$ 是 $(n, m)$ 单图，若对 $\forall k \in \mathbb{Z}$，有 $\delta(G) \geq \frac{(n+k-2)}{2}$，则 $G$ 是 $k$ 连通的
设 $G$ 是 $n$ 阶单图，若 $\delta(G) \geq \lfloor n / 2 \rfloor$，则有 $\lambda(G) = \delta(G)$。

分离集

设 $S$ 为 $G$ 的一个顶点子集或边子集，若 $u, v$ 不在 $G-S$ 的同一分支上，称 $S$ 分离 $u, v$。

定理

Menger定理：
- $G$ 中分离 $x, y$ 的最少点数等于独立的 $(x, y)$ 路的最大数目。
  
  也可以表述为：一个非平凡图 $G$ 是 $k \geq 2$ 连通的，当且仅当 $G$ 的任意两个顶点 $u, v$ 间至少存在 $k$ 条内点不交的 $(u, v)$ 路。
- $G$ 中分离 $x, y$ 的最少边数等于边不重的 $(x, y)$ 路的最大数目。
  也可以表述为：一个非平凡的图 $G$ 是 $k \geq 2$ 边连通的，当且仅当 $G$ 的任意两个顶点间至少存在 $k$ 条边不重的 $(u, v)$ 路。
  
  推论：对于一个阶至少为 3 的无环图 G , 下面三个命题等价：
  - G 是 2 连通的
  - G 中任意两点位于同一个圈上
  - G 无孤立点, 且任意两条边在同一个圈上

最大流和最小割

基础概念

Flow network定义

流网络的定义：

有向图
边有容量属性
有source节点（源节点）s和sink（汇节点）节点t

割（Cut）

一个割将结点划分为两部分：$S$和$T$，使得源节点$s$属于$S$，汇节点$t$属于$T$。

分割的容量（capacity）指的是从$S$（不是$s$）出发的边的权重之和。最小割问题就是找一个cut，使得分割的容量最小。

流（Flow）

每条边都有一个流，每条边的流需要满足：

不超过边的容量
除了$s$和$t$，其他点流入需要等于流出。

最大流问题就是找到一个流法，使得汇入$t$的流最大。

可以类比为，$s$是一个水库，水流通过管道（边）流向不同的区域（顶点），最终到达汇点𝑡，比如一个污水处理厂。在这个过程中，水流流量不能超过管道的容量，并且每个交叉点的水量必须保持平衡，不能有水积聚或流失。

最大流最小割定理

基础定理

设 $f$ 为一个流，$(S, T)$ 为任意的 $s-t$ 割。那么，穿过这个割的净流量等于到达 $t$ 的流量。
到达$t$的流量最多是割的容量。（穿过割的净流量不一定等于割的容量）
设 $f$ 为一个流，$(S, T)$ 为一个 $s-t$ 割，其容量等于流 $f$ 的值。那么 $f$ 是一个最大流，$(S, T)$ 是一个最小割。

最大流最小割定理

$在任意网络中，最大流的值=最小割的容量$

参考：[算法竞赛入门] 网络流基础：理解最大流/最小割定理 (蒋炎岩)

寻找最大流——Ford-Fulkerson算法

参考：13-2: Ford-Fulkerson Algorithm 寻找网络最大流

步骤：

初始化：首先，需要将网络中所有边的流量初始化为0（或者根据问题的具体要求设置为其他初始值）。同时，需要保留一个残余网络，用于记录每条边的剩余容量，即还能增加的流量。
寻找增广路径：在残余网络中寻找一条从源点到汇点的路径，这条路径上的所有边都有剩余容量大于0。这样的路径称为增广路径。如果存在这样的路径，则执行下一步；如果不存在，算法结束，当前网络流即为最大流。
计算瓶颈容量：在增广路径上，找到所有边中剩余容量最小的那一个，这个剩余容量即为瓶颈容量。这个值决定了我们可以沿增广路径增加多少流量。
增广流量：沿着增广路径，将每条边的流量增加瓶颈容量，同时需要减少残余网络中对应边的剩余容量（因为流量增加了，所以剩余容量相应减少）。对于增广路径上的每条边，还需要在残余网络中增加一条反向边，其容量等于增广路径上该边的增流量，用于表示流量的可逆性。
重复：返回第二步，继续寻找新的增广路径，直到无法找到增广路径为止。

定理：一个流 $f$ 是最大流，当且仅当不存在增广路径。

寻找最小割：13-5: 最小割 Min-Cut

欧拉图

在欧拉图中，可以通过图中的一条路径经过每条边恰好一次并返回起点。这条路径被称为欧拉回路（也称为欧拉环游或欧拉闭迹）。

定理

下列陈述对于非平凡连通图 $𝐺$ 是等价的：
- 𝐺 是欧拉图
- 𝐺 的顶点度数为偶数
- 𝐺 的边集合能划分为圈
连通图是欧拉图当且仅当每个点的度数是偶数。
- 推论：连通非欧拉图存在欧拉迹当且仅当只有两个顶点度数为奇数

求欧拉环游的算法

Fleury算法

Fleury算法用于在欧拉图中求出一条具体欧拉环游。复杂度为$O(m^2)$。

算法流程如下：

任意选择一个顶点 $v_{0}$，置 $w_{0}=v_{0}$。
假设迹 $w_{i}=v_{0} e_{1} v_{1} \cdots e_{i} v_{i}$ 已经选定，按下述方法从 $E-\left\{e_{1}, e_{2}, \cdots, e_{i}\right\}$ 中选取边 $e_{i+1}$：
- $e_{i+1}$ 与 $v_{i}$ 相关联。
- 除非没有别的边可选择，否则 $e_{i+1}$ 不能是 $G_{i}=G-\left\{e_{1}, e_{2}, \cdots, e_{i}\right\}$ 的割边。
当以上操作不能执行时，算法停止。

证明：

Hierholzer算法

Hierholzer算法是另一个寻找欧拉环游的算法，它采用深度优先搜索，不断找圈，最后合并为Euler环游。其的复杂度为$O(m)$，比Fleury算法的更小。

算法伪代码如下，其中cpath记录当前圈，epath记录总体路径。

while cpath:
    u = cpath.top()  # Assuming cpath is a stack
    if all_edges_visited(u):
      	cpath.pop()
        epath.append(u)  # Assuming epath is a list to store the final path
    else:
        u, x = select_random_edge(u)
        cpath.append(x)
        delete_edge(u, x)

中国邮路问题

中国邮路问题指的是：邮递员从邮局出发，每条街道至少行走一次，再回邮局。如何行走，其环游路程最短？

如果邮路图本身是欧拉图，可以直接用 Fleury 算法。
重要的是，如果是非欧拉图，如何重复行走街道才能使行走总路程最短？

定理

若 $W$ 是包含图 $G$ 每条边至少一次的闭途径，$W$ 具有最小权值当且仅当：

$G$ 的每条边在$W$ 中最多重复一次

对 $G$ 的每个圈，在$W$ 中重复的边的总权值不超过非重复边总权值

算法

若图 $G$ 只有两个奇度顶点 $u, v$，则最优邮递员路径算法如下：

在 $u, v$ 间求出一条最短路 $P^*$
在 $P^*$ 上，给每条边添加一条平行边得 $G$ 的欧拉母图 $G$ ∗
在 $G^*$ 中运行 Fleury 算法

哈密顿图

如果经过图 $𝐺$ 每个顶点一次后能够回到出发点，称这样的图为Hamilton 图，简称 $𝐻$ 图。所经过的闭途径是 $𝐺$ 的一个生成圈，称为 $𝐺$ 的 Hamilton 圈。如果存在经过 $𝐺$ 的每个顶点一次的路，称该路为 Hamilton 路，简称 $𝐻$ 路。

判定H图是一个NP难问题。

定理

$H$圈的必要条件：若 $G$ 为 $H$ 图, 则对 $V(G)$ 的任一非空顶点子集 $S$, 有 $w(G-S) \leq|S|$。

可用来证明不是$H$圈。$w$指的是连通分支。
Dirac定理：对于 $n \geq 3$ 的单图 $G$，如果 $\delta(G) \geq n / 2$，则 $G$ 是 $H$ 图。

这个定理不是紧的
Ore定理：若 $d(u) + d(v) \geq n$ 对任意不相邻 $u, v$ 成立，则 $G$ 是 $\mathrm{H}$ 图。

这个定理是紧的

闭包和H图

闭图

在 $n$ 阶单图中，若对 $d(u)+d(v) \geq n$ 的任意顶点 $u, v$，均有 $u, v$ 相邻，则称 $G$ 是闭图。

定理：若 $G_{1}$ 和 $G_{2}$ 是同一个点集 $V$ 的两个闭图，则 $G = G_{1} \cap G_{2}$ 也是闭图。

闭包

包含 $G$ 的极小闭图称为 $G$ 的闭包，如果 $G$ 本身是闭图，其闭包是它本身。

如果 $G$ 不是闭图，则可以通过在度和大于等于 $n$ 的不相邻顶点对间加边来构造闭图

定理：

图 $𝐺$ 的闭包是唯一的
Bondy定理：图 $G$ 是 $H$ 图当且仅当它的闭包是 $H$ 图

度序列和H图

设简单图 $G$ 的度序列是 $\left(d_{1}, d_{2}, \cdots, d_{n}\right), d_{1} \leq \cdots \leq d_{n}, n \geq 3$ 。若对任意 $m < \frac{n}{2}$, $d_{m} > m$ 或 $d_{n-m} \geq n-m$, $G$ 是 $\mathrm{H}$ 图。

TSP

不同的TSP问题：

一般TSP问题：给定一个城市集合和两两城市间的距离，找到最短的路径访问所有城市并回到出发城市。
Metric TSP问题：城市间距离满足三角不等式
Euclidean TSP：城市间的距离是欧拉距离

定理：对于所有$\rho >1$，寻找一个$\rho-$最优的TSP旅行路线是NP难题。

近似最优算法

基于最小生成树的算法

首先计算图的最小生成树
对最小生成树先序遍历
先序遍历序列就是TSP问题的一个近似解

路径长度小于等于2倍的最优长度。

基于最近邻的算法

从任意顶点开始
如果已有顶点还未包含所有顶点：
- 找到离已有顶点最近的顶点$v_a$，记其离的最近的顶点为$v_b$。
- 找到离开$v_b$的边，其到达$v_c$。
- 将$v_a$加入已有顶点，并替换$v_b\rightarrow v_c$为$v_b \rightarrow v_a$

路径长度小于等于2倍的最优长度。

Christofides算法

找到一个最小生成树 T
找到T中奇度顶点的最小匹配 M，将 M 添加到 T
找到一个欧拉回路
简化回路

路径长度小于等于1.5倍的最优长度。

偶图的匹配

图的匹配

匹配的定义

定义：设 $M$ 是图 $G$ 的边子集（不含环），若 $M$ 中任意两条边没有共同顶点，则称 $M$ 是 $G$ 的一个匹配或对集或边独立集。

若 $v \in G$ 为 $M$ 中某条边的端点，称它为 $M$ 的饱和点；否则，称为 $M$ 的非饱和点。

如果 $𝑀$ 是图 $𝐺$ 包含边数最多的匹配，称 $M$ 是 $𝐺$ 的最大匹配。若最大匹配饱和了 $𝐺$ 的所有顶点，称完美匹配。一个图不一定存在完美匹配，若存在，不一定唯一。一个图的最大匹配也不一定唯一。

交错路与可扩路

𝑀 是图 𝐺 的匹配，𝐺 中一条由 𝑀 中的边和非 𝑀 中的边交错形成的路，称为 𝑀 交错路。若路的起点与终点是 𝑀 非饱和点，称为 𝑀 可扩路。

  %%{ init: { 'flowchart': { 'curve': 'basis' } } }%%
flowchart TD
subgraph X
A
B
C
D
end

subgraph Y
E
F
G
H
end

A-.-F
B---E & F
B-.-G
C---G
C-.-H
D---F & H

这里$A\rightarrow F \rightarrow B \rightarrow G \rightarrow C \rightarrow H$是一条交错路。

定理

Berge定理（最大匹配充要条件）：$𝐺$ 的匹配 $𝑀$ 是最大匹配的充要条件是 $𝐺$ 不包含 $𝑀$ 可扩路。
Hall定理（偶图匹配存在性）：设 $G=(X, Y)$ 是偶图, $G$ 存在饱和 $X$ 每个顶点的匹配的充要条件是：$\forall S \subseteq X,|N(S)| \geq|S|$。（$N(S)表示S的邻居$）
- 推论：$k$正则偶图存在完美匹配
- 推论：每个$k\geq 2$方体都有完美匹配
$K_{2n}$中完美匹配的个数为$(2n-1)(2n-3)\cdot \cdot \cdot 1$
树至多存在一个完美匹配
Tutte定理：图 $𝐺$ 有完美匹配的充要条件为：对$𝑉$ 的任意非空真子集 $𝑆$，$𝐺$ − $𝑆$ 的奇分支个数 $𝑜 (𝐺 − 𝑆) ≤ |𝑆 |$。

图的点覆盖

对图 $𝐺$ 的顶点子集 $𝐾$，如果 $𝐺$ 的每条边都至少有一个点在 $𝐾$ 中，称 $𝐾$为 $𝐺$ 的一个点覆盖。顶点数最少的 $𝐾$ 称为最小点覆盖，|$𝐾$| 称为 $𝐺$ 的覆盖数。

定理：

设 $𝑀$ 是 $𝐺$ 的匹配，$𝐾$ 是 $𝐺$ 的覆盖，若 $|𝑀|$ = $|𝐾|$，则 $𝑀$ 是最大匹配，$𝐺$ 是最小覆盖。
Konig定理：偶图中最大匹配的边数等于最小覆盖的顶点数。

匈牙利算法

匈牙利算法用于寻找完美匹配。参考视频：图论匈牙利算法求最大匹配

算法流程

设 $G$ 是具有二部划分 $\left(V_{1}, V_{2}\right)$ 的二部图。

任给初始匹配 $M$（边集）。
若 $M$ 饱和 $V_{1}$ 则结束，否则转 3；
在 $V_{1}$ 中找一非 $M$ 饱和点 $x$，置 $S=\{x\}$，$T=\varnothing$；
若 $N(S)=T$，则停止，否则任选一点 $y \in N(S)-T$；
若 $y$ 为 $M$ 饱和点转 6，否则作求一条从 $x$ 到 $y$ 的 $M$ 可增广路 $P$，$M=M \Delta P$，转 2；
由于 $y$ 是 $M$ 饱和点，故 $M$ 中有一边 $\{(u, y)\}$，置 $S=S \cup\{u\}$，$T=T \cup\{y\}$，转 4。

其中，$N(S)$ 表示集合 $S$ 中所有点的邻点集合，$M \Delta P$ 表示环和（也就是将路径 $P$ 中的边与匹配 $M$ 进行交换）。

复杂度

匈牙利算法的时间复杂度为$O(|V|*|E|)$，其中$|V|$是顶点数而$|E|$是边数。

Kuhn-Munkres 算法

Kuhn-Munkres 算法用于寻找最优匹配。假设 $G=(X, Y)$ 是边赋权完全偶图, $X=\left\{x_{1}, \cdots, x_{n}\right\} , Y=\left\{y_{1}, \cdots, y_{n}\right\}, w_{i j}=w\left(x_{i} y_{j}\right)$ 。那么求这个图的最优匹配，就是求一个具有最大权值的完美匹配

前置知识

可行顶点标号

若对任意的$x\in X,y\in Y$, 有$l(x)+l(y)\ge w(xy)$，称$l$是$G$的可行顶点标号。

对于任意$G$，均存在可行顶点标号：

$l(x)=\max_{y\in Y}w(xy)\\ l(y)=0$

相等子图

设 $l$ 是 $G$ 的可行顶点标号, 令 $E_{l}=\{x y \in E(G) \mid l(x)+l(y)=w(x y)\}$ , 称 $G$ 的生成子图 $G_{l}=G\left[E_{l}\right]$ 为 $G$ 对应于 $l$ 的相等子图。

定理：设 $l$ 是赋权完全偶图 $G$ 的可行顶点标号，若相等子图 $G_{l}$ 有完美匹配 $M^{}$ ,则 $M^{}$ 是 $G$ 的最优匹配。

Kuhn-Munkres 算法

参考文章：https://blog.csdn.net/lemonxiaoxiao/article/details/108704280

参考视频：图论 KM算法求最优匹配

算法步骤：

基于任意可行标号 $l$, 求出相等子图 $G_{l}$, 任选 $G_{l}$ 一个匹配 $M$。
若 $M$ 是完美匹配，算法终止; 否则, 令 $x$ 是一个 $M$ 非饱和顶点, 置 $S=\{x\}, T=\emptyset$。
若 $T \subset N_{G_{l}}(S)$, 转第 3 步; 否则有 $N_{G_{l}}(S)=T$, 修改标号 $l$ 如下:

$\alpha_{l}=\min \{l(x)+l(y)-w(xy) \mid x \in S, y \in Y-T\}$ $l(v) \leftarrow\begin{cases} l(v)-\alpha & v \in S \\ l(v)+\alpha & v \in T \end{cases}$

在 $N_{G_{l}}(S)-T$ 中选择一个顶点 $y$, 若 $y$ 是 $M$ 饱和的, 记 $yz \in M$, 更新 $S \leftarrow S \cup\{z\}, T \leftarrow T \cup\{y\}$, 转第 2 步; 否则, 寻找 $G_{l}$ 中的 $M$ 可扩 $(u, y)$ 路, 用其更新 $M$, 转第 1 步。

另一种版本（我觉得更清晰）：

从任何可行顶标（例如平凡顶标）$ l $ 开始，确定 $ \left(K_{n, n}, w\right) $ 的等子图 $ G_{l} $，并且在 $ G_{l} $ 中选取匹配 $ M $。若 $ M $ 饱和 $ V_{1} $，则 $ M $ 是完美匹配，也即 $ M $ 是最优匹配，算法终止。否则转入步骤 (2)。

基于匹配 $ M $，在 $ \left(K_{n, n}, w\right) $ 的 $ l $ 等子图 $ G_{l} $ 中执行匈牙利算法，该算法终止于 $ S \subset V_{1} $，$ T \subset V_{2} $ 且 $ N_{G_{l}}(S)=T $。利用公式 $ \alpha_{l}=\min \left\{l(x)+l(y)-\omega(x, y) \mid x \in S, y \in V_{2}-T\right\} $ 计算值 $ \alpha_{l} $，然后利用公式 $l^{\prime}(u)=\left\{ \begin{array}{ll} l(u)-\alpha_{l}, & u \in S \\ l(u)+\alpha_{l}, & u \in T \\ l(u), & \text{其他} \end{array} \right.$ 确定新的可行顶标 $ l^{\prime} $，并以 $ l^{\prime} $ 替代 $ l $，以 $ G_{l^{\prime}} $ 替代 $ G_{l} $ 转入步骤 (1)。

注意：

标号的调整不影响已有匹配
每次改变标号都会扩大$𝑇$，从而扩大匹配
完全图存在完美匹配
算法复杂度 $𝑂(𝑛^3 )$

任务分配匈牙利算法

问题：$𝑁$ 个人分配 $𝑁$ 项任务，每人分配一项，将一项任务分给一个人需支付报酬，如何分配任务，支付的报酬总数最少。也就是求最小权值的完美匹配。

算法步骤：

减去行最小值
减去列最小值
用最少的线条覆盖所有零（如果将0视为人$i$和任务$j$间的连线，找最小的点覆盖数就是找最大匹配）
- 如果需要 $n$ 条线，则停止，在零之间存在一个最优分配。
创建额外的零
- 找到步骤 3 中未被线条覆盖的最小元素（称其为 $k$）
- 从未覆盖的元素中减去 $k$，给被两次覆盖的元素加上 $k$。
- 转到步骤 3

平面图

如果能把图 $𝐺$ 画在平面上，使得除顶点外，边与边之间没有交叉，称 $𝐺$可以嵌入平面，或称 $𝐺$ 是可平面图。$𝐺$ 的边不交叉的一种画法，称为 $𝐺$ 的一种平面嵌入

平面上的自身不相交的封闭曲线称为 Jordan 曲线。

定理：Jordan 曲线把平面分成内外 2 部分，连接两部分的任意曲线必然与Jordan 曲线相交。

面

平面图 $𝐺$ 把平面分成若干连通片，称为 $𝐺$ 的区域，或面，其集合记为 $Φ$

面积有限的面称为内部面，否则称为外部面

顶点和边都与某个面关联的子图，称为该面的边界

面 $𝑓$ 的边界中含有的边数称为 $𝑓$ 的次数，记为 $𝑑𝑒𝑔(𝑓 )$
- 割边计算 2 次

定理

设$G=(n, m)$是平面图, $\sum_{f \in \Phi} \operatorname{deg}(f)=2 m$。
平面图欧拉公式：设 $𝐺 = (𝑛,𝑚)$ 是有 $𝜙$ 个面的连通平面图，$𝑛 − 𝑚 + 𝜙 = 2$。
- 推论：平面图 $𝐺$ 有 $𝑘$ 个连通分支，$𝑛 − 𝑚 + 𝜙 = 𝑘 + 1$
- 若连通平面图 $G$ 每个面 $f$ 满足 $\operatorname{deg}(f) \geq l \geq 3$ , 则 $m \leq \frac{l}{l-2}(n-2)$。隐含着$m\leq 3n-6$。
- 对任意简单平面图，有 $ \delta \leq 5$
$m$是边的数量，$n$是顶点的数量，$l$是每个面最小次数，$𝜙$是面数

图的嵌入性

定理：

$G $ 可球面嵌入当且仅当 $ G $ 可平面嵌入。
所有图均可嵌入 $ \mathrm{R}^{3} $ 中。

平面图的判定

定理：

对简单图 $G$ , 若 $m>3 n-6$ , 则 $G$ 不是平面图。
对简单图 $G$ , 若 $m>\frac{l(n-2)}{(l-2)}$ , 则 $G$ 不是平面图。
$K_5$和$K_{3,3}$不是平面图
至少有 9 个顶点的简单平面图的补图不是平面图，9 为顶点数的下界

通过同胚判定

如 $G_{1}$ 与 $G_{2}$ 通过反复 2 度顶点内扩充和收缩后变成同构, 称它们同胚

在图的边上插入一个 2 度顶点, 使一条边分成两条边, 称将图在 2 度顶点内扩充
去掉一个图的 2 度顶点, 使关联它们的两条边合并成一条边，称将图 G 在 2 度顶点内收缩

图的平面性在同胚意义下不变。

Kuratowski定理：$G$ 是平面图，当且仅当它不含 $ K_{5} $ 和 $ K_{3,3} $ 同胚的子图

推论：$G $ 是非平面图，当且仅当它含有与 $ K_{5} $ 和 $ K_{3,3} $ 同胚的子图

通过简单基础图判定

去掉 𝐺 中的环，用单边代替平行边而得到的图称为 𝐺 的基础简单图。

图 $𝐺$ 是平面图，当且仅当它的基础简单图是平面图
图 $𝐺$ 是平面图，当且仅当它的每个块是平面图

Wangner 判定定理

设 $𝑢𝑣$ 是简单图 $𝐺$ 的一条边，去掉该边，重合其端点，再删去由此产生的环和平行边，这一过程称为 $𝐺$ 的初等收缩或边收缩。

Wanger定理：简单图 $ G $ 是平面图，当且仅当它不含可收缩到 $ K_{5} $ 或 $ K_{3,3} $ 的子图。

凸多面体与平面图

一个多面体，如果在体上任取两点，其连线均在体上，称为凸多面体。把凸多面体压缩在平面上，得到的平面图，称为该凸多面体的一维骨架。

定理：存在且只存在5种正多面体（plato 立体）：正四、六、八、十二、二十面体。

平面图的对偶图

$ G $ 的对偶图 $G^{*}$ 构造如下

在 $G$ 的每个面 $f_{i}$ 内取一个点 $v_{i}^{}$ 作为 $G^{}$ 的一个顶点
对 $G$ 的一条边 $e$ , 若 $e$ 是面 $f_{i}$ 与 $f_{j}$ 的公共边, 连接 $v_{i}^{}$ 与 $v_{j}^{}$ , 若 $e$ 是面 $f_{i}$ 中的割边, 以 $v_{i}$ 为顶点作环。

对偶图性质：

$G^{*}$ 的顶点数等于 $G$ 的面数
$G^{*}$ 的边数等于 $G$ 的边数
$G^{*}$ 的面数等于 $G$ 的顶点数
$d\left(v^{*}\right)=\operatorname{deg}(f)$
同构的平面图可以有不同构的对偶图

定理：

平面图 $ G $ 的对偶图 $ G^{*} $ 连通
对平面图 $ G,\left(G^{}\right)^{} \simeq(同构) G $ 当且仅当 $ G $ 连通。

图的着色

边着色

对图 $G$ 的边进行染色，若相邻边染不同颜色，则称对 $G$ 进行正常边着色。

如果能用 $k$ 种颜色对 $G$ 进行正常边着色，称 $G$ 是 $k$ 边可着色的。$k$ 的最小值，称为 $G$ 的边色数，记为 $\chi^{\prime}(G)$。
若点 $v$ 关联的边的着色没有用到色 $i$，则称 $v$ 缺 $i$ 色。着相同颜色的边集称为该着色的一个色组。

对图的边着色，本质上是对边集合的一种划分，因此对应实际问题中的划分问题或分类问题。

定理

偶图$K_{n,m}$边色数：$\chi^{\prime}\left(K_{m, n}\right)=\Delta$
一般偶图边色数：对偶图 $G$，$\chi^{\prime}(G) = \Delta$。
简单图边色数（Vizing定理）：对于简单图 $G$，其边色数 $\chi’(G)$ 为 $\Delta$ 或 $\Delta + 1$。

判断 $ \chi^{\prime}(G)=\Delta $ 还是 $ \chi^{\prime}(G)=\Delta+1 $ 一般情况下是困难的
- 引理：在简单图 $G$ 中，假设 $x$ 与 $y_1$ 是不相邻的两个顶点，$\pi$ 是 $G$ 的一个正常 $k$ 边着色。如果在着色 $\pi$ 下，顶点 $x$、$y_1$ 以及所有与 $x$ 相邻的点都至少缺少一种颜色，那么图 $G + xy_1$ 是 $k$ 边可着色的。
- 推论：若简单图 $ G $ 中只有一个最大度点或恰有两个相邻的最大度点, 则 $ \chi^{\prime}(G)=\Delta$
- 推论：对$n=2k+1$阶简单图G
  - 若 $m > k\Delta$，则 $\chi^{\prime}(G) = \Delta + 1$。
  - 若 $G$ 是正则图，则 $\chi^{\prime}(G) = \Delta + 1$。

点着色

对图 $G$ 的顶点进行染色，若相邻点染不同颜色，则称对 $G$ 进行正常点着色。

如果能用 $k$ 种颜色对 $G$ 进行正常点着色，称 $G$ 是 $k$ 点可着色的。
$k$ 的最小值，称为 $G$ 的点色数，记为 $\chi(G)$。
着相同颜色的点集称为该着色的一个色组

对图的点着色，本质上是对点集合的一种划分，因此对应实际问题中的划分问题或分类问题。

定理

对于任意图 $G$，有 $\chi(G) \leq \Delta + 1$。
Brooks定理：连通简单图 $G$，如果它既不是奇圈，又不是完全图，那么满足不等式 $\chi(G) \leq \Delta$。
Brooks定理改进：对于简单图 $G$，则有 $\chi(G) \leq \Delta_{2}(G) + 1$；若 $G$ 中最大度点互不邻接，则 $\chi(G) \leq \Delta(G)$。
- 记$N(u)$ 是顶点 $u$ 的邻居顶点集合。若记 $V_{2}(G)=\{v \mid \exists u \in N(v): d(u) \geq d(v)\}$，则次大度 $\Delta_{2}(G)=\max \left\{d(v) \mid v \in V_{2}(G)\right\}$。
五色定理：每个平面图都是5可着色的。
k着色，即给定一个图，问是否可以k着色，是NP难问题。

算法

对一般图的点染色是一个NP难问题。

$Δ(𝐺) + 1$ 的点着色算法：将顶点任意排序为 $v_{1}, \cdots, v_{n}$ , 将颜色任意排序依次染 $v_{i}$ , 每次用可能的最小颜色染 $v_{i}$ 。

不能保证得到最佳染色方案。

Welsh—Powell 改进：按顶点度数由大到小的次序着色，即先处理瓶颈结点。

随机图

给定 $N$ 与 $p$，对任意一对顶点，以概率 $p$ 连边，产生随机图记为 $G_{np}$。

边数：$\bar{M} = p \cdot\binom{N}{2} = \frac{p N(N-1)}{2}$

平均度数：$\bar{k}=2 \bar{M} / N=(N-1) p$

单个顶点度为$k$的概率：当 $k \ll N$ 时，$P(k)$ 近似于 Poisson 分布。

定理：记 $N_G$ 为 $G_{Np}$ 最大连通分支的顶点个数

当 $\bar{k} = Np < 1$ 时，$N_G = O(\ln N)$；
当 $\bar{k} = 1$ 时，$N_G = O\left(N^{2/3}\right)$；
当 $1 < \bar{k} < \ln N$ 时，巨连通分支存在；
当 $\bar{k} > \ln N$ 时，$N_G = N$，即 $G$ 是连通图。

有向图

有向图是由顶点集 $V$ 和有向边集 $E$ 组成的。

有向路径是一个顶点列表 $\{v_i\}$，满足 $v_i v_{i+1} ∈ E$。如果存在从 $s$ 到 $t$ 的有向路径，则称 $t$ 是从 $s$ 可达的。
有向无环图（DAG）是一个没有有向环的有向图。
只有出边的顶点称为源点。
只有入边的顶点称为汇点。
如果对于所有的 $u, v ∈ V$，$u$ 都是从 $v$ 可达的，则称有向图是强连通的。
强连通分量是一个最大的强连通子图。

核有向无环

假设给定一个有向图$𝐷$，定义另一个有向图$𝐾(𝐷)$。

在 $K(D)$ 中，每个顶点映射到 $D$ 的一个强连通分量。
如果 $D$ 中存在从对应于 $u$ 的分量到 $v$ 的边，则 $uv ∈ E(K(D))$。
$K(D)$ 被称为 $D$ 的核有向无环图（kernel DAG）。

寻找强连通分量

Kosaraju算法：

在图 $G$ 上运行深度优先搜索（DFS），并记录每个顶点的完成时间（每探索一个点时间+1）。
将图 $G$ 中所有边的方向反转。
从完成时间最大的节点开始在反转后的图上运行DFS，每当遇到死胡同时，就添加一个新的SCC。

传递闭包

传递闭包是一个有向图，它具有与 $D$ 相同的顶点集，但只在 $t$ 从 $s$ 可达时，从 $s$ 到 $t$ 有一条边。

计算传递闭包

方法一：计算邻接矩阵的布尔乘法$A^n$

使用逻辑与（AND）作为乘法（$\times$），逻辑或（OR）作为加法（+）。 -
复杂度：$O(n^4)$

改进方法：计算直到 $A^i$ 收敛。

进一步改进：计算 $A, A^2, A^4, \cdots$：复杂度：$O(n^3 \log n)$

拓扑排序

给定一个有向无环图 $G$，找到一个总排序，使得对于所有的 $uv \in E(G)$，在排序中 $u$ 都在 $v$ 之前。

算法：

识别一个源点 $s$
- 如果没有源点：停止（存在循环）
删除 $s$ 及其相关边，将 $s$ 加入队列
- 如果图不为空：回到步骤 1

复杂度：$O(n + m)$。

应用：调度

任务 $v$ 需要时间 $\text{time}[v]$ 来执行
存在优先级约束
问题：每个任务最早何时能完成？

算法：

计算顶点的拓扑顺序
初始化 $\text{fin}[v] = 0$ 对于所有 $v$
按拓扑顺序考虑 $v$：对于每条边 $v \rightarrow w$，设置 $\text{fin}[w] = \max(\text{fin}[w], \text{fin}[v] + \text{time}[w])$

点覆盖

给定无向图 $G$，找到一个最小顶点集 $V_0 \subseteq V$，使得如果 $(u, v) \in E(G)$，那么 $u \in V_0$ 或 $v \in V_0$。即通过选择顶点来覆盖边。是NP难问题。

APPROX-VERTEX-COVER 是一个多项式时间的 2-近似算法。

存在一个最优顶点覆盖，它不包括任何叶子 - 用其父节点替换覆盖中的任何叶子*

树上的点覆盖

存在一个最优顶点覆盖，它不包括任何叶子节点：用其父节点替换覆盖中的任何叶子节点。

用以下算法可以得到最优解：

初始化集合 C 为空：这是算法的起始步骤，创建一个空集合 C，用于存储算法的结果。
循环执行：这一部分是算法的核心，包含以下步骤：
- 条件判断：检查图 G 中是否至少存在一个叶子节点。如果不存在，则跳出循环。
- 添加父节点：在每次迭代中，将图 G 中所有叶子节点的父节点添加到集合 C 中。
- 删除节点：从图 G 中删除所有的叶子节点及其父节点。
返回集合 C：当循环结束后，算法返回集合 C 作为最终结果。

更优算法

定理：考虑一个图 $G$ 和它的边 $uv$。令 $G_u$ 为通过删除顶点 $u$ 及其关联边得到的图。图 $G$ 有一个大小为 $k$ 的顶点覆盖，当且仅当 $G_u$ 或 $G_v$ 有一个大小为 $k-1$ 的顶点覆盖。

算法：

如果 $E=\emptyset$，则返回 $\emptyset$；
如果 $k=0$ 且 $E\neq\emptyset$，则返回 $\perp$；
从 $E$ 中选择任意一条边 $(u,v)\in E$；
$S1=VERTEX-COVER-SEARCH(Gu,k-1)$；
$S2=VERTEX-COVER-SEARCH(Gv,k-1)$；
如果 $S1\neq\perp$，则返回 $S1\cup\{u\}$；
如果 $S2\neq\perp$，则返回 $S2\cup\{v\}$；
返回 $\perp$。

带权树的点覆盖

给定： 一个无向的、顶点加权的图 $G$。

目标： 找到一个权重最小的顶点子集 $V_0 \subseteq V$，使得如果边 $(u, v) \in E(G)$，那么 $u \in V_0$ 或 $v \in V_0$。

算法：

求以下问题的解
$\text{最小化 } \sum_{v} w(v) \cdot x(v)$
约束：
$\begin{aligned} &x(u)+x(v) \geq 1 & & \text { for each }(u, v) \in E \\ &x(v) \in[0,1] & & \text { for each } v \in V \end{aligned}$
在图中执行以下算法：
1. C = ∅
2. 根据刚才计算出来的一个最优解 $\bar{x}$
3. 对于每个顶点 $v$ 属于 $V$，如果 $\bar{x}(v) \geq \frac{1}{2}$，$C = C \cup \{v\}$
4. 返回 $C$

RAND-VC是一个期望中2-近似的多项式时间算法

图论基础

图论基础概念

Peterson图

图同构

几种典型的图

完全图

偶图

补图

自补图

顶点的度

握手定理

图的度序列

度序列判别定理

图序列

图序列判别定理（Havel-Hakimi 定理）

度的性质

子图

图运算

积运算

合成运算

偶图判定定理

必要性

充分性

图的代数表示

邻接矩阵

最短路算法

Dijkstra算法

Bellman-Ford最短路算法

改进的Bellman-Ford最短路算法

树

树的六种等价定义

定理

树的中心

生成树

概念

定理

最小生成树算法

Kruskal算法

管梅谷破圈法

Prim算法

根树

概念

几种不同类型的根树

m元树

有序树与完全树

二叉树

最优二叉树

最小Steiner树

Metric闭包

图的连通性

割边与割点

定理

块

定理

点割集和边割集

点割集

边割集

定理

分离集

定理

最大流和最小割

基础概念

Flow network定义

割（Cut）

流（Flow）

最大流最小割定理

基础定理

最大流最小割定理

寻找最大流——Ford-Fulkerson算法

欧拉图

定理

求欧拉环游的算法

Fleury算法

Hierholzer算法

中国邮路问题

定理

算法

哈密顿图

定理

闭包和H图