图与网络分析

图的基本概念与模型

P.S. 只列一些陌生概念（为什么图的概念会有这么多版本😅无语住了）

次：与某一个点 $v_i$ 相关联的边的数目称为点 $v_i$ 的次（degree），也叫做度，记作 $d(v_i)$
部分图： $G_1 = \left\{ V_1,E_1 \right\}$ ， $G_2 = \left\{ V_2,E_2 \right\}$ ，若有 $V_1 = V_2, E_1 \sqsubseteq E_2$ ，则称 $G_1$ 是 $G_2$ 的部分图。注意：部分图也是子图，子图不一定是部分图。（子图： $V_1 \sqsubseteq V_2, E_1 \sqsubseteq E_2$ ）
链、路：图中存在点和边交替序列 $\mu=\left\{ v_0,e_1,v_1,\cdots ,e_k,v_k \right\}$ ，若其中各边 $e_1,e_2,\cdots e_k$ 各不相同，且对任意的 $1\le t\le k$ 有， $v_{t-1}$ 和 $v_t$ 相邻，则称 $\mu$ 为链。如果链中所有顶点 $v_0,v_1,\cdots v_k$ 也互不相同，则称这样的链为路。

树和图的最小部分树

最小部分树就是最小生成树

树的性质

任何树中必定存在度为 1 的点
具有 n 个顶点的树的边树恰好等于 $(n-1)$
任何具有 n 个点、(n-1) 条边的连通图是树

以上性质说明：

树是无圈连通图中边数最多，即在树上只要任意再加上一条边就一定会出现圈。
由于树是无圈的连通图，即图的任意两个点之间有且仅有一条唯一通路。因此树也是最脆弱的连通图，只要从树中取走任意一条边，图就不连通了。因此一些重要的网络不能按照树的结构设计。

图的最小部分树

定义：
如果 $G_1$ 是 $G_2$ 的部分图，同时又是树，则称 $G_1$ 是 $G_2$ 的部分树。在所有部分树中树枝总长度最小的部分树，称为该图的最小部分树（也称为最小支撑树）。

定理：
图中任意一点 i，若 j 是与 i 相邻点中距离最近的，则边 $[i,j]$ 一定> 含在该图的最小部分树内。

避圈法和破圈法

两种方法寻找图的最小部分树

避圈法：

从图中任选一点 $v_i$ ，使得 $v_i \in V$ ，图中其余点均包含在 $\overline{V}$ 中
从 $V、\overline{V}$ 的连线中找出最小边，这条边一定包含在最小部分树内。不妨设最小边为 $[v_i,v_j]$ ，将其加粗，用以标记该边是最小部分树内的边。
令 $V \cup v_i \implies V，\overline{V} \backslash v_i \implies \overline{V}$
重复 2、3 两步，直至图中所有点均包含在 V 中为止。

破圈法：

从网络图 N 中任意取一条回路
去掉这个回路中权数最大的一条边，得到一个子网络 $N_1$ .
在 $N_1$ 中再任取一回路，再去掉回路中权数最大的一条边，得到 $N_2$
如此继续下去，一直到剩下的子图中不再含回路为止。得到的子图就是 N 的最小部分树。

最短路问题

Dijkstra 算法（求指定两点之间最短距离）

用 $d_{ij}$ 表示图中两相邻点 $i$ 与 $j$ 的距离，若 $i$ 与 $j$ 不相邻，令 $d_{ij} = \infty$ ，显然 $d_{ii} = 0$ ，若用 $L_{si}$ 表示从 $s$ 点到 $i$ 点的最短距离，现要求从 $s$ 点到某一点 $t$ 的最短距离，用 $Dijkstra$ 算法步骤如下：

从点 $s$ 出发，因为 $L_{ss} = 0$ ，将此值标注在 $s$ 旁的小方框内，表示 $s$ 点已标号；
从 $s$ 点出发，找出与 $s$ 相邻的点中距离最小的一个，设为 $r$ ，将 $L_{sr} = L_{ss} + d_{sr}$ 的值标注在 $r$ 旁的小方框内，表明点 $r$ 也已经标号；
从已标号的点出发，找出与这些点相邻的所有未标号的点 $p$ ，若有 $L_{sp} = \min(L_{ss}+d_{sp}; L_{sr} + d_{rp})$ ，则对 $p$ 点标号，并将 $L_{sp}$ 的值标注在 $p$ 点旁的小方框内；
重复前三步骤，一直到 $t$ 点得到标号为止

