【数学建模算法】(12)图的应用：最大流问题（上）

1.最大流问题的数学描述

1.1图中的流

定义在以 $V$ 为节点集， $A$ 为弧集的有向图 $G=(V, A)$ 上定义如下的权函数：
1. $L : A\rightarrow R$ 为弧上的权函数，弧 $(i, j) \in A$ 对应的权 $L(i, j)$ 记为 $l_{i j}$ ，称为弧 $(i,j)$ 的容量下界；
2. $U : A \rightarrow R$ 为弧上的权函数，弧 $(i, j) \in A$ 对应的权 $U(i, j)$ 记为 $u_{i j}$ ，称为弧 $(i,j)$ 的容量上界，或直接称为容量；
3. $D : V\rightarrow R$ 为顶点上的权函数，节点 $i \in V$ 对应的权 $D(i)$ 记为 $d_{i}$ ，称为顶点 $i$ 的供需量。
此时构成的网络称为流网络，可以记为：
$N=(V, A, L, U, D)$

由于我们只讨论 $V，A$ 优先级和的情况，所以对于弧上的权函数 $L,U$ 和顶点上的权函数 $D$ ，可以直接用所有弧上对应的权和顶点上的权组成的有限维向量表示，因此 $L, U, D$ 有时直接称为权向量，或简称权。由于给定有向图 $G=(V, A)$ ，我们总是可以在它的弧集合和顶点集合上定义各种权函数，所以流网络一般也直接简称为网络。

在流网络中弧 $(i,j)$ 的容量下界 $l_{i j}$ 和容量上界 $u_{i j}$ 表示的物理意义是：通过该弧发送某种“物质”时，必须发送最少数量为 $l_{i j}$ ，而发送的最大数量为 $u_{i j}$ ，顶点 $i \in V$ 对应的供需量 $d_{i}$ 则表示该顶点从网络外部获得的“物质”数量（ $d_{i}>0$ 时），或从该顶点发送到网络外部的“物质数量”（ $d_{i}<0$ 时）。下面我们给出严格定义。

定义：对于流网络 $N=(V, A, L, U, D)$ 其上的一个流 $f$ 是指从 $N$ 的弧集 $A到R$ 的一个函数，即对每条弧赋予一个实数 $f_{i j}$ （称为弧 $(i,j)$ 的流量）。如果流 $f$ 满足：
$\sum_{j :(i, j) \in A} f_{i j}-\sum_{j :(j, i) \in A} f_{j i}=d_{i}, \quad \forall i \in V\quad(1)$
$l_{i j} \leq f_{i j} \leq u_{i j}, \quad \forall(i, j) \in A\quad(2)$
则称 $f$ 为可行流，至少存在一个可行流的网络称为可行网络，约束（1）称为流量守恒条件（也称流量平衡条件），约束（2）称为容量约束。

可见，当 $d_{i}>0$ 时，表示有 $d_{i}$ 个单位的流量从该顶点流失到网络外部，因此顶点 $i$ 称为供应点或源。同理 $d_{i}<0$ 的点称为吸收点或汇。特殊地，当 $d_{i}=0$ ，改点称为转运点或平衡点。

一般来说，我们总是假设容量下界为0，所以约束2可改为：
$0 \leq f_{i j} \leq u_{i j}, \quad \forall(i, j) \in A$

1.2.饱和弧，非饱和弧和空弧

定义：在流网络 $N=(V, A, U, D)$ 中，对于流 $f$ ，如果
$f_{i j}=0, \quad \forall(i, j) \in A$
则称 $f$ 为零流，否则为非零流，如果某条弧 $(i,j)$ 上的流量等于其容量 $\left(f_{i j}=u_{i j}\right)$ ，则称该弧为饱和弧；如果某条弧 $(i,j)$ 上的流量小于其容量 $\left(f_{i j}<u_{i j}\right)$ ，则称该弧为非饱和弧；如果某条弧 $(i,j)$ 上的流量为0 $\left(f_{i j}=0\right)$ ，则称该弧为空弧。

2.最大流问题

2.1.问题的定义和辅助定理

考虑如下流网络 $N=(V, A, U, D)$ ；节点 $s$ 为网络中唯一的源点， $t$ 为唯一的汇点，而其他节点为转运点。如果网络中存在可行流 $f$ ，此时称流 $f$ 的流量为 $d_{s}$ （自然也等于 $-d_{t}$ ），通常记为 $v$ 或 $v(f)$ ，即
$v=v(f)=d_{s}=-d_{t}$
对于这种单源单汇的网路，如果我们并不给定 $d_{s}$ 和 $d_{t}$ （流量不给定），则网络一般记为 $N=(s, t, V, A, U)$ 。最大流问题就是在 $N=(s, t, V, A, U)$ 中找到流值最大的可行流（即最大流）。我们将会看到，最大流问题的许多算法也可以用来求解流量给定的网络中的可行流。也就是说，当我们解决了最大流问题以后，对于在流量给定的网络中寻找可行流的问题，通常也就可以解决了。

