1、第六章 离散优化模型及算法设计浙江大学数学建模基地浙江大学数学建模基地在上一章中在上一章中,我们介绍了与计算复杂性有关的一些基本概念我们介绍了与计算复杂性有关的一些基本概念.人们发现人们发现,在离散问题中存在着两个互不相交的类：在离散问题中存在着两个互不相交的类：P P类与类与NPNP完全类（若完全类（若P PNPNP）。）。前者具有求解的有效算法而后者不可能有这种算法。从这一点上讲，前者具有求解的有效算法而后者不可能有这种算法。从这一点上讲，P P问题可以看成是一类具有良好性质而又较容易求解的问题，而问题可以看成是一类具有良好性质而又较容易求解的问题，而NPNP完全问完全问题则是固有地难解的
2、。题则是固有地难解的。在在5.45.4中看到，有着广泛应用背景的线性规划问题是一个中看到，有着广泛应用背景的线性规划问题是一个P P问题。这样，问题。这样，作为线性规划子问题的运输问题及作为运输问题子问题的指派问题自然作为线性规划子问题的运输问题及作为运输问题子问题的指派问题自然更是更是P P问题。虽然从平均的角度讲，人们似乎更常遇到问题。虽然从平均的角度讲，人们似乎更常遇到NPNP完全问题，但完全问题，但P P仍不失为一个十分重要的问题类。一方面，很多仍不失为一个十分重要的问题类。一方面，很多P P问题象线性规划一样有问题象线性规划一样有着极广泛的应用前景，且它们本身又是十分有趣的；另一方面
3、，它们也着极广泛的应用前景，且它们本身又是十分有趣的；另一方面，它们也是研究一些更为复杂、难解的问题时经常被采用的研究工具。在本章中，是研究一些更为复杂、难解的问题时经常被采用的研究工具。在本章中，将再介绍一些经常遇到的将再介绍一些经常遇到的P P问题并给出求解它们的有效算法。问题并给出求解它们的有效算法。一、拟阵问题及贪婪算法一、拟阵问题及贪婪算法在在P类中又存在着一个被称为拟阵的具有更为良好性质的问题类，其中的类中又存在着一个被称为拟阵的具有更为良好性质的问题类，其中的任一问题均可用一种被称为贪婪法的方法来求解，而这一性质并不是所有任一问题均可用一种被称为贪婪法的方法来求解，而这一性质并不
4、是所有的的P问题都具有的。问题都具有的。例例 6.1（最小生成树问题（最小生成树问题MST）给定一连通图给定一连通图G=（V，E），），有一表示边长的权有一表示边长的权C（e）（表示顶点间的距离或费用），求此图的具有）（表示顶点间的距离或费用），求此图的具有最小总权的生成树。最小总权的生成树。e此问题的标准形式为给定一完全图此问题的标准形式为给定一完全图G G，其每边赋有一权数，求此完全图的，其每边赋有一权数，求此完全图的最小生成树。所谓树是指连通而无圈的图，单独的一个点也可看成一颗最小生成树。所谓树是指连通而无圈的图，单独的一个点也可看成一颗树。树用树。树用(U U，T T)表示，表示，U
5、U为树的顶点，为树的顶点，T T为树的边集。不相交的树的集合为树的边集。不相交的树的集合被称为森林。一个连通图的生成树是指图中具有最多边数的一棵树。容被称为森林。一个连通图的生成树是指图中具有最多边数的一棵树。容易证明，对于一个连通图易证明，对于一个连通图G G，G G 的任一生成树必有的任一生成树必有V V-1-1条边。条边。求解最小生成树的算法主要依据下面的定理：求解最小生成树的算法主要依据下面的定理：定理定理 6.1 设设（V1，T1），），（Vk,Tk）为连通图为连通图G中的森林，中的森林，V1 U V2U Vk=V。k,若仅有一个顶点在若仅有一个顶点在Vi中的具有最小权的边为（中的具
6、有最小权的边为（,u），），则必有一棵则必有一棵G的最小生成树包含边（的最小生成树包含边（,u）。）。,1i根据定根据定1可以作了如下算法：任选一点可以作了如下算法：任选一点 ，令，令 若若V1=V，停；否则，找出仅有一个顶点在，停；否则，找出仅有一个顶点在V1中的边里具有最小权的边中的边里具有最小权的边（,u），设，将），设，将u加入加入V1（,u）加入）加入T。重复上述步骤，直到。重复上述步骤，直到V1=V。1 11:,:.VT 证明：设：设G的一棵最小生成树（的一棵最小生成树（V，T）不含（）不含（,u）。将（）。将（,u）加入）加入T，由于（由于（V，T）是生成树，）是生成树，T U（
7、,u）中含有过（）中含有过（,u）的唯一的圈。不）的唯一的圈。不妨设妨设 ，则，则 ，此圈中的点不全由，此圈中的点不全由Vi中的点组成中的点组成,因此必存在因此必存在圈中的另一边圈中的另一边 。删去边。删去边 得到一新的生成树（得到一新的生成树（V，T1），），T1=，须其总权不超过（，须其总权不超过（V，T）的权）的权,即（即（V，T）是包含边（是包含边（,u）的最小生成树。）的最小生成树。iViV,iiuuu,uu例例6.2 求图求图9.1中图中图G的最小生成树。的最小生成树。解：不妨从顶点开始寻找。不妨从顶点开始寻找。标号标号1，先加入，先加入 （因为边权（因为边权最小），最小），标号标
8、号2。再加入。再加入 标号标号3。，每次加入一条一顶点已标，每次加入一条一顶点已标号加一顶点未标号而又具有最小权的边，直到所有顶点均标号为止。找号加一顶点未标号而又具有最小权的边，直到所有顶点均标号为止。找到的最小生成树已用又线标在图到的最小生成树已用又线标在图6.2中。中。111,V212244 容易看出算法的计算量为容易看出算法的计算量为O (V)2 ，所以此算法是有效算法，若，所以此算法是有效算法，若G具有具有O（）条边，其中）条边，其中n=V ，计算量的界还是不能改进的，因为每条，计算量的界还是不能改进的，因为每条边至少应被检查一次。边至少应被检查一次。2nC由例由例6.2可以看出，算
9、法执行的每一步均加入一条可以加入的（即不生成可以看出，算法执行的每一步均加入一条可以加入的（即不生成圈的）具有最小权的边，而不去考虑它对以后选取的影响，这种算法被圈的）具有最小权的边，而不去考虑它对以后选取的影响，这种算法被称为贪婪算法。称为贪婪算法。例例6.3 (入树问题入树问题)给出一个有向图给出一个有向图G=（V，A），对），对A中的每一条孤中的每一条孤e，给，给出一个权出一个权C（e），求），求A的一个具有最大权（或最小权）的子集的一个具有最大权（或最小权）的子集B，要求，要求B中任意两条孤都没有公共的终点。中任意两条孤都没有公共的终点。考察下面的入树问题实例：考察下面的入树问题实例：
10、例例6.4 给出有向图给出有向图G=（V，A）（图（图9.3），孤上标出的数字为该边的，孤上标出的数字为该边的权，求此图具有最大权的入树。权，求此图具有最大权的入树。解：由于入树不能包含具有公共终点的孤，故对每一顶点解：由于入树不能包含具有公共终点的孤，故对每一顶点 只能选取只能选取一条入孤。为使选出的弧具有最大权，只需要对每一顶点选取权最大的一条入孤。为使选出的弧具有最大权，只需要对每一顶点选取权最大的入孤，可用计算量为入孤，可用计算量为O O（V VE E）的贪婪法求解，具有最大权的入树）的贪婪法求解，具有最大权的入树为为 。i 1221244553,类似地，出树问题也可以用贪婪法求解。类
11、似地，出树问题也可以用贪婪法求解。例例6.5 (矩阵拟阵问题矩阵拟阵问题)给出一个矩阵给出一个矩阵Amxn，记其，记其n个列向量为个列向量为e1,，en。设对每一列向量设对每一列向量en已指定一权已指定一权C（en）求）求 的一个线性无的一个线性无关的子集，它具有最大的权和。关的子集，它具有最大的权和。1,iin易见，这一问题也可以用贪婪法求解。集合易见，这一问题也可以用贪婪法求解。集合 的线性无关的的线性无关的子集被称为独立子集，利用贪婪法必可求得具有最大权的独立子集，可用子集被称为独立子集，利用贪婪法必可求得具有最大权的独立子集，可用线性代数知识加以证明线性代数知识加以证明（见习题（见习题
12、1）。1,iin例例6.6 求矩阵求矩阵A的列向量具有最大权和的独立子集的列向量具有最大权和的独立子集7*45762101543100012731214531011AC(C(e ei i)8 4 7 5 2 6 48 4 7 5 2 6 4解：采用贪婪法，先取权最大的列采用贪婪法，先取权最大的列e1，同时对，同时对A作高斯消去，逐次加入作高斯消去，逐次加入线性无关的向量：线性无关的向量：A的列向量中具有最大权的独立子集为的列向量中具有最大权的独立子集为 。1354取e6取e4取e3?45110205431000334211045310111231110543100033421104531011
13、A4/904/194/90204/514/34/100033421104531011定义定义6.1 (拟阵拟阵)设设E是一个有限集，是一个有限集，为为E的部分子集构成的封闭系统（即的部分子集构成的封闭系统（即若若 ，则必有，则必有 ）。若）。若M=（E，）上的离散优化问题的每一）上的离散优化问题的每一实例均可用贪婪算法求出最优解，则称实例均可用贪婪算法求出最优解，则称M为一拟阵。（注：为一拟阵。（注：被称为独立系被称为独立系统）。统）。,AAA现以矩阵拟阵为例，对定义现以矩阵拟阵为例，对定义6.1作一说明。作一说明。对矩阵拟阵的每一实例，对矩阵拟阵的每一实例，E=e1,en为矩阵列向量的集合，
14、为矩阵列向量的集合，为为E的线性无的线性无关子集构成的系统，称为独立系统，其元素被称为独立子集。由于关子集构成的系统，称为独立系统，其元素被称为独立子集。由于E的任一的任一线性无关子集的子集也是线性无关子集的子集也是E的线性无关子集，故独立系统的线性无关子集，故独立系统是封闭的。又由是封闭的。又由于这一离散优化问题的任一实例都可用贪婪法求解，故构成一拟阵，被称于这一离散优化问题的任一实例都可用贪婪法求解，故构成一拟阵，被称为矩阵拟阵。例为矩阵拟阵。例9.1被称为图拟阵，例被称为图拟阵，例9.3被称为划分拟阵。被称为划分拟阵。拟阵问题（或称拟阵结构）拟阵问题（或称拟阵结构）有一个明显而又本质的特
15、性，其任一极大独立有一个明显而又本质的特性，其任一极大独立子集中包含着相同个数的元素，从而可以引入基的概念。例如，矩阵列向子集中包含着相同个数的元素，从而可以引入基的概念。例如，矩阵列向量的所有线性无关极大组均具有相同的向量个数，这就导出了基量的所有线性无关极大组均具有相同的向量个数，这就导出了基即矩即矩阵列秩的概念。对于图拟阵，每一极大独立集均为一生成树，其边数均为阵列秩的概念。对于图拟阵，每一极大独立集均为一生成树，其边数均为|V|-1。对于划分拟阵，孤集被划分成个。对于划分拟阵，孤集被划分成个|V|个子集，每一子集由指向同一个子集，每一子集由指向同一顶点的孤组成。显然，任一极大独立集应在
16、每一子集中取一条孤，故其基顶点的孤组成。显然，任一极大独立集应在每一子集中取一条孤，故其基数为顶点个数。数为顶点个数。我们不加证明地引入下面的定理，虽然其证明并不十分困难。我们不加证明地引入下面的定理，虽然其证明并不十分困难。定理定理6.2 E为一有限集合，为为一有限集合，为E的部分子集构成的封闭独立系统。以下的部分子集构成的封闭独立系统。以下两个条件均为两个条件均为M=(E,y)构成拟阵（即其上的优化问题可用贪婪法求解）构成拟阵（即其上的优化问题可用贪婪法求解）的充分必要条件：的充分必要条件：（条件（条件2）若若I、I均为均为A的两个极大独立集，则的两个极大独立集，则|I|=|I|。AE（条
17、件（条件1）若若I、I|I|M|，G中至少含一条路，其中中至少含一条路，其中M中的边多于中的边多于M中的边，不难看出，这条路是中的边，不难看出，这条路是G的的关于关于M的增广路。的增广路。现在可以看出，找最大匹配的关键在于找增广路。读者不难用顶点标号现在可以看出，找最大匹配的关键在于找增广路。读者不难用顶点标号的办法（由未盖点出发），作出一个求解两分图匹配的增广路算法。此的办法（由未盖点出发），作出一个求解两分图匹配的增广路算法。此算法稍加改动，还可以用于非两分图的情况。算法稍加改动，还可以用于非两分图的情况。三、网络流问题三、网络流问题网络流问题是又一类具有广泛应用前景的网络流问题是又一类具
18、有广泛应用前景的P问题，本节将介绍一些有关问题，本节将介绍一些有关网络流问题的基本理论与算法。网络流问题的基本理论与算法。1、最大流问题（、最大流问题（MFP）边赋值的有向图称为网络。给定一个网络，其边赋值表示该边的容量。最边赋值的有向图称为网络。给定一个网络，其边赋值表示该边的容量。最大流问题要求在不超过边容量的前提下求出网络中两个指定顶点之间的最大流问题要求在不超过边容量的前提下求出网络中两个指定顶点之间的最大流。例如：当网络是通讯网时，我们可能会去求出网络中两个指定点间大流。例如：当网络是通讯网时，我们可能会去求出网络中两个指定点间的最大通话量；当网络是城市的街道时，我们又可能会去求两地
19、间的最大的最大通话量；当网络是城市的街道时，我们又可能会去求两地间的最大交通流，即单位时间内允许通过的车辆数等等。交通流，即单位时间内允许通过的车辆数等等。建模：建模：给定一有向图给定一有向图G=（V，A），），A的每一条孤（边）（的每一条孤（边）（i,j）上已赋一）上已赋一表示边容量的非负整数表示边容量的非负整数C（i,j）。并已指定）。并已指定V中的两个顶点中的两个顶点 s、t，分别称，分别称它们为发点和收点。它们为发点和收点。设网络中已存在一个流（不一定是最大流），记孤（设网络中已存在一个流（不一定是最大流），记孤（i,j）上的流量为）上的流量为 （i,j），记），记s发出的总流量（即发
20、出的总流量（即t收到的总流量）为收到的总流量）为 ，根据平衡条件，可，根据平衡条件，可得如下的约束条件，得如下的约束条件，有，有i 其中是其中是 指指A中以顶点中以顶点i为起点的孤集，为起点的孤集，是指是指A中以中以 i为终点的孤集为终点的孤集,(.1)式表示式表示s发出流为发出流为 ，t收入的流为收入的流为 ，其余各点只起中转作用，其余各点只起中转作用，既不增加也不消耗流量。根据边容量限止，还应有既不增加也不消耗流量。根据边容量限止，还应有 iAiA,i jC i ji jA而我们的愿望是使总流量尽可能地大。而我们的愿望是使总流量尽可能地大。即在（即在（6.1）、）、(6.2)式约束下式约束
21、下使达到最大，易见，这是一个线性规划问题的子问题，故使达到最大，易见，这是一个线性规划问题的子问题，故 类。类。PtivtsisivjijiAijiAiji若若若.0),(),(),(),(对于一个较为复杂的网络，要想直接找出最大流是不太可能的。为了简化对于一个较为复杂的网络，要想直接找出最大流是不太可能的。为了简化问题，我们先引入一些符号。问题，我们先引入一些符号。记记、为为的两个不相交的子集，的两个不相交的子集，s ，用（，）表示发，用（，）表示发点在，收点在的边集，点在，收点在的边集，记记，并定义如下的切割概念：，并定义如下的切割概念：,P tQ,i P j Qi P j QP Qi j
22、 C P QC i j定义定义6.5 （切割）（切割）设设是是的顶点集合的顶点集合的一个真子集，的一个真子集，为为关于关于的补集。若的补集。若、满足满足 且且 则称则称和和 为的一个切割。为的一个切割。PPSPtPP根据切割的定义可以看出，当和根据切割的定义可以看出，当和 为一切割时，如果去掉连接为一切割时，如果去掉连接和的和的边集（边集（，），就切断了由通往），就切断了由通往t的所有通路。所以，对网络的任一切的所有通路。所以，对网络的任一切割（割（，），），（，）必为最大流的一个上界，）必为最大流的一个上界，而而 。PPPP,P PP P例例6.9 网络如图网络如图9.6所示，边（弧）上的两
23、数字分别表示边容量及实际流所示，边（弧）上的两数字分别表示边容量及实际流量。取，则，显然量。取，则，显然、是网络的是网络的一个切割。对于这一切割容易算出一个切割。对于这一切割容易算出而网络的流量而网络的流量 。P,6,9P PC P P为了尽可能地增大网络上的流量，按如下方法作出一个和为了尽可能地增大网络上的流量，按如下方法作出一个和具有相同顶具有相同顶点并具有相同发点和收点的增广网络点并具有相同发点和收点的增广网络（）（简记（简记）。）。包含两包含两类边，对中每一条边（类边，对中每一条边（i，j）：A（1）若）若 ，作正向边（，作正向边（i，j）,规定容量规定容量 ，即剩余容量。，即剩余容量
24、。,i jC j i,C j iC j ij i（2）若）若 ，作反向边（，作反向边（j,i），），规定容量规定容量 事实上是边（事实上是边（j,i）上最多可减少的容量。）上最多可减少的容量。,0i j,Cj ij iCj i第一类边称为正规边，第二类边则称为增广边。例如由图第一类边称为正规边，第二类边则称为增广边。例如由图9.6中的流可以中的流可以作出其相应的增广网络图作出其相应的增广网络图9.7，其中实箭线为正规定，虚箭线为增广边，其中实箭线为正规定，虚箭线为增广边，边上的数字为边容量。边上的数字为边容量。如果增广网络上存在着由如果增广网络上存在着由st的通路的通路p（称为原网络的一条增广
25、路），（称为原网络的一条增广路），记记 ，则只要在，则只要在P中的一切正规边上增加流量中的一切正规边上增加流量a，而在对应，而在对应增广边（增广边（j,i），），G的边（的边（i,j）上减少流量）上减少流量a，就得到，就得到G的一个由的一个由st的增的增大了流量大了流量a的更大的流。例如，从图的更大的流。例如，从图9.7上可以找出增广路上可以找出增广路，a=2。于是，图。于是，图9.6中的流可改进增大为图中的流可改进增大为图9.8(a)中的流，总流量为中的流，总流量为7。由于其增广网络图。由于其增广网络图9.8(b)中不再存在增广路，无法中不再存在增广路，无法再继续增大。容易看出，若取再继续增
26、大。容易看出，若取s出发（在增广网络上）可到达的点的集出发（在增广网络上）可到达的点的集合为合为P，则，则P=,，=,，C（P，）=7，而流量已达，而流量已达到到7，故此流已是最大流。，故此流已是最大流。(,)min(,)i jPaC i jPP（1）(,)(,),(,)(,)i jC i ji jP P（2）(,)0,(,)(,)i ji jP P故故 ，已不能再增大，（注：这是线性规划的补松驰定理）。已不能再增大，（注：这是线性规划的补松驰定理）。(,)(,)P PC P P综上所述，有下面的有关网络流问题的定理。综上所述，有下面的有关网络流问题的定理。定理定理9.59.5 （Ford和和
27、Fulkerson最大流最小切割定理）最大流最小切割定理）任一由任一由s到到t的流，的流，其流量不大于任一切割的容量其流量不大于任一切割的容量C（P，），而最大流的流量则等于最小），而最大流的流量则等于最小切割的容量。进而切割的容量。进而 为最大流且（为最大流且（P，）为最小切割当且仅当：）为最小切割当且仅当：（1）有有（2）有有 。PP(,)(,)i jP P(,)(,)i jC i j(,)(,)i jP P(,)0i j增广路可以通过对顶点标号的方法来寻找。由于边容量均为整数，而每次增广路可以通过对顶点标号的方法来寻找。由于边容量均为整数，而每次经改进，流量至少增加一，故算法总能很快求得
28、最大流。经改进，流量至少增加一，故算法总能很快求得最大流。定理定理6.46.4 网络网络G上的流是最大流的充要条件为其增广网络上不存在由上的流是最大流的充要条件为其增广网络上不存在由s到到t 的通路。的通路。证明：证明：若增广网络上存在由若增广网络上存在由s到到t的通路的通路P，则对，则对P上的正规边（上的正规边（i,j）增加流）增加流量量a，对，对P的增广边（的增广边（j,i）对应）对应G的边（的边（i,j）减少流量）减少流量a，即可得到一个更，即可得到一个更大的可行流。若增广网络上不存在由大的可行流。若增广网络上不存在由s到到t的路，记增广图上的路，记增广图上s可达到的点组可达到的点组成的
29、集合为成的集合为P，则对切割（，则对切割（P,）必有：）必有：P2、最小费用最大流问题、最小费用最大流问题对于一个给定的网络，由发点对于一个给定的网络，由发点s到收点到收点t常常存在着多个具有相同流量的最常常存在着多个具有相同流量的最大流。如图大流。如图6.9所示，图中的（所示，图中的（a）、（）、（b）、（）、（c）均是流量为）均是流量为7的最大流，的最大流，边上的两个数字依次为容量和边上的实际流量。有时候，当流流经一条边边上的两个数字依次为容量和边上的实际流量。有时候，当流流经一条边时需支付一定的费用，我们不仅希望找出一个最大流，而且希望找出的最时需支付一定的费用，我们不仅希望找出一个最大
30、流，而且希望找出的最大流在具有相同流量的流中具有最小的总费用，这时问题可描述为：对有大流在具有相同流量的流中具有最小的总费用，这时问题可描述为：对有向图向图G=（V，A）的每条边（弧）（）的每条边（弧）（i,j）给定一个边容量）给定一个边容量C（i,j）及一个）及一个单位流量费用单位流量费用l(i,j)。希望求出由。希望求出由s到到t的最大流，使得总费用最少，即求最的最大流，使得总费用最少，即求最大流大流*，使，使*(,)()min(,)(,)i jALl i ji j最大流例如，在交通网络中，例如，在交通网络中，l(i,j)可以是可以是i,j之间的距离或运费。自然，在运送之间的距离或运费。自
31、然，在运送相同数量货物时，我们希望总距离或总运费最小。现在，我们将以最大相同数量货物时，我们希望总距离或总运费最小。现在，我们将以最大流问题的增广路算法为基础，导出求解最小费用最大流问题的算法。流问题的增广路算法为基础，导出求解最小费用最大流问题的算法。对于网络上的一个现行流对于网络上的一个现行流 ，作出其增广网络，作出其增广网络G()，对，对G中的正规边中的正规边赋值赋值l(i,j)，对，对G中的增广边中的增广边(i,j)则赋值则赋值l(i,j)。定义定义6.66.6 增广网络增广网络G上由上由s到到t的流量为零但边流量不全为零的流称为一个循环流。的流量为零但边流量不全为零的流称为一个循环流
32、。最小费用最大流问题可以变换成为一个线性规划问题，根据线性规划理最小费用最大流问题可以变换成为一个线性规划问题，根据线性规划理论可以证明下面的定理：论可以证明下面的定理：定理定理6.66.6 网络中的流网络中的流 是最小费用的，当且仅当其增广网络是最小费用的，当且仅当其增广网络G中不存在中不存在负费用的循环流（证明略）。负费用的循环流（证明略）。例例6.106.10 图图6.10（a）给出了有向图）给出了有向图G上的一个可行流，其中弧上的三个数上的一个可行流，其中弧上的三个数字分别为容量、单位流费用及实际流量。图字分别为容量、单位流费用及实际流量。图6.10（b）为相应的增广网络，）为相应的增
33、广网络，其中边（弧）上的两个数字分别为容量及单位流费用。求此网络的一个更其中边（弧）上的两个数字分别为容量及单位流费用。求此网络的一个更小费用流。小费用流。从图从图6.10（b）中可以找出一个负费用循环流）中可以找出一个负费用循环流s21s（其余边流量（其余边流量为为0），每单位流量的总费用为），每单位流量的总费用为5。调整此循环流上的流量，得到图。调整此循环流上的流量，得到图6.11（a）中的流。原先的流总费用为）中的流。原先的流总费用为17，调整后的总费用为，调整后的总费用为12，减少值，减少值为负费用循环流的总费用。为负费用循环流的总费用。图图6.11（a）中流的增广网络（）中流的增广网
34、络（b）中已不存在负费用循环流，它是一个最小）中已不存在负费用循环流，它是一个最小费用的流。费用的流。定理定理6.76.7 设设1是网络上流量为是网络上流量为的最小费用流，的最小费用流，2是其增广网络上由是其增广网络上由s到到t的的最小费用单位流增广路，则最小费用单位流增广路，则1+2是此网络流量为是此网络流量为+1的最小费用流。的最小费用流。证明：证明：设设1+2不是流量为不是流量为+1的最小费用流，由定理的最小费用流，由定理6，在，在 1+2的增广网的增广网络中必存在一负圈络中必存在一负圈C。记构造。记构造2的增广路为的增广路为P。由于。由于 1是最小费用流，是最小费用流，1的增广网络中不
35、存在负圈，故的增广网络中不存在负圈，故C中必有一边（中必有一边（i,j），其反向边（），其反向边（j,i）含）含在在P中（因为如若不然，中（因为如若不然，C不含不含P中任意边，则中任意边，则C将含在将含在1的增广网络中，与的增广网络中，与1为最小费用流的假设矛盾，见图为最小费用流的假设矛盾，见图9.12），但这又说明），但这又说明P（C（i,j）是）是S到到t的更小费用单位流增广路，与的更小费用单位流增广路，与P是最小费用单位流增广路的假设矛盾。是最小费用单位流增广路的假设矛盾。根据定理根据定理6.7及定理及定理6.6，求最大流的算法只需稍作，求最大流的算法只需稍作变动即可用来求解最小费用最大
36、流。算法可以用变动即可用来求解最小费用最大流。算法可以用归纳方式给出，当归纳方式给出，当=0时，可取时，可取=0，这显然是，这显然是=0的最小费用流。在以后逐次增大流量时，若增广的最小费用流。在以后逐次增大流量时，若增广网络中存在着多于一条增广路时，每次均选用其网络中存在着多于一条增广路时，每次均选用其中单位流费用最小的一条。这样，每次得到的均中单位流费用最小的一条。这样，每次得到的均为相同流量的流中费用最小的，而最后得到的即为相同流量的流中费用最小的，而最后得到的即为最小费用最大流。为最小费用最大流。网络流问题的算法在解决实际问题时常常被用到。它可用来求解运输问网络流问题的算法在解决实际问题
37、时常常被用到。它可用来求解运输问题、指派问题及赋权两分图匹配问题（等价于指派问题），也可用来寻题、指派问题及赋权两分图匹配问题（等价于指派问题），也可用来寻找网络的瓶颈找网络的瓶颈即最小切割（即最小切割（P，）确定的边。作为一个网络流问题）确定的边。作为一个网络流问题的应用实例，我们来求解例的应用实例，我们来求解例6.7中的婚姻姻问题：增加发点中的婚姻姻问题：增加发点s和收点和收点t，将，将原图的边改为有向边，所有边的容量为原图的边改为有向边，所有边的容量为1。找出最大财礼数。找出最大财礼数28，以此数，以此数减每边原有的财礼费，并用此差为各边的费用，得一最小费用最大流问减每边原有的财礼费，并
38、用此差为各边的费用，得一最小费用最大流问题（未注数字的边费用均为零），其网络图见图题（未注数字的边费用均为零），其网络图见图6.13。此问题在使用三。此问题在使用三次增广路后可求得最佳结果。次增广路后可求得最佳结果。P四、最短路径问题四、最短路径问题最短路径问题是又一个经常遇到的最短路径问题是又一个经常遇到的P问题，它在工艺流程的安排、管道或问题，它在工艺流程的安排、管道或网络的铺设、设备更新等实际生产中常被用到，是网络规划的基本问题之网络的铺设、设备更新等实际生产中常被用到，是网络规划的基本问题之一。顾名思义，最短路径求的是以下问题：给定一个网络，如何求出网络一。顾名思义，最短路径求的是以下
39、问题：给定一个网络，如何求出网络中指定两点间总距离（或总费用）最小的路径。中指定两点间总距离（或总费用）最小的路径。例例6.116.11 给定图给定图6.14中的网络，边上的数字为两顶点间的距离（或费用），中的网络，边上的数字为两顶点间的距离（或费用），求由求由A到到E的最短路径。的最短路径。求解最短路径问题的求解最短路径问题的Dijkstra算法体现了动态规划算法的基本思想。若点算法体现了动态规划算法的基本思想。若点P在在A到到E的最短路上，则的最短路上，则P到到E的最短路径必整个地包含在的最短路径必整个地包含在A到到E的最短路的最短路径上。因为，若不然，将由径上。因为，若不然，将由P到到E
40、的最短路径导出的最短路径导出A到到E的更短路径，从而的更短路径，从而导出矛盾。算法既可以通过对顶点逐次标号来实现，也可以通过矩阵运导出矛盾。算法既可以通过对顶点逐次标号来实现，也可以通过矩阵运算进行。在使用标号法时，既可以从起点开始标，也可以从终点开始标。算进行。在使用标号法时，既可以从起点开始标，也可以从终点开始标。（两者目的略有不同）对例（两者目的略有不同）对例6.11中的网络，如从起点中的网络，如从起点A开始标导，先在开始标导，先在A点标上点标上0。再找出离。再找出离A最近的点最近的点B3，标上，标上A到到B3的最短矩离的最短矩离1并记录下并记录下A点点（表明由（表明由A而来）。一般，在
41、标新顶点时，先找出离已标号顶点最近的顶而来）。一般，在标新顶点时，先找出离已标号顶点最近的顶点。比较各已标号顶点（与拟标号顶点有边相连）的标号与它到拟标号点。比较各已标号顶点（与拟标号顶点有边相连）的标号与它到拟标号顶点距离之和，找出各种中最小者作为新顶点的标号，并记录下其前的顶点距离之和，找出各种中最小者作为新顶点的标号，并记录下其前的已标号顶点。直到拟到达的终点已标号为止。例如，图已标号顶点。直到拟到达的终点已标号为止。例如，图6.15指出，指出，A到到E的最短路径为的最短路径为AB2C1D1E，最短距离为，最短距离为19。容易看出，算法是多项式时间的。在标每一顶点时，最多作了容易看出，算
42、法是多项式时间的。在标每一顶点时，最多作了|V|次运算。次运算。算法进行中，事实上在构造一棵由已标号顶点及它们与其前行点间的边算法进行中，事实上在构造一棵由已标号顶点及它们与其前行点间的边组成的树。每一顶点均不可能重复标号，故总计算量的一个上界为组成的树。每一顶点均不可能重复标号，故总计算量的一个上界为O（|V|2）。）。按一般习惯，动态规划算法常按逆顺序进行。图按一般习惯，动态规划算法常按逆顺序进行。图9.16给出了按向前标号的给出了按向前标号的结果，最短路径已用双线划出。结果，最短路径已用双线划出。从图从图6.15中可看出中可看出A到各点的距离及最短路径，而从图到各点的距离及最短路径，而从
43、图9.16中则可看出由中则可看出由各点到各点到E点的距离及最短路径，这是两者的区别。点的距离及最短路径，这是两者的区别。读者不难给出一般问题的计算步骤，也不难推广得到能求出任意两点间最读者不难给出一般问题的计算步骤，也不难推广得到能求出任意两点间最短路径的算法。短路径的算法。作为最短路径问题的一个应用实例，我们来研究下面的设备更新问题：作为最短路径问题的一个应用实例，我们来研究下面的设备更新问题：例例6.126.12 某单位使用一种设备。该设备在某单位使用一种设备。该设备在5年内的预期价格见表年内的预期价格见表9.1，使用，使用不同年数的设备的年维修费用见表不同年数的设备的年维修费用见表6.2
44、。现准备制订一个五年内的设备更。现准备制订一个五年内的设备更新计划，使五年内支付的设备购置费用及总维修费用最少。新计划，使五年内支付的设备购置费用及总维修费用最少。这显然是一个十分有意义的实际问题，即使作为个人，也会经常遇到更这显然是一个十分有意义的实际问题，即使作为个人，也会经常遇到更换交通工具、家用电器等设备更新问题的实例。当然，作为一般情况，换交通工具、家用电器等设备更新问题的实例。当然，作为一般情况，还可能要考虑残值，如购买了新车，旧车可以折价处理，回收资金与已还可能要考虑残值，如购买了新车，旧车可以折价处理，回收资金与已使用年数有关。使用年数有关。解：解：作有向图图作有向图图6.17
45、，图中点，图中点i表示第表示第i年初（或第年初（或第i1）年末），弧（）年末），弧（i,j）上的数字表示第上的数字表示第i年初购买设备到第年初购买设备到第j年初更换，在该段时间内的总费用。年初更换，在该段时间内的总费用。例如，弧（例如，弧（，）上的数）上的数68表示第一年初购买设备到表示第一年初购买设备到5年后的第六年年后的第六年初更换，需支付购设备费初更换，需支付购设备费10万元及各年维修费万元及各年维修费 58 万元，共计万元，共计68万元。万元。问题化为求由顶点问题化为求由顶点到顶点到顶点的最短路。的最短路。容易看出，作出容易看出，作出n年设备更新问题的有向图将问题化为最短路径问题大约年
46、设备更新问题的有向图将问题化为最短路径问题大约需要需要O(n2)计算量，其后要求求解的最短路径问题的计算量也是计算量，其后要求求解的最短路径问题的计算量也是O(n2)，故，故设备更新问题可在设备更新问题可在O(n2)时间内求解。时间内求解。表表6.1表表6.2第i年12345价格（万年）1010111213已使用年数01234（万年）48111520五、欧拉圈与最短邮路问题五、欧拉圈与最短邮路问题欧拉圈问题起源于著名的七桥问题。给定一个无向图欧拉圈问题起源于著名的七桥问题。给定一个无向图G=（V，E），问能），问能否由一个顶点出发，经且仅经过每条边一次并返回原出发顶点。如果能够，否由一个顶点出
47、发，经且仅经过每条边一次并返回原出发顶点。如果能够，则每一个这样的圈被称为图则每一个这样的圈被称为图G的欧拉圈，而图的欧拉圈，而图G则被称为是一个欧拉图。则被称为是一个欧拉图。显然，图显然，图G为欧拉图的充要条件是它可以被一笔画出且首尾相连（当首尾为欧拉图的充要条件是它可以被一笔画出且首尾相连（当首尾不能相连时则被称为欧拉路）。由此，立即可得出下面的定理：不能相连时则被称为欧拉路）。由此，立即可得出下面的定理：定理定理6.86.8 G为为 欧拉图的充要条件是：欧拉图的充要条件是：G是连通的且是连通的且G的每一个顶点都与偶的每一个顶点都与偶数条件相关联。数条件相关联。把关联偶数条边的顶点称为偶顶
48、点，把关联奇数条边的顶点称为奇顶点，把关联偶数条边的顶点称为偶顶点，把关联奇数条边的顶点称为奇顶点，则容易看出奇顶点的个数必为偶数个（因为每一笔画都产生一个起点与则容易看出奇顶点的个数必为偶数个（因为每一笔画都产生一个起点与一个终点），又易得出一个终点），又易得出定理定理6.96.9 G为欧拉路的充要条件为：为欧拉路的充要条件为：G是连通的且奇顶点的个数为是连通的且奇顶点的个数为2。综合定理综合定理6.8和定理和定理6.9可知，可知，G可一笔画出的充要条件为可一笔画出的充要条件为G是连通的且奇顶是连通的且奇顶点的个数为点的个数为0或或2，当奇顶点个数为零时，尚可设法使起点和终点相重。下，当奇顶
49、点个数为零时，尚可设法使起点和终点相重。下面的图面的图6.18（a）为欧拉圈，而图）为欧拉圈，而图6.18（b）则为欧拉路，后者虽可一笔画）则为欧拉路，后者虽可一笔画出，但必须以一个奇顶点为起点，以另一个奇顶为终点。出，但必须以一个奇顶点为起点，以另一个奇顶为终点。图的连通性可以十分容易地用标号算法加以检验。而图的奇顶点数又可通图的连通性可以十分容易地用标号算法加以检验。而图的奇顶点数又可通过对其顶点一一检测而求得。容易看出总计算量是多顶式时间的，故欧拉过对其顶点一一检测而求得。容易看出总计算量是多顶式时间的，故欧拉圈问题和欧拉路问题均是十分简单的圈问题和欧拉路问题均是十分简单的P问题，从而，
50、等价地，一笔画问题问题，从而，等价地，一笔画问题也可十分容易地求解：若图也可十分容易地求解：若图G是欧拉图，则从任一顶点出发均可将它一笔是欧拉图，则从任一顶点出发均可将它一笔画出；若图画出；若图G是欧拉路，则由一奇顶点出发，一一经偶顶点地走过各条边，是欧拉路，则由一奇顶点出发，一一经偶顶点地走过各条边，最后到达另一奇顶点，即可将最后到达另一奇顶点，即可将G一笔画出；否则一笔画出；否则G不能一笔画出，（当然，不能一笔画出，（当然，如何走法仍需规划一下）。如何走法仍需规划一下）。与欧拉图有较大联系的另一有名的与欧拉图有较大联系的另一有名的P问题是无向图上的中国邮路问题。给问题是无向图上的中国邮路问
