第10章第12节.ppt

《第10章第12节.ppt》由会员分享，可在线阅读，更多相关《第10章第12节.ppt（71页珍藏版）》请在三一办公上搜索。

1、1,第1节图的基本概念第2节 树,运筹学（第三版）运筹学教材编写 组第10章 图与网络优化清华大学出版社,2,图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。,3,1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间

2、有七座桥相互连接，,4,哥尼斯堡七空桥,一笔画问题,欧拉（1736）,5,第1节图的基本概念,例1是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。,6,例 2 表示五个球队比赛请况。用五个点v1,v2,v3,v4,v5分别表示五个球队，点与点之间的连线表示对应的两个球队已经比赛过。,7,例 3 用八个点v1,v2,v3,v4,v5,v6,v7,v8 表示八种化学药品，其间有连线的表示该两种化学药品不能存放在一个仓库里，问至少要设几个仓库来存放这些药品？由图可见，至少要设四个仓库。,8,

3、图是反映对象之间关系的一种工具，其中点表示对象，点间连线表示对象之间的关系。一般而言，图中点的位置，点间连线的长短曲直对于反映对象及其之间的关系并不重要。,v1,v2,v3,v4,v5,v1,v2,v3,v4,v5,在前面两例中，对象之间的关系是“对称的”，这种对称的关系可用两点之间的连线表示。但有些关系不是对称的，不可用两点之间的连线表示，却可以用两点之间的一条箭线来表示。如两个球队进行过比赛，这种关系是对称的；但谁胜谁负就不是对称的。若甲胜乙负，那么可以用从甲到乙划一条箭线来表示。,甲,乙,。,9,甲 v1,乙 v2,v3 丙,v4 丁,戊 v5,图论中的图，是指点以及点与点之间的连线所组

4、成的集合。如果联线没有方向（不是箭线）就叫做边，如果联线有方向（即箭线）就叫做弧。如果一个图G(Graph)是由点与边组成，就叫无向图（也简称为图）。记为 G=（V，E），其中V表示点的集合，E 表示边(Edge)的集合。如果一个图 D(Diagram)是点与弧的集合就叫有向图，记为：D=（V，A），其中V表示点的集合，A表示弧（Arc)的集合。,连接 vi与vj 的边记为 vi，vj 或 vj,vi。由 vi指向vj 的弧记为（vi，vj）。,10,V1,V2,V3,V4,253 页 图 107,例如右图（无向图，见 253页）可表为：,e1,e7,e6,e5,e4,e3,e2,G=V,E,

5、其中：V=，E=e1，e2，e3，e4，e5，e6，e7,V1,V2,V3,V 4,V1,V2,V3,V4,a1,a6,a5,a4,a3,a2,其中又：e1=V1,V2,e2=V1,V2e3=V3,V2,e4=V4,V3,e5=V1,V4,e6=V1,V3,e7=V4,V4,又例如右图（为一有向图）可表为：,D=V,A,其中：V=，A=a1，a2，a3，a4，a5，a6,V1,V2,V3,V 4,其中又：a1=(V1,V2),a2=(V1,V2),a3=(V2,V3),a4=(V4,V3),a5=(V1,V4),a6=(V1,V3),图的实例,11,图G(或图D)的点数记为p（G）(或P（D）

6、)，边（或弧）的条数记为q(G)(或q(D),在不会引起误会时，也分别简记为p,q.下面介绍一些基本名词和记号，先考虑无向图 G=（V，E）：若 e=u,v,则称 u,v 是 e 的端点,也称 u,v 是相邻的。称 e 是点 u,v 的关联边。若边的两个端点相同，则该边成为环（如图107中的 e7）；如两点之间有多条边，则称这些边为多重边。（如图107中的e1，e2）。一个无环、无多重边的图称简单图，无环但有多重边的图称多重图。以 v 为端点的边的条数称为点 v 的次数，记为 d(v)，如在右图中：d(v1)=4,d(v2)=3,d(v 4)=4(环 e7在计算d(v 4)时算作两次)。称次数

7、为一的点为悬挂点，悬挂点的关联边为悬挂边，次数为 0 的点称为孤立点（点击）。次数为奇数的点称为奇点，次数为偶数的点称为偶点.,V1,V2,V3,V4,253 页 图 107,e1,e7,e6,e5,e4,e3,e2,V5,V6,次与简单图,12,端点的度 d(v)：点 v 作为边端点的个数；奇点：d(v)=奇数；偶点：d(v)=偶数；悬挂点：d(v)=1；悬挂边：与悬挂点连接的边；孤立点：d(v)=0；空图：E=，无边图,13,定理1 所有顶点次数之和等于所有边数的2倍。定理2 在任一图中，奇点的个数必为偶数。,基本定理,14,链：由两两相邻的点及其相关联的边构成的点边序列;如:v0,e1,

8、v1,e2,v2，e3,v3,vn-1,en,vn;v0，vn分别为链的起点和终点；初等链：链中所含的点均不相同 简单链：链中所含的边均不相同；,链,15,圈,第一个点和最后一个点相同的链叫圈。中间点皆不相同的圈叫初等圈。所有边皆不相同的圈叫简单圈。,16,连通图,给定图G，若其中任何两点之间至少有一条链，则称G为连通图，否则称为不连通图；若G 不是连通图，则可将它分为若干个连通的分图。,17,v8,v9,e10,在图10-9中，链（v1,v2,v3,v4,v5,v3,v6,v7)是简单链，非初等链。链（v1,v2,v3,v6,v7)是初等链。（v1,v2,v3,v4,v1)是初等圈。（v4,

