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