图与网络分析基础

没想到没几天又开始学到算法部分了，这一次定义将会学习的更加严谨。按照书上的拓展学习。

图的相关概念

图 (graph) 是一个二元组 $G=(V(G), E(G))$。其中 $V(G)$ 是非空集，称为 点集，对于 $V$ 中的每个元素，我们称其为 顶点 或 节点，简称 点；$E(G)$ 为 $V(G)$ 各结点之间边的集合，称为 边集。

常用 $G=(V,E)$ 表示图。

当 $V,E$ 都是有限集合时，称 $G$ 为 有限图。

当 $V$ 或 $E$ 是无限集合时，称 $G$ 为 无限图。

图有多种，包括 无向图，有向图，混合图 等。

若 $G$ 为无向图，则 $E$ 中的每个元素为一个无序二元组 $(u, v)$，称作 无向边，简称 边，其中 $u, v \in V$。设 $e = (u, v)$，则 $u$ 和 $v$ 称为 $e$ 的 端点。

若 $G$ 的每条边 $e_k=(u_k,v_k)$ 都被赋予一个数作为该边的 权，则称 $G$ 为 赋权图。如果这些权都是正实数，就称 $G$ 为 正权图。与一个顶点 $v$ 关联的边的条数称作该顶点的 度，记作 $d(v)$。特别地，对于边 $(v, v)$，则每条这样的边要对 $d(v)$ 产生 $2$ 的贡献。

对于一张无向图 $𝐺=(𝑉,𝐸)$，对于 $𝑢,𝑣∈𝑉$，若存在一条途径使得 $𝑣=𝑢,𝑣𝑘=𝑣$，则称 𝑢 和 𝑣 是 连通的。由定义，任意一个顶点和自身连通，任意一条边的两个端点连通。

若无向图 $𝐺=(𝑉,𝐸)$，满足其中任意两个顶点均连通，则称 $𝐺$ 是 连通图，$𝐺$ 的这一性质称作 连通性。

最基本的就这些了。

树

一个无圈的连通图称为树。

给了一个无向图$G=(V,E)$，保留 $G$ 的所有点，而删掉部分 $G$，的边或者说保留一部分 $G$ 的边，所获得的图称为$G$的生成子图。如果 $G$ 的生成子图是一个树，则称这个生产子图为一个生成树。

最小生成树

在一个赋权图的联通的无向图 $G$ 中找一个生成树，并使得这个生成树的所有边的权数之和最小。

Kruskal 算法求最小生成树

基本思想是从小到大加入边，是个贪心算法。

1. 新建图 $G$，$G$ 中拥有原图中相同的节点，但没有任何边。
2. 将原图中所有的边按权值从小到大排序。
3. 从权值最小的边开始，如果这条边连接的两个节点于图 $G$ 中不在同一个连通分量（不是联通的）中，则添加这条边到图 $G$ 中。
4. 重复3，直到 $G$ 中所有的节点都在同一个联通分量中。

伪代码：

KRUSKAL-FUNCTION(G, w)
    F := 空集合
    for each 图 G 中的顶点 v
        do 将 v 加入森林 F
    所有的边(u, v) ∈ E依权重 w 递增排序
    for each 边(u, v) ∈ E
        do if u 和 v 不在同一棵子树
            then F := F ∪ {(u, v)}
                将 u 和 v 所在的子树合并

通过使用路径压缩的并查集，平均时间复杂度为$O(\left| E \right| \log \left| V \right|)$，其中 $E,V$ 分别是图的边集和点集。

还有如果同时使用路径压缩和按秩合并的并查集，时间复杂度可以优化到$O(\left| E \right| \alpha( \left| V \right|))$，其中 $\alpha$ 表示反阿克曼函数。

反阿克曼函数

定义：

$$A(m,n) = \begin{cases}n + 1 & \text{如果 m=0} \\ A(m-1,1) & \text{如果 m>0 且 n=0} \\ A(m-1,A(m,n-1)) & \text{如果 m>0 且 n>0 }\end{cases}$$