9、v1,v2,v3,v5,v7,v6,v3,v4)是简单圈，非初等圈（中间有相同点）。,18,V1,V3,V4,V5,V2,图 G,图 G V3,图 G的一个支撑子图,V1,V4,V5,V2,V1,V3,V4,V5,V2,给定一个图G=（V，E）如果图G=（V，E），满足条件：V=V，EE，则称 G是 G 的一个支撑子图。即去掉G的一些边（边的端点并不随边一起去掉）后所得的图称G的支撑子图。设 vV(G),用 Vv表示从 G中去掉点v及其关联边后所的到的图。,19,V1,V3,V4,V5,V2,图 G,图 G的支撑子图,基本概念4,20,以下讨论有向图。设有一个有向图D=（V，A），去掉D中所有

10、弧上的箭头，得一无向图，叫D 的基础图，记为G（D）。给定弧a=(u,v),称 u 为 a 的始点，称 v 为 a 的终点。有向图D中的一个点弧交错序列，如果在其基础图G（D）中对应一条链，则称D的这一点弧交错序列为图D的一条链。若D的链上每条弧的左右两点分别是该弧的始点和终点，就称该链为一条路。若路的第一个点与最后一个点相同，就称之为回路。初等路是中间点皆不相同的路。,如点弧交错序列：V1,a2,V3,a8,V5,a10,V6,a11,V7 是链不是路。而点弧交错序列：V1,a1,V2,a5,V4,a7,V6,a11,V7 是链也是路。,基本概念5,21,2.1树及其性质,在各种各样的图中，

11、有一类图是十分简单又非常具有应用价值的图，这就是树。,22,已知有五个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话（允许通过其它城市），并且电话线的根数最少。不含圈的连通图,23,定义1 一个无圈的连通图叫做树。下面介绍树的一些重要性质：定理3 设图G=（V，E）是一个树P(G)2，那么图G中至少有两个悬挂点。定理4 图G=（V，E）是一个树的充要条件是G不含圈，并且有且仅有P-1条边。定理5 图G=（V，E）是一个树的充要条件是G是连通图，并且有且仅有P-1条边。定理8.6 图G是一个树的充分必要条件是任意两个顶点之间有且仅有一条链。,24,从以上定理，不难得出以下结论：（1）

12、从一个树中任意去掉一条边，那么剩下的图不是连通图，亦即，在点集合相同的图中，树是含边数最少的连通图。（2）在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。,25,2.2图的支撑树,定义2 设图T=(V,E)是图G=(V,E)的支撑子图,如果图T=(V,E)是一个树,那么称T是G的一个支撑树。,v6,v5,v2,v3,v4,v1,图1014,a,v6,v2,v4,v1,b,v3,v5,26,若T=（V，E）是图 G=（V，E）的支撑树，则T的边数：q(T)=p(T)-1=p(G)-1，G 中不属于 T 的边数是 q(G)-（p(G)-1）=q(G)-p(G)+1。,27,定理 7 图G有