Floyd 算法（求任意两点之间的最短距离）

要点：以每一个顶点为中转站，刷新所有入度和出度的距离
因此需要：遍历每一个点顶点 --> 遍历每一个顶点的入度 --> 遍历每一个顶点的出度，以这个点为中转站，距离更短就刷新距离
核心代码：

for (int i = 0; i < graph.length; i++) {
        //所有入度
        for (int j = 0; j < graph.length; j++) {
            //所有出度
            for (int k = 0; k < graph[j].length; k++) {
                //以每个点为「中转」，刷新所有出度和入度之间的距离
                //例如 AB + BC < AC 就刷新距离
                if (graph[j][i] != -1 && graph[i][k] != -1) {
                    int newDistance = graph[j][i] + graph[i][k];
                    if (newDistance < graph[j][k] || graph[j][k] == -1) {
                        //刷新距离
                        graph[j][k] = newDistance;
                        //刷新路径
                        path[j][k] = i;
                    }
                }
            }
        }
    }

网络的最大流

割和流量

割是指将容量网络中的发点和收点分割开，并使 $s\to t$ 的流中断的一组弧的集合，

最大流最小割定理

增广链
如果在网络的发点和收点之间能找出一条链，在这条链上所有指向为 $s \to t$ 的弧（称 前向弧，记作 $\mu^{+}$ ），存在 $f<c$ ；所有指向为 $t \to s$ 的弧（称 后向弧，记作 $\mu^{-}$ ），存在 $f>0$ ，这样的链称 增广链。
当有增广链存在时找出

$\theta = \min \begin{cases} (c_i-f_i),\quad \text{对} \mu^{+} \\ f_i\ ,\quad \quad \quad \ \ \text{对} \mu^{-} \end{cases} \qquad (\theta > 0)$

再令

