面向网络拓扑的通信优化

(并行与分布式计算十一)

最短路径问题

研究范围: 有权图

Prim算法(P算法)

Kruskal算法(K算法)

Prim算法注意顶点，kruskal算法更关心边。
思想：
将所有边排序，然后由小到大选边，只要保持所选边不成圈，选了n-1条边后就可以证明形成一个最小生成树。
赋权的连通图G=(V,E)中$m=|E|,n=|V|$,
S1:对E中各边的权排序，设$w_1 \leq w_2 \leq … \leq w_m, w_i=w(e_i)$
S2:初始化：$w \leftarrow 0,T \leftarrow \phi, k \leftarrow 1,t \leftarrow 0$
S3:若t=n-1则转S6，否则转S4
S4:若$T \bigcup {e_k}$有圈则$k \leftarrow k+1$转S4，否则转S5
S5: $T \leftarrow T \bigcup {e_k}, w \leftarrow w+w_k, t \leftarrow t+1, k \leftarrow k+1$,转S3
S6:输出T及w，结束。
T为最小树，w为T的权。

有向图，单商品流问题(网络中只需要安排的只有一种商品或业务)

$$
\sum{(i,j)\in E} f{ij} = \sum{(j, i)\in E} f{ji} =\begin{cases}
F&\text{$v_i$ 为源端}\
-F&\text{$v_i$ 为宿端}\
0& \text{其他}
\end{cases}
$$

可行流的条件

具有m条(有向)边、n个端的图共有2m+n-1个限制条件，包括
- m个非负性条件
- m个有限性条件
- n-1个连续性条件(连续性条件中有一个不是独立的)
满足此二限制条件的流称为可行流；可行流不止一个(流量为0也是一个可行流)
v(f) = F 为源宿间流的总流量
需要解决的基本问题分为两类：
- 最大流问题：在确定流的源和宿的情况下求一个可行流是v(f) = F为最大
- 网络拓扑已定，$c_{ij}$已知，给定源$v_s$与宿$v_t$，在二限制条件下求$v_s \to v_t$的最大流量$F_max$
- 最小费用流问题：如果边$e{i,j}$的单位流费用为$d{i,j}$，流f的费用为$C = \sum{(i,j)\in E}d{i,j}f_{i,j}$，在确定流的源和宿的情况下求一个可行流f使C最小
- 网络拓扑已定，$c_{ij}$已知，单位流量通过边$(v_i, vj)$所需的代价$\alpha{ij}$(代价系数)已知，给定流量F，寻求总代价中最小的可行流${f{ij}}$，其中总费用定义为：$\phi = \sum \alpha{ij}*f_{ij}$

割量

设X是V的真子集，且$v_s \in X$, $v_t \in \overline X$。$(X, \overline X)$表示两者界上的边，显然是使$v_s$,$v_t$分离的割集，定义方向$v_s \to v_t$。
其边分二类：
- 前向边：与割方向一致的边
- 反向边：与割方向相反的边
割量：前向边容量和 $c(X, \overline X) = \sum_{v_i \in X, vj \in \overline X} c{ij}$
对可行流${f_{ij}}$
- $f(X, \overline X)$表示前向边的流量$\sum f_{ij}$
- $f(\overline X, X)$表示反向边的流量$\sum f_{ji}$

性质

$F \leq c(X, \overline X)$
$ F = f(X, \overline X) - f(\overline X, X) \leq f(X, \overline X) \leq c(X, \overline X) $

可增流路

可增流路径：
- 前向边均不饱和($f{ij} < c{ij}$)
- 反向边均有非0流量($f_{ij} \not= 0$)
在可增流路上增流不影响连续性条件也不影响其它边上的流量，同时可以使从源端到宿端的流量增大
在可增流路上所有正向边的流量均可增加不致于破坏流量的有限性，所有反向边上均可减流(相当于正向增流)不致于破坏非负性。整体的增流量应为这些正向边上能增流(或反向边上能减流)的最小值，即可增量为
$$
\delta = min[min{e{ij} \in P}(c{ij} - f{ij}), min_{eji} \in P(f{ji})]
$$
在可增流路上各边均增加$\delta$(对于反向边即为减流$\delta$)，不会破坏流量的非负性、有限性，并不影响连续性条件，从而得到一个新的可行流，并使源宿端间的流量增加