用线性规划的方法，可将最大流问题描述如下：
$\max v$
$\text { s.t. } \sum_{j :(i, j) \in A} f_{i j}-\sum_{j : j, i \in A} f_{j i}=\left\{\begin{array}{ll}{v,} & {i=s} \\ {-v,} & {i=t} \\ {0,} & {i \neq s, t}\end{array}\right.$
$0 \leq f_{i j} \leq u_{i j}, \quad \forall(i, j) \in A$

为了解决这个问题，给出一些定义和定理：

全幺模矩阵（全单位模矩阵）：如果一个矩阵 $A$ 的任何子方阵的行列式的值都是0,1，-1，则称 $A$ 是全幺模的，或称A是全幺模矩阵。

整流定理：最大流问题所对应的约束矩阵是全幺模矩阵。若所有弧容量均为正整数，则问题的最优解为整数解。

最大流问题虽然是一个线性规划问题，但是其可以利用图的优点，解决这个问题的方法较之线性规划的一般方法要方便，直观得多。

2.2.单源和单汇运输网络

实际问题往往是多源多汇网络，为了计算的规格化，可将多源多汇网络 $G$ 化成单源单汇网络 $G^{\prime}$ 。设 $X$ 为 $G$ 的源， $Y$ 是 $G$ 的汇

具体转化方法如下：
1.在原图 $G$ 中增加两个新的顶点 $x$ 和 $y$ ，令为新图 $G^{\prime}$ 中之单源和单汇，则 $G$ 中所有顶点 $V$ 成为 $G^{\prime}$ 的中间顶点集。
2.用一条容量为 $\infty$ 的弧把 $x$ 连接到 $X$ 的每个顶点。
3.用一条容量为 $\infty$ 的弧把 $Y$ 中的每个顶点连接到 $y$ 。

$G$ 和 $G^{\prime}$ 中的流以一个简单的方式相互对应。若 $f$ 是 $G$ 中的流，则由：
$f^{\prime}(a)=\left\{\begin{array}{l}{f(a)} ，若a是G的弧\\ {f^{+}(v)} ，若a=(x,v)\\ {f^{-}(v)}，若a=(v,y)\end{array}\right.$
所定义的函数 $f^{\prime}$ 是 $G^{\prime}$ 中使得 $v\left(f^{\prime}\right)=v(f)$ 的流，这里 $f^{+}(v)$ 表示流出 $v$ 的流量， $f^{-}(v)$ 表示流入 $v$ 的流量（在 $G$ 中）。

2.3.最大流和最小割关系

设 $N=(s, t, V, A, U), S \subset V, s \in S, t \in V-S$ ，则称 $(S, \overline{S})$ 为网络的一个割，其中 $\overline{S}=V-S, \quad(S, \overline{S})$ 为尾在 $S$ ，头在 $\overline{S}$ 的弧集，称
$C(S, \overline{S})=\sum_{(i, j) \in A \atop i \in S, j \in \overline{S}} u_{i j}$
为割 $(S, \overline{S})$ 的容量。

定理： $f$ 是最大流， $(S, \overline{S})$ 是容量最小的割的充要条件是
$v(f)=C(S, \overline{S})$

在网络 $N=(s, t, V, A, U)$ 中，对于轨 $\left(s, v_{2}, \cdots, v_{n-1}, t\right)$ （此轨是无向的），若 $v_{i} v_{i+1} \in A$ ，则称它为前向弧；若 $v_{i+1} v_{i} \in A$ ，则称它为后向弧。

在网络 $N$ 中，从 $s$ 到 $t$ 的轨 $P$ 上，若对所有的前向弧 $(i,j)$ 都有 $f_{i j}<u_{i j}$ ，对所有的后向弧 $(i,j)$ 恒有 $f_{i j}>0$ ，则称这条轨 $P$ 为从 $s$ 到 $t$ 的关于 $f$ 的可増广轨。

令
$\delta_{i j}=\left\{\begin{array}{l}{u_{i j}-f_{i j}}，当(i,j)为前向弧 \\ {f_{i j}}，当(i,j)为后向弧\end{array}\right.$
$\delta=\min \left\{\delta_{i j}\right\}$
则在这条可增广轨上每条前向弧的流都可以增加一个量 $\delta$ ，而相应的后向弧的流可减少 $\delta$ ，这样就可使得网络的流量获得增加，同时可以使每条弧的流量不超过它的容量，而且保持为正，也不影响其它弧的流量。总之，网络中 $f$ 可增广轨的存在是有意义的，因为这意味着 $f$ 不是最大流。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 219,928评论 6赞 509
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,748评论 3赞 396
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 166,282评论 0赞 357
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 59,065评论 1赞 295
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 68,101评论 6赞 395
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,855评论 1赞 308
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,521评论 3赞 420
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,414评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,931评论 1赞 319
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 38,053评论 3赞 340
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,191评论 1赞 352
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,873评论 5赞 347
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,529评论 3赞 331
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,074评论 0赞 23
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,188评论 1赞 272
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,491评论 3赞 375
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,173评论 2赞 357