$f^{'} = \begin{cases} f_i + \theta,\quad \text{对所有} \mu^{+} \\ f_i - \theta,\quad \text{对所有} \mu^{-} \\ f_i\ , \quad \quad\ \ \text{对非增广链上的弧} \end{cases}$

显然 $f^{'}$ 仍是一个可行流，但较之原来的可行流 $f$ ，这时网络中从 $s \to t$ 的流量增大了一个 $\theta$ ，因此 只有当网络图中找不到增广链时， $s \to t$ 的流才不可能进一步增大。

定理：
在网络中 $s \to t$ 的最大流量等于它的最小割集的容量，即

$v^{*}(f) = c^{*}(V,\overline{V})$

求网络最大流的标号算法

又称 $Ford-Fulkerson$ 标号算法
算法实质是判断是否有增广链存在并设法吧增广链找出来
标号算法步骤：

首先给发点 $s$ 标号 $(0,\varepsilon(s))$ 。括弧中第一个数字是使这个点得到标号的前一个点的标号，因 $s$ 是发点，故记作 $0$ ；第二个数字 $\varepsilon(s)$ 表示从上一个标号点到这个标号点的流量最大允许调整值， $s$ 为发点，不限允许调整量，故 $\varepsilon(s) = \infty$ 。
列出与已标号点相邻的所有未标号点：
1. 考虑从标号点 $i$ 出发的弧 $(i,j)$ ，如果有 $f_{ij} = c_{ij}$ ，不给点 $j$ 标号；若有 $f_{ij} < c_{ij}$ ，则对点 $j$ 标号，记为 $(i,\varepsilon(j))$ ，括弧中 $i$ 表示点 $j$ 的标号是从点 $i$ 延伸过来的， $\varepsilon(j) = min \{ \varepsilon(i),(c_{ij}-f_{ij})\}$ ；
2. 考虑所有指向标号点 $i$ 的弧 $(h,i)$ ，如果有 $f_{hi}=0$ ，对 $h$ 点不标号；若有 $f_{hi} > 0$ ，则对点 $h$ 标号，记为 $(h,\varepsilon(h))$ ，其中， $\varepsilon(h) = min \{ \varepsilon(h),f_{hi}\}$ ；
3. 如果某为标号点 $k$ 有两个以上相邻的标号点，为了减少迭代次数，可按前两步中所述规则分别计算出 $\varepsilon(k)$ 的值，并取其中最大的一个标记。
重复第2步，可能出现以下两种结局：
- 标号过程中断， $t$ 得不到标号，说明该网络中不存在增广链，给定的流量即为最大流。记已标号点的集合为 $V$ ，未标号点集合为 $\overline{V}$ ， $(V,\overline{V})$ ，为网络的最小割；
- $t$ 得到标号，这时可用反向追踪法在网络中找出一条从 $s \to t$ 的由标号点及相应的弧连接而成的增广链。
修改流量，设图中原有可行流为 $f$ ，令
$f^{'}= \begin{cases} f + \varepsilon(t),\quad \text{对增广链上所有前向弧} \\ f - \varepsilon(t),\quad \text{对增广链上所有后向弧} \\ f\ , \quad \quad \quad \ \ \text{对所有非增广链上的弧} \end{cases}$
这样又得到网络上的一个新的可行流 $f^{'}$ .
抹掉图上所有标号，重复一至四步，直至图中找不到任何增广链，即出现第三步的第一个结局为止，这是网络图中的流量即为最大流。

最小费用流

最小费用流问题描述：
设网络有 $n$ 个点， $f_{ij}$ 为弧 $(i,j)$ 上的流量， $c_{ij}$ 为该弧的容量， $b_{ij}$ 为在弧 $(i,j)$ 上通过单位流量时的费用， $s_i$ 代表第 $i$ 点的可供量或需求量，当 $i$ 为发点时， $s_i>0$ ， $i$ 为收点时， $s_i<0$ ， $i$ 为中转点时， $s_i=0$ 。当网络供需平衡，即 $\displaystyle \sum_{i}s_i=0$ 时，将各发点物资调运到各收点（或从各发点按最大流量调运到各收点），使总掉运费用最小的问题，可归结为如下线性规划模型：

$min\ z = \sum_{i=1}^{n}\sum_{j=1}^{n}b_{ij}\,f_{ij} \\ s.t. \begin{cases} \displaystyle \sum_{j=1}^{n}f_{ij} - \sum_{k=1}^{n}f_{ki} = s_i(i=1,\cdots ,n) \\ 0 \le f_{ij} \le c_{ij} (对弧(i,j)) \\ \end{cases}$

最小费用流问题解题步：

从零流 $f_0$ 开始。 $f_0$ 是可行流，也是相应的流量为零时费用最小的
对可行流 $f_k$ $f_{k}$ 构造加权网络 $W(f_k)$ $W (f_{k})$ ，方法是：
1. 对 $0<f_{ij}<c_{ij}$ 的弧 $(i,j)$ ，当其为正向弧时，通过单位流的费用为 $b_{ij}$ ，当其为反向弧时，相应费用 $b_{ji}=-b_{ij}$ 。故在 $i$ 和 $j$ 点之间分别给出弧 $(i,j)$ 和 $(j,i)$ ，其权数分别为 $b_{ij}$ 和 $-b_{ij}$ 。
2. 对 $f_{ij}=c_{ij}$ 的弧 $(i,j)$ ，因为该弧流量已饱和，在增广链中只能作为反向弧。故在 $W(j_k)$ 中只画出弧 $(j,i)$ ，其权数值为 $-b_{ij}$ 。
3. 对 $f_{ij} = 0$ 的弧 $(i,j)$ ，在增广链中只能为正向弧，故在 $W(j_k)$ 中只画出弧 $(i,j)$ ，其权数值为 $b_{ij}$ 。
在加权网络 $W(f_k)$ 中，寻找费用最小的增广链，也即求从 $s \to t$ 的最短路，并将该增广链上流量调整至允许的最大值，得到一个新的流量 $f_{k+1}(>f_k)$ 。
重复第二、三两步，直至网络 $W(f_{k+m})$ 中找不到增广链（也即找不出最短路）时， $f_{k+}$ 即为要寻找的最小费用流。