由于这个函数的增加速率非常快，那么它的反函数就相应的增长的非常慢。

证明

思路很简单，为了造出一棵最小生成树，我们从最小边权的边开始，按边权从小到大依次加入，如果某次加边产生了环，就扔掉这条边，直到加入了 $n-1$ 条边，即形成了一棵树。

证明：使用归纳法，证明任何时候 K 算法选择的边集都被某棵 MST 所包含。

基础：对于算法刚开始时，显然成立（最小生成树存在）。

归纳：假设某时刻成立，当前边集为 $F$，令 $T$ 为这棵 MST，考虑下一条加入的边 $e$。

如果 $e$ 属于 $T$，那么成立。

否则，$T+e$ 一定存在一个环，考虑这个环上不属于 $F$ 的另一条边 $f$（一定只有一条）。

首先，$f$ 的权值一定不会比 $e$ 小，不然 $f$ 会在 $e$ 之前被选取

然后，$f$ 的权值一定不会比 $e$ 大，不然 $T+e-f$ 就是一棵比 $T$ 还优的生成树了。

所以，$T+e-f$ 包含了 $F$，并且也是一棵最小生成树，归纳成立。

最短路问题

最短路问题是指对一个赋权的有向图 $D$ 中指定的两点 $v_s$ 和 $v_t$，找到一条从 $v_s$ 到 $v_t$ 的路，使得这条路上所有弧的总和最小，这条路被称为从 $v_s$ 到 $v_t$ 的最短路。这条路上所有弧的权数的总和被称为从 $v_s$ 到 $v_t$ 的距离。

我们一般讨论单源的最短路，全源最短路径得用 Floyd 算法以及 Johnson 全源最短路径算法，这里不再讨论。

Dijkstra 算法

Dijkstra 算法由荷兰计算机科学家 E. W. Dijkstra 于 1956 年发现，1959 年公开发表。是一种求解 非负权图 上单源最短路径的算法。

松弛

对于边 $(u,v)$，松弛操作对应下面的式子：$dis(v) = \min(dis(v), dis(u) + w(u, v))$。

$dis(v)$ 表示的含义是起点开始，到 $v$ 的最短路径，$w(u,v)$ 表示边 $(u,v)$ 的权值 $w$。

这么做的含义是显然的：我们尝试用 $S \to u \to v$（其中 $S \to u$ 的路径取最短路）这条路径去更新 $v$ 点最短路的长度，如果这条路径更优，就进行更新。

过程

将结点分成两个集合：已确定最短路长度的点集（记为 $S$ 集合）的和未确定最短路长度的点集（记为 $T$ 集合）。一开始所有的点都属于 $T$ 集合。

初始化 $dis(s)=0$，其他点的 $dis$ 均为 $+\infty$。

然后重复这些操作：

1. 从 $T$ 集合中，选取一个最短路长度最小的结点，移到 $S$ 集合中。
2. 对那些刚刚被加入 $S$ 集合的结点的所有出边执行松弛操作。

直到 $T$ 集合为空，算法结束。

正确性证明

$D(u)$ 为 $s$ 点到 $u$ 点的 实际 最短路长度。

下面用数学归纳法证明，在 所有边权值非负 的前提下，Dijkstra 算法的正确性。

简单来说，我们要证明的，就是在执行 1 操作时，取出的结点 $u$ 最短路均已经被确定，即满足 $D(u) = dis(u)$。

初始时 $S = \varnothing$，假设成立。

接下来用反证法。

设 $u$ 点为算法中第一个在加入 $S$ 集合时不满足 $D(u) = dis(u)$ 的点。因为 $u$ 点一定满足 $D(u)=dis(u)=0$，且它一定是第一个加入 $S$ 集合的点，因此将 $u$ 加入 $S$ 集合前，$S \neq \varnothing$，如果不存在 $s$ 到 $u$ 的路径，则 $D(u) = dis(u) = +\infty$，与假设矛盾。