13、支撑树的充分必要条件是 G 连通。,必要性显然。充分性 设G连通。若G是树，则G是它自己的支撑树。若G非树，则 G含圈，从该圈中任意去掉一边，得G的支撑子图G，若G为树，则是G的支撑树；若 G 非树，则G 含圈，又去掉圈中任意一条边，如此反复进行，因边数有限，最后必得G的一个支撑树。证毕！,28,上定理的证明过程实际上给出了寻找一个图的支撑树的一个方法，名“破圈法”，就是任取图中一个圈，去掉圈中一条边，如此反复进行直到获得一个支撑树为止。,29,例6:用破圈法求出图的一个支撑树,取一个圈(v1,v2,v3,v1)，在一个圈中去 掉边e3。在剩下的图中，再取一个圈（v1,v2,v4,v3,v1）

14、，去掉边e4。再从圈（v3,v4 v5,v3）中去掉边e6。再从圈(v1,v2,v5,v4,v3,v1）中去掉边e8，这样，剩下的图不含圈，于是得到一个支撑树。,v3,30,例6:用避圈法求出图的一个支撑树,31,2.3 最小支撑树,定义 3 给图G=（V，E）的每一条边Vi，Vj赋予一个实数Wij,则称G 为 赋权图。而Wij称为边 Vi，Vj 的权。定义 4 如果T=（V，E）是赋权图G 的一个支撑树，称T的所有边的权数之和为T的权，记为w(T).如果图G的支撑树T*的权w(T*)是G的所有支撑树中权为最小的支撑树，则称T*为G的最小支撑树，简称最小树。,32,1、“避圈法”生长法 Kru

15、skal,33,2、“破圈法”,(b),34,第3节最短路径问题,最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。也可以用于解决其它的最优化问题。,35,例10 如图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从v1出发，经过这个交通网到达v8，要寻求是总路程最短的线路。,3.1 引例,36,一般意义下的最短路问题：设一个赋权有向图D=（V，A），对于每一个弧a=（vi,vj），相应地有一个权wij。vs,vt是D中的两个顶点，P是D中从vs到vt的任

16、意一条路，定义路的权是P 中所有弧的权的和，记作w(P)。最短路问题就是要在所有从vs到vt的路P 中，寻找一个权最小的路P0，使w(P0)=minw(p)。P0叫做从vs到vs的最短路。P0的权w(P0)叫做从vs到vt的距离，记作d（vs，vt）。由于D是有向图，很明显d（vs，vt）与d（vt，vs）一般不相等。,37,3.2最短路算法(Dijkstra 1959),下面介绍在一个赋权有向图中寻求最短路的方法Dijkstra算法，它是在1959年提出来的。目前公认，在所有的权wij 0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj

17、的最短路。,38,Dijkstra算法的基本思想,从vs出发，逐步向外寻找最短路。在运算过程中，与每个点对应，记录一个数(称为这个点的标号)。它或者表示从vs到该点的最短路权（叫做P 标号,即永久标号），或者表示从vs到该点最短路权的上界（叫做T 标号,即临时标表号）。算法的每一步是去修改T 标号，把某一个具有T 标号的点改变为具有P 标号的点，使图D 中具有P 标号的顶点多一个。这样，至多经过p-1步，就可求出从vs到各点vj的最短路。,39,以例10为例说明这个基本思想。VS=V1。因为Wij 0，d（v1,v1）=0。这时，v1是具有P标号的点。现在看从v1出发的三条弧（v1,v2），（

18、v1,v3）和（v1,v4）。沿（v1,v2）到达v2，则d（v1,v1）+w12=6沿（v1,v3）到达v3，则d（v1,v1）+w13=3沿（v1,v4）到达v4，则d（v1,v1）+w14=1因此，从v1出发到达v4的最短路必是（v1,v4），d（v1,v4）=1。因为从v1到达v4的任一条路P，假如不是（v1,v4），则必先沿（v1,v2）到达v2，或者沿（v1,v3）到达v3，而这时的路程已是6或者3单位。,40,看从v1出发的三条弧（v1,v2），（v1,v3）和（v1,v4），mind(v1,v1)+w12,d(v1,v1)+w13,d(v1,v1)+w14=d（v1,v4）=1

19、。,由于所有的权wij 0，因此，不论他如何再从v2或者v3到达v4，所经过的总路程都不会比1少，于是就有d（v1,v4）=1。这样就使V4变成具有P标号的点。,41,现在看从v1和v4指向其余点的弧。如上所述，从V1出发，分别沿（v1,v2），（v1,v3）到达v2，v3，经过的路程是6或者3单位。从v4出发沿（v4,v6）到达v6，经过的路程是d（v1,v4）+w46=1+10=11单位。而mind（v1,v1）+w12，d（v1,v1）+w13，d（v1,v4）+w46=d（v1,v1）+w13=3单位。根据同样的理由，可以断定，从V1到达V3的最短路是（v1,v3），d（v1,v3）=

20、3。这样，又使点v3变为具有P 标号的点，不断重复以上过程，就可以求出从vs到达任一点vj的最短路。,42,在下述的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。,43,Dijkstra算法的步骤,开始（i=0）令S0=vs，P（vs）=0，(vs)=0，对每一个v vs

21、，令T（v）=+，(v)=M，令k=s；,44,（1）如果Si=V，则算法结束，对每一个vSi，d（vs,v）=P（v）。否则转入（2）；（2）考察每一个使（vk,vj）A，且vj不属于Si的点vj，如果T(vj)P(vk)+wkj，则把T(vj)改变为P(vk)+wkj，把(vj)改变为k，否则转入（3）；(3）令(vji)=minT(vj)vjSi，,45,如果T(vji)+，则把vji的T 标号改变为P 标号P(vji)=T(vji)，令Si+1=Sivji，k=ji，把i换成i+1，转入（1）；否则结束。这时，对每一个vSi，d(vs,v)=P(v)。对每一个v不属于Si，d（vs,v

22、）=T（v）。,46,最短路问题 261 页 例 10（权数非负的有向网络最短路问题）,v1,v2,v3,v4,v5,v6,v7,v8,v9,6,1,3,6,2,2,1,4,4,2,6,2,3,3,10,10,0,0,，,，,，,，,，,，,，,，,1，V1,3，V1,6，1,11，4,5，V3,6，V2,10，V5,9，V5,12，V5,黄筐表示P标号，即永久标号；蓝筐表示T标号，即临时表号。,算法：1、始点给予P标号，其他点给予T标号；2、修改尽可能多T标号；3、检查所有T 标号，将离始点最近的T 标号改为P标号。4、反复进行 2、3 两步，直到无法进行为止。,P标号永久标号,T标号临时标

23、号,本点号：1 2 3 4 5 6 7 8 9紧前点：1 3 1 1 2 5 5 5 路 长：0 5 3 1 6 10 9 12,47,最短路问题 261 页 例 10,v1,v2,v3,v4,v5,v6,v7,v8,v9,6,1,3,6,2,2,1,4,4,2,6,2,3,3,10,10,0,0,1，V1,3，V1,5，V3,6，V2,9，V5,10，V5,12，V5,前页的算法也可简化如下：,本点号：1 2 3 4 5 6 7 8 9紧前点：1 3 1 1 2 5 5 5 路 长：0 5 3 1 6 10 9 12,261页例10,48,v1,v2,v3,v4,v5,v6,v7,v8,v9

24、,6,1,3,6,2,2,1,4,4,2,6,2,3,3,10,0,0,1，V1,3，V1,5，V3,6，V2,8，V5,10，V5,9，V5,11，V9,本点号：1 2 3 4 5 6 7 8 9紧前点：1 3 1 1 2 5 5 9 5路 长：0 5 3 1 6 10 9 11 8,264 页 例 11权数非负的无向网络最短路问题,非负权无向网,49,第4节网络最大流问题,50,4.1基本概念和基本定理,1、网络和流定义6给一个有向图 D=（V，A）,在V中指定一点,叫做发点,记为vs，指定另一点v t,叫收点，其余的点叫中间点；又对每一弧(v i,v j)A赋予一个容量c(vi,vj)=

25、0,简记 c i j,表示该弧的最大通过能力。常称D为网络，记为D=（V，A，C）。所谓网络上的流，是指定义在每一条弧（v i，v j）A上的一个函数集:f=f（v i，v j）=f i j,并称 f i j 为 弧（v i，v j）上的 流量。,51,2、可行流与最大流,定义 7 满足下述条件的流 f 称为可行流：(1)容量限制条件对每一条弧(v i，v j),流量不得超过容量 0 f i j c i j，(2)平衡条件,注意：零流，即所有f i j=0,（v i，v j）A，的流，是可行流！,52,网络最大流问题,就是在网络上求一个可行流f i j使流量v（f）达到最大。,53,3、增广链

26、,在D=（V，A，C）上给定一个可行流f i j饱和弧：f i j=c i j非饱和弧：f i j0,54,网络D=（V，A，C）上取出一条从发点到收点的链u：前向弧,方向与链一致，全体记为u后向弧,方向与链相反，全体记为u定义8，增广链给定一条从发点到收点的链，若链上所有前向弧皆非饱和，而所有 后向弧皆非零流弧，则称该链为增广链,55,容量网络G=（V1，E，C），vs为始点，vt为终点。如果把V分成两个非空集合 使，则所有始点属于V1，而终点属于 的弧的集合，称为由V1决定的截集,记作。截集 中所有弧的容量之和，称为这个截集的容量，记为。,4、截集与截量,56,vs,vt,v1,v3,v2

27、,v4,(3,3),(4,2),(5,1),(2,2),(1,1),(1,1),(5,3),(3,0),(3,1),(c ij,fij),截集(割集)为：（Vs，V2）,(V1,V3)。割容量为：3+2=5,截集(割集)为：（V2，V4）,(V1,V3)。割容量为：4+2=6,截集(割集)为：（V4，Vt）,(V1,V3)。割容量为：5+2=7,网络最大流的流量=容量最小的割容量,57,定理 8 可行流 f*是最大流当且仅当不存在关于 f*的增广链。,58,4.2寻求最大流的标号法（Ford,Fulkerson),1、标号过程2、调整过程,59,272 页 例14,vs,vt,v1,v3,v2

28、,v4,(3,3),(4,3),(5,1),(2,2),(1,1),(1,1),(5,3),(3,0),(3,1),(c ij,fij),0,+,vs,4,v1,1,v2,1,v4,1,0,+,vs,3,60,第5节 最小费用最大流,寻找最小费用的最大流方案（274276页）,61,设D=（V，A，C）是一个容量网络，再给出每条弧（v i，v j）上的单位运价 bi j,并以（c i j,，b ij）表示弧（v i，v j）上的容量与单位运价。假定D有增广链，所谓增广链的费用是指沿增广链增加一单位物资所增加的费用：bi j-bi j，寻找关于可行流f 的最小费用链的方法如下：,+,-,对于 f

29、，定义一个赋权有向图如下：其顶点集与D的顶点集相同，而D的每条弧（v i，v j）换为两条方向相反的弧（v i，v j）与（v j，v i）,其权数分别定义为：bi j,若 f i j 0 w j i=+,若 f i j=0。.注意,长度为+的弧可以抹去.,62,4,vs,vt,v1,v2,v3,4,1,2,3,1,6,2,vs,vt,v1,v2,v3,按最短路根据弧的容量调整运量得流量图下图.,W(f(0),0,0,0,0,vs,vt,v1,v2,v3,(a),(b),f(1),v(f(1)=5,1,-2,3,1,6,2,vs,vt,v1,v2,v3,-1,-1,W(f(1),(c),作相应

30、赋权有向图并求出最短路,bi j,若 f i j c i j，,+,若 f i j=c i j.,-b j i,若 f i j 0,+,若 f i j=0,w i j=,w j i=,以0流 f(0)=0为初始流构造赋权有向图并算得最短路如右,0,0,0,5,5,5,276页各图的解释：,(4,10),(1,8),(2,5),(3,10),(1,7),(6,2),(2,4),(bij,cij),（运价，容量）,276页解释,63,1,4,0,5,5,0,5,0,0,vs,vt,v1,v2,v3,(b),f(1),v(f(1)=5,1,3,1,6,2,vs,vt,v1,v2,v3,-1,W(f(

31、1),(c),作相应赋权有向图并求出最短路,0,5,5,0,5,0,0,vs,vt,v1,vs,v2,v3,(d),4,3,-1,6,2,vs,vt,v1,v2,v3,-1,W(f(2),(e),-4,沿最短路调整,得左下图,作相应赋权有向图并求出最短路,vs,vt,v1,v2,v3,bi j,若 f i j c i j，,+,若 f i j=c i j.,-b j i,若 f i j 0,+,若 f i j=0,w i j=,w j i=,题目,-1,2,7,(4,10),(1,8),(2,5),(3,10),(1,7),(6,2),(2,4),(bij,cij),-2,-2,同上1,64,

32、1,2,5,5,0,7,0,0,vs,vt,v1,vs,v2,v3,(d),4,3,-1,6,2,vs,vt,v1,v2,v3,-1,W(f(2),(e),-4,作相应赋权有向图并求出最短路,4,-2,3,-1,6,2,vs,vt,v2,v3,-1,W(f(3),(g),-4,-2,-3,2,5,5,0,7,0,0,vs,vt,v1,v2,v3,(f),f(3),v(f(3)=10,作相应赋权有向图并求出最短路,沿最短路调整流量,bi j,若 f i j c i j，,+,若 f i j=c i j.,-b j i,若 f i j 0,+,若 f i j=0,w i j=,w j i=,vs,

33、vt,v1,v2,v3,题目,8,3,3,p.276,(4,10),(1,8),(2,5),(3,10),(1,7),(6,2),(2,4),(bij,cij),-2,同上2,65,2,8,5,3,7,0,3,vt,v1,vs,v2,v3,(h),f(4),v(f(4)=11,4,-2,3,-1,6,2,vs,vt,v2,v3,-1,W(f(3),(g),-4,-2,-3,2,8,5,3,7,0,3,vs,vt,v1,v2,v3,(f),f(3),v(f(3)=10,4,-2,3,-1,6,vs,vt,v2,v3,-1,W(f(4),(i),-4,-2,-3,2,从发点到收点的路长为无限大,故

34、左边的网络流是最小费用最大流.完!,vs,vt,v1,v2,v3,bi j,若 f i j c i j，,+,若 f i j=c i j.,-b j i,若 f i j 0,+,若 f i j=0,w i j=,w j i=,沿最短路调整流量,作相应赋权有向图并求出最短路,作相应赋权有向图并求出最短路,题目,3,4,4,4,v1,v1,p.276,(4,10),(1,8),(2,5),(3,10),(1,7),(6,2),(2,4),(bij,cij),同上,66,同上，终,5,6,4,2,7,2,4,vs,vt,v1,v2,v3,2,8,5,3,7,0,3,vt,v1,vs,v2,v3,3,

35、4,4,4,4,-2,3,-1,6,vs,v2,v3,-1,W(f(4),(i),-4,-2,2,vt,v1,(4,10),(1,8),(2,5),(3,10),(1,7),(6,2),(2,4),vs,vt,v1,v2,v3,(bij,cij),题目,p.276,这是刚才获得的一个最小费用最大流方案,V（f）=11,cost=55,以下也是一个最大流方案,V（f）=11;但费用较大,cost=67。,67,例 十名研究生参加六门课程的考试，个人选修课程不同，每人参加考试的课程（打*号者）见下表：规定三天内靠完，每天上、下午各考一门。考 生希望每天最多考一门，又课程A必须在第一天上午考，F安排

36、在最后一门考，B只能安排在上午考，试列出一张满足各方要求的考试日程表。,课程,研究生,A B C D E F,1,*,*,*,2,*,*,3,*,*,4,*,*,*,5,*,*,*,6,*,*,7,*,*,*,8,*,*,9,*,*,*,10,*,*,*,68,解：每门课程用一个点表示，同一个人参加的课程用边联起来，得图如下：课程A、E可排在同一天，B、C可排在同一天，D、F也可排在同一天。再根根据其他要求可得满足各方面要求的考试日程表如下：,69,如下图所示，某人从住处到工作地上班，图中各弧旁的数字为该弧的长度（单位：公里）。试问该人应选择哪条线路，使从家出发到工作地的路程最短。用Dijkstra标号法求解上述问题。（要求写出主要过程）,70,最大流问题如下图所示，图中弧旁数字为容量，求下图网络中到的最大流量,71,下面左图表示一个网络，弧旁的数字为（bij,cij），右图为一个可行方案，试在右图所示可行流的基础上按最小费用最大流的求解方法进行下一步变换（只要求作一步计算，不需完整计算；要求作出赋权有向图、找出最小费用增广链和调整后的网络图）。,