什么是增广路？网络流的。给个详细清楚的定义和解释，搜资料的免了
发布网友
发布时间：2022-04-29 18:47
共1个回答
热心网友
时间：2023-10-05 04:57
给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点，对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图5-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。 所谓网络上的流，是指定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图5-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。
3.可行流与最大流
在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有：
(1)容量约束：0≤fij≤cij，(vi,vj)∈E，
(2)守恒条件
对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量vs(f)=汇点的净流入量（-vt(f)）
的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。
网络N中流值最大的流f*称为N的最大流。
4.可增广路径
所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。
设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件：
(1)在p上的所有前向弧(vi→vj)都是非饱和弧，即0≤fij<cij
(2)在p上的所有后向弧(vi←vj)都是非零弧，即0<fij≤cij
则称p为(关于可行流f的)一条可增广路径。
5.最大流定理
当且仅当不存在关于f*的增广路径，可行流f*为最大流。
5. 2 最大流算法
算法思想:最大流问题实际上是求一可行流{fij}，使得v(f达到最大。若给了一个可行流f，只要判断N中有无关于f的增广路径，如果有增广路径，改进f， 得到一个流量增大的新的可行流；如果没有增广路径，则得到最大流。
1.寻求最大流的标号法(Ford,Fulkerson)
从一个可行流(一般取零流)开始，不断进行以下的标号过程与调整过程，直到找不到关于f的可增广路径为止。
(1)标号过程
在这个过程中，网络中的点分为已标号点和未标号点，已标号点又分为已检查和未检查两种。每个标号点的标号信息表示两个 部分：第一标号表明它的标号从哪一点得到的，以便从vt开始反向追踪找出也增广路径；第二标号是为了表示该顶点是否已检查过。
标号开始时，给vs标上(s，0)，这时vs是标号但末检查的点，其余都是未标号的点，记为(0，0)。
取一个标号而未检查的点vi，对于一切未标号的点vj：
A．对于弧(vi，vj)，若fij<cij，则给vj标号(vi，0)，这时，vj点成为标号而未检查的点。
B．对于弧(vi，vj)，若fji>0，则给vj标号(-vi，0)，这时，vj点成为标号而未检查的点。
于是vi成为标号且已检查的点，将它的第二个标号记为1。重复上述步骤，一旦vt被标上号，表明得到一条从vi到vt的增广路径p，转入调整过程。
若所有标号都已检查过去，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。
(2)调整过程
从vt点开始，通过每个点的第一个标号，反向追踪，可找出增广路径P。例如设vt的第一标号为vk(或-vk)，则弧(vk，vt)(或 相应地(vt，vk))是p上弧。接下来检查vk的第一标号，若为vi(或-vi)，则找到(vi，vk)(或相应地(vk，vi))。再检查vi的第一 标号，依此类推，直到vs为止。这时整个增广路径就找到了。在上述找增广路径的同时计算Q：
Q=min{min(cij-fij)，minf*ij}
对流f进行如下的修改：
f'ij = fij+Q (vi，vj)∈ P的前向弧的集合
f'ij = fij-Q (vi，vj)∈ P的后向弧的集合
f'ij = f*ij (vi，vj)不属于P的集合
接着，清除所有标号，对新的可行流f’，重新进入标号过程。