于是一定存在路径 $s \to x \to y \to u$，其中 $y$ 为 $s \to u$ 路径上第一个属于 $T$ 集合的点，而 $x$ 为 $y$ 的前驱结点（显然 $x \in S$）。需要注意的是，可能存在 $s = x$ 或 $y = u$ 的情况，即 $s \to x$ 或 $y \to u$ 可能是空路径。

因为在 $u$ 结点之前加入的结点都满足 $D(u) = dis(u)$，所以在 $x$ 点加入到 $S$ 集合时，有 $D(x) = dis(x)$，此时边 $(x,y)$ 会被松弛，从而可以证明，将 $u$ 加入到 $S$ 时，一定有 $D(y)=dis(y)$。

下面证明 $D(u) = dis(u)$ 成立。在路径 $s \to x \to y \to u$ 中，因为图上所有边边权非负，因此 $D(y) \leq D(u)$。从而 $dis(y) = D(y) \leq D(u)\leq dis(u)$。但是因为 $u$ 结点在 1 过程中被取出 $T$ 集合时，$y$ 结点还没有被取出 $T$ 集合，因此此时有 $dis(u)\leq dis(y)$，从而得到 $dis(y) = D(y) = D(u) = dis(u)$，这与 $D(u)\neq dis(u)$ 的假设矛盾，故假设不成立。

因此我们证明了，1 操作每次取出的点，其最短路均已经被确定。命题得证。

注意到证明过程中的关键不等式 $D(y) \leq D(u)$ 是在图上所有边边权非负的情况下得出的。当图上存在负权边时，这一不等式不再成立，Dijkstra 算法的正确性将无法得到保证，算法可能会给出错误的结果。

时间复杂度

$|E|$ 表示边数，$|V|$ 顶点数

朴素方法：$O(|E|^2)$

使用二叉堆优化方法：$O((|E| + |V|) \log |V|)$

网络流问题

前置知识

网络是指一个特殊的有向图 $G=(V,E)$，其与一般有向图的不同之处在于有容量和源汇点。

• $E$ 中的每条边 $(u, v)$ 都有一个被称为容量的权值，记作 $c(u, v)$。当 $(u,v)\notin E$ 时，可以假定 $c(u,v)=0$。
• $V$ 中有两个特殊的点：源点 $s$ 和汇点 $t$（$s \neq t$）。

对于网络 $G=(V, E)$，流是一个从边集 $E$ 到整数集或实数集的函数，其满足以下性质。

1. 容量限制：对于每条边，流经该边的流量不得超过该边的容量，即 $0 \leq f(u,v) \leq c(u,v)$；
2. 流守恒性（平衡条件）：除源汇点外，任意结点 $u$ 的净流量为 $0$（输入量等于输出量）。其中，我们定义 $u$ 的净流量为 $f(u) = \sum{x \in V} f(u, x) - \sum{x \in V} f(x, u)$。

定义网络 $D$，若 $\mu$ 为网络中的一条链，给 $\mu$ 定向为从 $us$ 到 $u_t$，$\mu$ 上的弧凡与 $\mu$ 同向称为前向弧，反向为后向弧，其集合分别用 $\mu^+$ 和 $\mu ^-$ 表示。设 $f={f{ij}}$ 是一个可行流，如果满足

$$\begin{cases} 0 \leq f_{ij} \leq c_{ij} & (v_i,v_j) \in \mu^+ \\ c_{ij} \geq f_{ij} > 0 & (v_i,v_j) \in \mu^- \end{cases}$$

则称 $\mu$ 为从 $v_s$ 到 $v_t$ 的一条增广链。

对于给定网络 $G=(V,E,C)$ ，设 $S,T \subset V$ ，且 $S\cup T=V,S \cap T = \varnothing,v_s\in S,v_t\in T$ ，则称 $(S,T)$ 为割集

