图与网络优化.ppt

图与网络优化,厦门大学管理学院管理科学系孙见荆,图论是应用十分广泛的运筹学分支，它已广泛地应用在物理学、化学、控制论、信息论、科学管理、电子计算机等各个领域。在实际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决。例如，在组织生产中，为了完成某项任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。一个邮递员送信，要走完他负责的全部街道，完成任务后回到邮局，应该按照怎样的路线走，使所走的路程最短。再例如，各种通信网络的合理架设，交通网络的合理分布等问题，应用图论的方法求解都很简便。欧拉在1736年发表图论方面的第一篇论文，解决了著名的哥尼斯堡七桥问题（哥尼斯堡城中有一条河普雷格尔河，该河中有两个岛，河上有七,座桥）。当时那里的居民热中于这样的问题：一个散步者能否走过七桥，且每座桥只走过一次，最后回到出发点。1736年欧拉将此问题归结为如下图所示的一笔画问题。即能否从某一点开始，不重复地一笔画出这个图形，最后回到出发点。欧拉证明了这是不可能的，因为图中的每一个点都只与奇数条线相关联，不可能将这个图不重复地一笔画成。这是古典图论中的一个著名问题。随着科学技术的发展以及计算机的出现与广泛应用，20世纪50年代，图论得到进一步发展。将庞大复杂,A,B,C,D,的工程系统和管理问题用图描述，可以解决很多工程设计和管理决策的最优化问题。例如，完成工程任务的时间最少、距离最短、费用最省等。图论受到数学、工程技术及经营管理等各个方面越来越广泛的重视。第一节 图的基本概念 在实际生活中，人们常常用点和线画出各种各样的示意图。通常用点代表研究的对象，点与点之间的连线表示这两个对象之间有特定的关系。在一般情况下，图中点的相对位置如何，点与点之间连线的长短曲直，对于反映对象之间的关系并不重要。一个图是由一些点及一些点之间的连线（不带箭头或带箭头）所组成。为了区别起见，把两点之间不带箭头的连线称为“边”，带箭头的连线称为“弧”。,如果一个图 G 是由点及边所构成的，则称之为无向图，简记为 G=(V,E)，其中，V,E 分别是图 G 的点集合和边集合。一条连接点 vi，vj V 的边记为vi,vj（或 vj,vi）。如果一个图 D 是由点及弧所构成的，则称之为有向图，简记为D=(V,A)，其中，V,A 分别是图 G 的点集合和弧集合。一条方向是从 vi 指向 vj 的弧记为(vi,vj)。图 G 或 D 中的点数记为 p(G)或 p(D)，边（弧）数记为 q(G)或 q(D)。在不会引起混淆的情况下，也分别简记为 p，q。一些常用的记号，先考虑无向图 G=(V,E)。若边 e=u,vE，则称 u,v 是 e 的端点，也称 u,v,是相邻的。称 e 是点 u（或 v）的关联边。若图 G 中，某个边 e 的两个端点相同，则称 e 是环，若两个端点之间有多于一条边，称这些边为多重边。一个无环，无多重边的图称为简单图，一个无环，但允许有多重边的图称为多重图。以点 v 为端点的边的个数称为 v 的次。记为 dG(v)或d(v)。称次为1的点为悬挂点，悬挂点的关联边称为悬挂边，次为零的点称为孤立点。定理1：图 G=(V,E)中，所有点的次之和是边数的两倍，即有：次为奇数的点称为奇点，否则称为偶点。定理2：任一个图中，奇点的个数为偶数。,证明：设 V1 和 V2 分别是 G 中奇点和偶点的集合，由定理1，有：因为从而 V1 的点数是偶数。给定一个图 G=(V,E)，一个点、边的交错序列(vi1,ei1,vi2,ei2,vik-1,eik-1,vik)，如果满足 eit=vit,vit+1(t=1，k-1)，则称为一条联结 vi1 和 vik 的链，记为(vi1,vi2,vik)，有时称点 vi2,vik-1 为链的中间点。链(vi1,vi2,vik)中，若 vi1=vik，则称为一个圈，记为(vi1,vi2,vik-1,vi1)。若链(vi1,vi2,vik)中，,点 vi1,vi2,vik 都是不同的，则称之为初等链；若圈(vi1,vi2,vik-1,vi1)中 vi1,vi2,vik-1 都是不同的，则称之为初等圈；若链（圈）中含的边均不同，则称之为简单链（圈）。以后说到链（圈），除非特别交代，否则均指初等链（圈）。图 G 中，若任何两点之间，至少有一条链，则称 G 是连通图，否则称为不连通图。若 G 是不连通图，它的每个连通的部分称为 G 的一个连通分图（也简称为分图）。给定一个图 G=(V,E)，如果 G/=(V/,E/)，使 V=V/及 EE/，则称 G/是 G 的一个支撑子图。设 vV，用 G-v 表示从图 G 中去掉点 v 及 v 的关联边后得到的一个图。如下图所示：,现在讨论有向图的情形。设给定一个有向图 D=(V,A)，从 D 中去掉所有弧上的箭头，就得到一个无向图，称之为 D 的基础图，记为 G(D)。给 D 中的一条弧 a=(u,v)，称 u 为 a 的始点，v 为 a 的终点，称弧 a 是从 u 指向 v 的。,v1,v2,v3,v4,v5,v1,v2,v4,v5,v1,v2,v3,v4,v5,设(vi1,ai1,vi2,ai2,vik-1,aik-1,vik)是 D 中的一个点弧交错序列，如果这个序列在基础图 G(D)中所对应的点边序列是一条链，则称这个点弧交错序列是 D 的一条链。类似定义圈和初等链（圈）。如果(vi1,ai1,vi2,ai2,vik-1,aik-1,vik)是 D 中的一条链，并且对 t=1，k-1，均有 ait=(vit,vit+1)，则称之为从 vi1 到 vik 的一条路。若路的第一个点和最后一点相同，则称之为回路。类似定义初等路（回路）。对于无向图，链与路（圈与回路）这两个概念是一致的。类似于无向图，可定义简单有向图、多重有向图。以后除非特别交代，否则，说到图均指简单图。第二节 树,2.1 树及其性质 在各式各样的图中，有一类图是极其简单然而却很有用的，这就是树。定义1：一个无圈的连通图称为树。下面介绍树的一些重要性质。定理3：设图 G=(V,E)是一个树，p(G)2，则 G 中至少有两个悬挂点。证明：令 P=(v1,v2,vk)是 G 中含边数最多的一条初等链，因为 p(G)2，并且 G 是连通的，故链 P 中至少有一条边，从而 v1与 vk 是不同的。现在来证明：v1 是悬挂点，即 d(v1)=1。用反证法，如果 d(v1)2，则存在边 v1,vm，使 m2。若点 vm 不在 P 上，那么(vm,v1,v2,vk)是 G 中的一条初等链，,它所含边数比 P 多一条，这与 P 是含边数最多的初等链相矛盾。若点 vm 在 P 上，那么(v1,v2,vm,v1)是G 中的一个圈，这又与树的定义相矛盾。于是必有 d(v1)=1，即 v1 是悬挂点。同理可证 vk 也是悬挂点。因而G 中至少有两个悬挂点。定理4：图 G=(V,E)是一个树的充分必要条件是G不含圈，且恰有 p-1 条边。证明：“必要性”：设G是一个树，根据定义，G不含圈，故只要证明 G 恰有 p-1 条边。对点数 p 施行数学归纳法。当 p1，2时，结论显然成立。假设对点数 pn时，结论成立。设树 G 含有n+1个点。由定理3，G 含有悬挂点，设 v1 是 G 的一个悬挂点，考虑图 G-v1，易见 p(G-v1)=n，q(G-v1)=q(G)-1。因 G-v1 是 n 个点的树，由归纳假设，q(G-v1)n-1，于是,q(G)=q(G-v1)+1=(n-1)+1=n=p(G)-1“充分性”：只要证明 G 是连通的。用反证法，设 G 是不连通的，G 含有 s 个连通分图 G1,G2,Gs，(s2)。因每个 Gi(i=1，s)是连通的，并且不含圈，故每个 Gi(i=1，s)是树，设 Gi 有 pi 个点，则由必要性，Gi 有 pi1条边，于是：这与 q(G)=p(G)-1的假设相矛盾。定理5：图 G=(V,E)是一个树的充分必要条件是G 是连通图，并且 q(G)=p(G)-1。证明：“必要性”：设 G 是树，根据定义，G 是连通,图，由定理4，q(G)=p(G)-1。“充分性”：只要证明 G 不含圈，对点数施行归纳法。当 p1，2时，结论显然成立。设 p(G)n(n1)时结论成立。现设 p(G)n1，首先证明 G 必有悬挂点。若不然，因 G 是连通的，且 p(G)2，故对每个点 vi，有 d(vi)2。从而：这与 q(G)=p(G)-1相矛盾，故 G 必有悬挂点，考虑 G-v1，这个图仍然是连通的，q(G-v1)=q(G)-1=p(G)-2=p(G-v1)-1由归纳假设知道 G-v1不含圈，于是 G 也不含圈。定理6：图 G 是树的充分必要条件事任意两个顶点之,间恰有一条链。证明：“必要性”：因 G 是连通的，故任意两个点之间至少有一条链。但如果某两个点之间有两条链的话，那么图 G 中含有圈，这与树的定义相矛盾，从而任何两个点之间恰有一条链。“充分性”：设图 G 中任两个点之间恰有一条链，那么易见 G 是连通的。如果 G 中含有圈，那么这个圈上的两个顶点之间有两条链，这与假设相矛盾，故 G 不含圈，于是 G 是树。由这个定理，很容易推出如下结论：（1）从一个树中去掉任意一条边，则余下的图是不连通的。由此可知，在点集合相同的所有图中，树是含边数最少的连通图。,（2）在树中，不相邻的两个点间添上一条边，则恰好得到一个圈。进一步说，如果再从这个圈上任意去掉一条边，可以得到一个树。2.2 图的支撑树定义2：设图 T=(V,E/)是图 G=(V,E)的支撑子图，如果图 T=(V,E/)是一个树，则称 T 是 G 的一个支撑树。若 T=(V,E/)是 G=(V,E)的一个支撑树，则显然，树 T 中边的个数是 p(G)-1，G 中不属于树 T 的边数是：q(G)-p(G)+1。定理7：图 G 有支撑树的充分必要条件是图 G 是连通的。证明：必要性是显然的。,“充分性”：设图 G 是连通图，如果 G 不含圈，那么 G 本身就是一个树，从而 G 是它自身的一个支撑树。现假设 G 含圈，任取一个圈，从圈中任意地去掉一条边，得到图 G 的一个支撑子图 G1。如果 G1 不含圈，那么 G1 就是 G 的一个支撑树（因为 G1 的顶点数与 G 相同，且连通）；如果 G1 仍然含圈，那么从 G1 中任取一个圈，从圈中再任意去掉一条边，得到图 G 的一个支撑子图 G2，如此重复，最终可以得到 G 的一个支撑子图 Gk，它不含圈，于是 Gk 是 G 的一个支撑树。定理7充分性的证明，提供了一个寻求连通图的支撑树的方法。这就是任取一个圈，从圈中去掉一个边，对余下的图重复这个步骤，直到不含圈时为止，即得到一个支撑树。称这种方法为“破圈法”。,也可以用另一种方法来寻求连通图的支撑树。在图中任取一条边 e1，找一条与 e1 不构成圈的边 e2，再找一条与 e1、e2 不构成圈的边 e3，一般，设已有e1，e2、ek，找一条与 e1，e2、ek 中的任何一些边不构成圈的边 ek+1。重复这个过程，直到不能进行为止。这时，由所有取出的边所构成的图就是一个支撑树，称这种方法为“避圈法”。2.3 最小支撑树问题定义3：给图 G=(V,E)，对 G 中的每一条边 ui,vj，相应地有一个数 wij，则称这样的图 G 为赋权图，wij 称为边 ui,vj上的权。这里所说的“权”，是指与边有关的数量指标。根据实际问题的需要，可以赋予它不同的含义，如表示距离、时间、费用等等。,赋权图在图的理论及其应用方面有着重要的地位。赋权图不仅指出各个点之间的邻接关系，而且同时也表示出各点之间的数量关系。所以，赋权图被广泛地应用于解决工程技术及科学生产管理等领域的最优化问题。最小支撑树问题就是赋权图上的最优化问题之一。设有一个连通图 G=(V,E)，每一个边 e=ui,vj，有一个非负权 w(e)=wij(wij 0)。定义4：如果 T=(V,E/)是 G 的一个支撑树，称 E/中所有边的权之和为支撑树 T 的权，记为 w(T)，即：如果支撑树 T*的权 w(T*)是 G 的所有支撑树中权最,小者，则称 T*是 G 的最小支撑树（也称最小树）。即有：式中对 G 的所有支撑树 T 取最小。最小支撑树问题就是要求给定连通赋权图 G 的最小支撑树。假设给定一些城市，已知每对城市间交通线的建造费用。要求建造一个联结这些城市的交通网，使总的建造费用最小，这个问题就是赋权图上的最小树问题。下面介绍求最小树的两个方法。方法一：避圈法(kruskal)开始选一条最小权的边，以后每一步中，总从与已选出的边不构成圈的那些未选边中，选出一条权最小的。,（每一步中，如果有两条或两条以上的边都是权最小的边，则从中任选一条）。算法的具体步骤如下：第一步：令 i=1，E0=，（表示空集）；第二步：选一条边 eiEEi-1，使 ei 是使(V,Ei-1ei)不含圈的所有边 e(eEEi-1)中权最小的边。令 Ei=Ei-1ei，如果这样的边不存在，则T=(V,Ei-1)就是最小树；第三步：把 i 换成 i+1，转入第二步。,v1,v2,v3,v4,v5,v6,v1,v2,v4,v3,v5,v6,6,5,1,7,2,5,3,4,4,现在来证明方法一的正确性。令 G=(V,E)是连通赋权图，根据2.2中所述可知：方法一终止时，T=(V,Ei-1)是支撑树，并且这时i=p(G)。记：E(T)=e1，e2、ep-1，式中 p=p(G)，T 的权为：用反证法来证明 T 是最小支撑树，设 T 不是最小支撑树，在 G 的所有支撑树中，令 H 是与 T 的公共边数最多的最小支撑树。因 T 与 H 不是同一个支撑树，故 T 中至少有一条边不在 H 中。令 ei(1 i p-1)是第一个不属于 H 的边，把 ei 放入 H 中，必得到一个且仅一个圈，记这个圈为 C。因为 T 是不含圈的，故 C 中必有一条边不属于 T，记这条边为 e。在 H 中去掉 e，增加 ei，就得到 G 的另一个支撑树 T0，,可见：W(T0)=w(H)+w(ei)-w(e)因为 w(H)W(T0)，推出 w(e)w(ei)。但根据算法，ei 是使(V,e1，e2、ei)不含圈的权最小的边，而(V,e1，e2、ei-1、e)也是不含圈的，故必有 w(ei)w(e)，从而 w(ei)w(e)，也就是 W(T0)=w(H)。这就是说 T0 也是 G 的一个最小支撑树，但是 T0 与 T 的公共边数比 H 与 T 的公共边数多一条，这与 H 的选取相矛盾。方法二：破圈法任取一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）。在余下的圈中，重复这个步骤，直至,得到一个不含圈的图为止，这时的图便是最小树。第三节 最短路问题3.1 引例 已知如下图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用。现在某人要从 v1 出发，通过这个交通网到 v8 去，求使总费用最小的旅行路线。,v1,v2,v3,v4,v5,v6,v7,v8,v9,1,10,2,2,6,2,4,3,2,6,3,10,4,3,6,1,从这个例子可以引出一般的最短路问题，即给了一个有向图 D=(V,A)，对于每一个弧 a=(vi,vj)，相应地有权 w(a)=wij，又给定 D 中的两个顶点 vs,vt。设 P是 D 中从 vs 到 vt 的一条路，定义路 P 的权是 P 中所有弧的权之和，记为 w(P)。最短路问题就是要在所有从 vs 到 vt 的路中，求一条权最小的路，即求一条从 vs 到 vt 的路 P0，使得：式中对 D 中所有从 vs 到 vt 的路 P 取最小，称 P0 是从 vs 到 vt 的最短路。路 P0 的权称为从 vs 到 vt 的距离，记为 d(vs,vt)。显然 d(vs,vt)与 d(vt,vs)不一定相等。最短路问题是重要的最优化问题之一，它不仅可以,直接应用于解决生产实际的许多问题，诸如管道铺设、路线安装、厂区布局、设备更新等，而且经常被作为一个基本工具，用于解决其他最优化问题。3.2 最短路算法 本节将介绍在一个赋权有向图中寻求最短路的方法，这些方法不仅求出了从起点 vs 到终点 vt 的最短路，更是求出了从给定一个点 vs 到任意一个点 vj 的最短路。如下事实经常要利用到的，即：如果 P 是有向图 D 中从 vs 到 vj 的最短路，vi 是 P 中的一个点，那么，从 vs 沿 P 到 vi 的路是从 vs 到 vi 的最短路。首先介绍所有 wij 0 的情形下，求最短路的方法。当所有的 wij 0 时，目前公认最好的方法是由 Dijkstra 于1959年提出来的。Dijkstra方法的基本思想是从 vs 出发，逐步地向,外探寻最短路。执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从 vs到 该点的最短路的权（称为 P 标号），或者是从 vs 到 该点的最短路的权的上界（称为 T 标号），方法的每一步是去修改 T 标号，并且把某一个具 T 标号的点改变为具 P 标号的点，从而使 D 中具 P 标号的顶点数多一个，这样，至多经过 p-1 步，就可以求出从 vs到各个点的最短路。在下述 Dijkstra方法具体步骤中，用 P，T 分别表示某个点的 P 标号、T 标号，Si 表示第 i 步时，具 P 标号点的集合。为了求出从 vs 到各点的距离的同时，也求出从 vs 到各点的最短路，给每一个点 v 以一个 值，算法终止时，如果(v)=m，表示在从 vs 到 v 的最短路上，v 的前一个点是 vm；如果(v)=M，,则表示 D 中不含从 vs 到 v 的路；(v)=0 表示 v=vs。对于给定的赋权有向图 D=(V,A)，Dijkstra 方法的具体步骤如下：开始(i=0)，令 S0=vs，P(vs)=0，(vs)=0，对每一个 vvs，令 T(v)=+，(v)=M，令 k=s；(1)如果 Si=V，算法终止，这时，对每个 vSi，d(vs,v)=P(v)；否则转入（2）；(2)考查每个使(vk,vj)A 且 vjSi 的点 vj；如果 T(vj)P(vk)+wkj，则把 T(vj)修改为 P(vk)+wkj，把(vj)修改为 k；否则转入（3）；(3),k=ji，i:=i+1，转入（1）；否则终止，这时对每一个vSi，d(vs,v)=P(v)，而对每个 vSi,d(vs,v)=T(v)。上面介绍了求一个赋权有向图中，从一个顶点 vs 到各个顶点的最短路。对于赋权无向图 G=(V,E)，因为沿边vi,vj既可以从 vi 到达 vj，也可以从 vj 到达 vi，所以边vi,vj可以看着是两条弧(vi,vj)及(vj,vi)，它们具有相同的权 wvi,vj。这样，在一个赋权无向图中，如果所有的 wij 0，只要把 Dijkstra方法中的第2步，即（2）“考查每个使(vk,vj)A 且 vjSi 的点 vj”改为（2）考查每个使 vk,vjE 且 vjSi 的点 vj”，同样地可以求出从 vs 到各个顶点的最短路（对于无向图来说，即为最短链）。现在来证明 Dijkstra方法的正确性。只要证明对于每,一个点 vSi，P(v)是从 vs 到 v 的最短路的权，即 d(vs,v)=P(v)即可。对 i 施行归纳法，i=0 时结论显然成立。设对 i=n 时，结论成立，即对每一个点 vSn，d(vs,v)=P(v)。现在考查 i=n1 时，因 Sn+1=Snvjn，所以只要证明 d(vs,vjn)=P(vjn)。根据算法，vjn 是这时的具最小 T 标号的点，即：这里为了清晰起见，用 Tn(v)表示当 i=n 时执行步骤（3）时点 v 的 T 标号。假设 H 是 D 中任一条从 vs 到 vjn 的路，因为 vsSn，而 vjnSn，那么从 vs 出发，沿 H 必存在一条弧，它的始点属于 Sn，而终点不属于 Sn。假设(vr,vl)是的一条这样的弧，即：,H=(vs,vr,vl,vjn)W(H)=w(vs,vr)+wrl+w(vl,vjn)由归纳假设，P(vr)是从 vs 到 vr 的最短路的权，于是：W(H)P(vr)+wrl+w(vl,vjn)根据方法中 T 标号的修改规则，因 vrSn，vlSn，所以，P(vr)+wrl Tn(vl)。而 Tn(vl)Tn(vjn)，所以：W(H)Tn(vjn)+w(vl,vjn)Tn(vjn)又因为所有的 wij 0，从而，w(vl,vjn)0。这就证明了 Tn(vjn)是从 vs 到 vjn 的最短路的权，由方法，P(vjn)=Tn(vjn)，这样就证明了：d(vs,vjn)=P(vjn)Dijkstra 算法只适用于所有 wij 0 的情形，当赋权有,向图中存在负权时，则算法失效。如下图所示：如果用 Dijkstra 方法，可得出从 v1 到 v2 的最短路的权是 1，但这显然是不对的，因为从 v1 到 v2 的最短路是(v1,v3,v2)，权是1。下面介绍当赋权有向图 D 中，存在具负权的弧时，求最短路的方法。为方便起见，不妨假设从任一个点 vi 到任一个点 vj 都有一条弧（如果(vi,vj)A，则添加弧(vi,vj)，且,v1,v2,v3,1,2,-3,令 wij=+）。显然，从 vs 到 vj 的最短路总是从 vs 出发，沿着一条路到某个点 vi，再沿(vi,vj)到达 vj，由本节开始时介绍的一个结论可知，从 vs 到 vi 的这条路必定是从 vs 到 vi 的的最短路，所以 d(vs,vj)必满足如下方程：为求得这个方程的解 d(vs,v1),d(vs,v2),d(vs,vp)，可用如下的递推公式：开始时，令：d(1)(vs,vj)=wsj(j=1,2,p)对 t=2,3,，,j=1,2,p若进行到某一步，例如第 k 步时，对所有 j=1,2,p，有：d(t)(vs,vj)=d(t-1)(vs,vj)则 d(t)(vs,vj)，j=1,2,p，就是 vs 到各点的最短路。例：求下图所示赋权有向图中从 v1 到各点的最短路。解：利用上述递推公式，求解结果如下表所示（表中未填,v1,v2,v3,v4,v5,v6,v7,v8,6,-1,3,8,-2,-3,-5,1,2,-1,2,-1,1,1,7,-5,-3,数字的空格内表示）。可以看到，当 t 4时，对所有 j=1,8，有：d(t)(v1,vj)=d(t-1)(v1,vj)于是，表中最后一列的数值就是从起点 v1 到 v1、v2、v8 的最短路的权。为了进一步求得从 vs 到各点的最短路，可以类似于 Dijkstra 方法中，给每一个点以 值，开始时，令：(vs)=0，(vi)=s(ij)；在迭代过程中，如果：则把这时的(vj)修改为 i0。迭代终止时。根据各点的 值，可以得到从 vs 到各点的最短路。,定义5：设 D 是赋权有向图，C 是 D 中的一个回路，如果 C 的权 w(C)小于零，则称 C 是 D 中的一个负回路。根据定义，我们可以证明如下结论：（1）如果 D 是不含负回路的赋权有向图，那么，从 vs 到任一个点的最短路必可取为初等路，从而最多包含 p-2 个中间点；（2）上述递推公式中的 d(t)(vs,vj)是在至多包含 t-1 个中间点的限制条件下，从 vs 到 vj 的最短路的权。由（1），（2）可知：当 D 中不含负回路时，上述算法最多经过 p-1 次迭代必定收敛，即对所有的 j=1,p，均有 d(t)(vs,vj)=d(t-1)(vs,vj)，从而求出从 vs 到各个顶点的最短路的权。,如果经过 p-1 次迭代，存在某个 j，使得：d(t)(vs,vj)d(t-1)(vs,vj)则说明 D 中含有负回路。显然，这时，从 vs 到 vj 的路的权是没有下界的。为了加快收敛速度，可以利用如下的递推公式：J.Y.Yen 提出了一个改进的递推算法：,对 t=2,4,6,，按 j 1,2,p 的顺序计算：对 t=3,5,7,，按 j p,p-1,1 的顺序计算：同样地，当对所有的 j=1,p，均有：d(t)(vs,vj)=d(t-1)(vs,vj)时，算法终止。3.3 应用举例例13（设备更新问题）。某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还,是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧设备，则需要支付一定的维修费用。现在的问题是如何制定一个几年之内的设备更新计划，使得总的支付费用最少。我们用一个五年之内要更新某种设备的计划为例，若已知该种设备在各年年初的价格为：还已知使用不同时间(年)的设备所需维修费用为：,可供选择的设备更新方案有很多。例如，每年都购置一台新设备，则其购置费用为 111112121359，而每年支付的维修费用为5，五年合计为25。于是五年总的支付费用为 592584。又例如决定在第一、三、五年各购进一台，这个方案的设备购置费为11121336，维修费为5656527。五年总的支付费用为63。如何制定使得总的支付费用最少的设备更新计划？可以把这个问题化为最短路问题，见下图：,v1,v2,v3,v4,v5,v6,16,16,17,17,18,59,41,30,22,23,41,31,30,23,22,用点 vi 代表“第 i 年年初购进一台新设备”这种状态(这里的 v6 可理解为第五年年底)。从 vi 到 vi+1，v6 各画一条弧。弧(vi,vj)表示在第 i 年年初购进的设备一直使用到第 j 年年初（即第 j-1 年年底）。每条弧的权可按已知资料计算出来。例如，(v1,v4)表示第1年年初购进一台新设备（支付购置费11），一只用到第3年年底（支付维修费56819），故(v1,v4)上的权为 30。这样，该问题就转换成为寻求从 v1 到 v6 的最短路的问题。按求最短路的计算方法，v1,v3,v6 及 v1,v4,v6 均为最短路，即有两个最有方案。一个是在第1、3年初各购置一台新设备；另一个方案是在第1、4 年初各购置一台新设备。五年总的支付费用为 53。,3.4 最短路方法的数学模型已知赋权有向图 D=(V,A,W)，其中：V=v1,v2,vn，v1 为起点，vn 为终点；A=e1,e2,em；B=(bij)nm 为 D 的点边关联矩阵；b=(b1,b2,bn)，b11，bn=-1，bi=0,1 i n-1；xi 为决策变量，当最短路线通过弧 ei 时取值为1，否则取值为0。CT=(c1,c2,cm)为各对应弧上的权；XT=(x1,x2,xm)，则从 v1 到 vn 的最短路数学模型为：,第四节 网络最大流问题许多系统包含了流量问题。例如，公路系统中有车辆流，控制系统中有信息流，供水系统中有水流，金融系统中有现金流等。如下图是联结某产品产地 v1 和销售地 v6 的交通网，每一弧(vi,vj)代表从 vi 到 vj 的运输线，产品经这条弧由 vi 输送到 vj，弧旁的数字表示这条运输线的最大通过能力。产品经过交通网从 v1 输送到 v6。现在要求制定一个运输方案，使从 v1 运到 v6 的产品数量最多。如下图(2)给出了一个运输方案，每条弧旁的数字表示在这个方案中，每条运输线上的运输量。这个方案使 8 个单位的产品 v1 运到 v6，在这个交通网上输送量是否还可以增多，或者说在这个运输网络中，,从 v1 到 v6 的最大输送量是多少？这就是我们这一节要研究的问题。(1)(2)4.1 基本概念与基本定理1.网络与流定义6：给定一个有向图 D=(V,A)，在 V 中指定了一点称为发点(记为 vs)，而另一个点称为收点(记为 vt)，其余的点叫着中间点。对于每一个弧(vi,vj)A，对应有一个 c(vi,vj)0（或简写成 cij），称,v1,v2,v3,v4,v5,v6,v1,v2,v3,v4,v5,v6,10,8,4,3,5,6,5,3,11,17,为弧的容量。通常我们就把这样的 D 叫做一个网络。记做：D=(V,A,C)所谓网络上的流，是指定义在弧集合 A 上的一个函数 f=f(vi,vj)，并称 f(vi,vj)为弧(vi,vj)上的流量（有时也简记作 fij）。2.可行流与最大流在运输网络的实际问题中可以看出，对于流有两个明显的要求：一是每个弧上的流量不能超过该弧的最大通过能力（即弧的容量）；二是中间点的流量为零。因为对于每个点，运出这点的产品总量与运进这点的产品总量之差，是这点的净输出量，简称为是这点的流量；由于中间点只起转运作用，所以中间点的流量必为零。易见发点的净流出量和收点,的净流入量必相等，也是这个方案的总输送量。因此，我们有：定义7：满足下述条件的流 f 称为可行流：（1）容量限制条件：对每一个弧(vi,vj)A，0 fij cij（2）平衡条件：对于中间点，流出量等于流入量，即对每个 i(i s,t)有：对于发点 vs，记：,对于收点 vt，记：式中 v(f)称为这个可行流的流量，即发点的净输出量或收点的净输入量。可行流总是存在的。比如令所有弧的流量 fij=0，就得到一个可行流（称为零流）。这时 v(f)=0。最大流问题就是求一个流 fij 使其流量 v(f)达到最大，并满足：,最大流问题是一个特殊的线性规划问题。即求一组 fij，在满足条件(1),(2)下使 v(f)达到极大。下面我们将会看到，利用图的特点，解决这个问题的方法较之线性规划的一般方法要方便、直观得多。3.增广链若给定一个可行流 f=fij，我们把网络中使 fij=cij 的弧称为饱和弧，使 fij 0 的弧称为非零流弧。若 是网络中的联结发点 vs 和收点 vt 的一条链，我们定义链的方向是从 vs 到 vt，则链上的弧被分为两类：一类是弧的方向与链的方向一致，叫做前向弧。前向弧的全体记为。另一类与链的方向相反，称为后向弧。后向弧的全体记为。,定义8：设 f 是一个可行流，是从 vs 到 vt 的一条链，若 满足下列条件，则将其称之为（关于可行流 f 的）增广链。前向弧 中的每一个弧是非饱和弧，即：当弧(vi,vj)时，0 fij cij 后向弧 中的每一个弧是非零流弧，即：当弧(vi,vj)时，0 fij cij。4.截集与截量设 S，T V，S T，我们把始点在 S 中，终点在 T 中的所有弧构成的集合，记为(S,T)。定义9：给定一个网络 D=(V,A,C)，若点集 V 被划分为两个非空集合 V1 和 V2，V1 V2 V，V1 V2，使得 vsV1，vtV2，则把弧集(V1,V2),称为是（分离 vs 和 vt 的）截集。显然，若把某一截集的弧从网络中去掉，则从 vs 到 vt 便不存在路。所以，直观上说，截集是从 vs 到 vt 的必经之道。定义10：给一截集(V1,V2)，把截集(V1,V2)中所有弧的容量之和称为这个截集的容量（简称为截量），记为 c(V1,V2)，即：容易证明，任何一个可行流的流量 v(f)都不会超过任一截集的容量。即：v(f)c(V1,V2)显然，若对于一个可行流 f*，网络中有一个截集,(V1*,V2*)，使 v(f*)=c(V1*,V2*)，则 f*必是最大流，而(V1*,V2*)必定是 D 中的所有截集中，容量最小的一个，即最小截集。定理8：可行流 f*是最大流，当且仅当不存在关于f*的增广链。证明：首先若 f*是最大流，设 D 中存在关于 f*的增广链，令：由增广链的定义，可知 0，令：,容易验证 f*是一个可行流，v(f*)=v(f*)+v(f*)。这与 f*是最大流的假设相矛盾。其次，现在假设 D 中不存在关于f*的增广链，证明 f*是最大流。我们利用下面的方法来定义 V1*：令：vsV1*；若：viV1*，且 fij*0，则令 vjV1*；因为不存在关于f*的增广链，所以 vtV1*。记 V2*=VV1*，于是得到一个截集(V1*,V2*)。显然必有：,所以，v(f*)=c(V1*,V2*)。于是，f*必是最大流。由上述证明过程中可见，若 f*是最大流，则网络中必存在一个截集(V1*,V2*)，使：v(f*)=c(V1*,V2*)。于是，有如下重要的结论：最大流量最小截集定理：任一个网络 D 中，从 vs 到 vt 的最大流量等于分离 vs，vt 的最小截集的截量。定理8 为我们提供了寻求网络中最大流的一个方法。若给定了一个可行流 f，只要判断 D 中有无关于 f 的增广链。如果有增广链，则可以按定理8 前半部证明中的办法，改进 f，得到一个流量增大的可行流。如果没有增广链，则得到最大流。而利用定理8 后半部证明中定义 V1*的办法，可以根据 vt 是否属于 V1*来判断 D 中有无关于 f 的增广链。,实际计算时，用给顶点标号的方法来定义 V1*。在标号的过程中，有标号的顶点表示是 V1*中的点，没有标号的点表示不是 V1*中的点。一旦 vt 有了标号，就表明找到一条增广链；如果标号过程无法进行下去，而 vt 尚未标号，则说明不存在增广链，于是得到最大流。而且同时也得到一个最小截集。4.2 寻求最大流的标号法(FordFulkerson方法)从一个可行流出发（若网络中没有给定 f，则可以假设其为零流），经过标号过程与调整过程。1.标号过程在这个过程中，网络中的点或者是标号点（又分为已检查和未检查两种），或者是未标号点。每个标号点的标号包含两部分：第一个标号表明它的标号,是从哪一点得到的，以便找出增广链；第二个标号是为了确定增广链的调整量 用的。标号过程开始，总先给 vs 标上(0,+)，这时 vs 是标号而未检查的点，其余都是未标号点。一般地，取一个标号而未检查的点 vi，对一切未标号的点 vj：（1）若在弧(vi,vj)上，fij0，则给 vj 标号(-vi,l(vi)这里 l(vj)=minl(vi),fji。这时点 vj 成为标号而未检查的点。于是 vi 成为标号而已检查过的点。重复上述步骤，一旦 vt 被标上号，表明得到一条从 vs 到 vt 的增广链,，转入调整过程。若所有标号都是已检查过的，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。2.调整过程首先按 vt 及其他的点的第一个标号，利用“反向追踪”的办法，找出增广链。令调整量 是 l(vt)，即 vt 的第二个标号。令：去掉所有的标号，对新的可行流 f/=f ij/，重新进入标号过程。,例：用标号法求如下图所示网络的最大流。解：（1）标号过程 首先给 vs 标上(0,+)，检查 vs，在弧(vs,v2)上，fs2=cs2=3，不满足标号,vs,vt,v1,v2,v3,v4,(3,3),(5,1),(2,2),(4,3),(1,1),(5,3),(2,1),(1,1),(3,0),条件。弧(vs,v1)上，fs1=10，则给 v2 记下标号为(v1,l(v2)，其中：l(v2)minl(v1),f21=min4,1=1 检查 v2，在弧(v2,v4)上，f24=30，则给 v3 记下标号为(v2,l(v3)，其中：l(v3)minl(v2),f32=min1,1=1,在 v3,v4 中任选一个检查。例如：在弧(v3,vt)上，f3t=1 c3t=2，则 vt 的标号：(v3,l(vt)，其中：l(vt)minl(v3),(c3t-f3t)=min1,2-1=1因 vt 有了标号，故转入调整过程。（2）调整过程按点的第一个标号找到一条增广链，如下图红箭头线所示：,vs,v1,v2,v3,v4,vt,(3,3),(5,1),(2,2),(4,3),(1,1),(3,0),(1,1),(5,3),(2,1),(0,+),(vs,4),(-v1,1),(-v2,1),(v2,1),(v3,1),显然：(vs,v1),(v3,vt)，(v2,v1),(v3,v2)按 1在 上调整 f：在 上：fs1+=1+1=2；f3t+=1+1=2；在 上：f21-1-10；f32-1-10；其余的 fij 不变。调整后得如下图所示的可行流，对这个可行流进入标号过