残量网络：根据原网络，定义的一个可描述每条边当前可调配流量的网络图，其中可调配残量 $r(u,v)=c(u,v)−f(u,v)$ ，表明每条弧还能再有多 少流量经过。

网络最大流问题（标号法）

最大流问题：对于网络 $G = (V, E)$，给每条边指定流量，得到合适的流 $f$，使得 $f$ 的流量尽可能大。此时我们称 $f$ 是 $G$ 的最大流。

这里我们只讨论运筹书上写的标号法求最大流，不讨论更深入的。

标号过程

1. 源点 $v_s$ 标号$(0,+\infty)$

2. 不断选择一个已标号的顶点 $v_i$ ，对所有与 $v_i$ 相邻而没有标号的顶点 $v_j$ 按如下规则处理：

   • 若 $(vi,v_j)\in E$ ，并且 $f{ij}<c{ij}$ ，则给顶点 $v_j$ 标号 $(v_i,\delta_j),\delta_j=\min(\delta_i,c{ij}−f_{ij})$

   • 若 $(vj,v_i)\in E$ ，并且 $f{ij}>0$，则给顶点 $vj$ 标号 $(v_i,\delta_j),\delta_j=\ min(\delta_i,f{ji})$

3. 当无法选择后，若终点 $v_i$ 得到标号，说明存在增广链，转到调整阶段，否则说明不存在增广链，此时可行流 $f$ 即为最大流

调整过程

• 应用反向追踪法，从终点 $v_t$ 及其其他顶点的第一个标号，找出增广链
• 调整结束后去掉所有标号，再次进行标号过程。

最小费用最大流问题

最小费用最大流问题：在网络 $G = (V, E)$ 上，对每条边给定一个权值 $w(u, v)$，称为费用（cost），含义是单位流量通过 $(u, v)$ 所花费的代价。对于 $G$ 所有可能的最大流，我们称其中总费用最小的一者为最小费用最大流。

增流网络

顶点：增流网络 $D_f$ 的顶点与原网络相同

弧与权：

• 在 D 中的弧 $(vi,v_j)$ 若为零流弧，即 $f{ij} = 0$ ，则在 $Df$ 中构建一个同向的弧，$c{ij}^, = c{ij} - f{ij},b{ij}^, = b{ij}$
• 在 D 中的弧 $(vi,v_j)$ 若为饱和弧，即 $f{ij} = c{ij}$ ，则在 $D_f$ 中构建一个反向的弧，$c{ij}^, = c{ij} ,b{ij}^, = -b_{ij}$
• 在 D 中的弧 $(vi,v_j)$ 若为非饱和弧，即 $f{ij} < 0$ ，则在 $Df$ 中构建一个同向的弧和反向的弧，同向的弧$c{ij}^, = c{ij} - f{ij},b{ij}^, = b{ij}$，反向的弧 $c{ij}^, = c{ij} ,b{ij}^, = -b{ij}$

增流圈

在增流网络 $D_f$ 中的负回路对应网络 $D$ 中的一个圈，在这个圈中，如果方向与负回路方向相同的所有弧都为不饱和弧，方向与负回路方向相反的所有弧都为非零流弧，则这个圈被称为增流圈。

算法实际过程

1. 利用最大流算法，将网络的流量调整到最大流
2. 构建伴随网络流f的增流网络 $D_f$
3. 在增流网络 $Df$ 中，查找关于费用的负回路，令$\theta = \min c{ij}^,$($c_{ij}^,$ 为负回路中各弧的容量)，若不存在负回路，则说明当前网络流已经是最小费用流，结束算法
4. 针对负回路对应网络 $D$ 中的圈，若该圈是增流圈，则把增流圈方向上与负回路方向一若该圈致的所有弧的流量加上 $\theta$，把增流圈方向上与负回路方向相反的所有弧的流量减去 $\theta$ 不是增流圈，则转到 3 重新寻找负回路
5. 继续寻找负回路，如果还有负回路，继续调整；否则返回 2