《第10章第12节》由会员分享，可在线阅读，更多相关《第10章第12节（71页珍藏版）》请在金锄头文库上搜索。
1、第1节图的基本概念第2节 树运筹学（第三版）运筹学教材编写 组第10章 图与网络优化清华大学出版社1图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。21736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连
2、接，3BDACABCD哥尼斯堡七空桥哥尼斯堡七空桥一笔画问题一笔画问题欧拉（1736）4第1节图的基本概念例1是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。太原重庆武汉南京徐州连云港上海郑州石家庄塘沽青岛济南天津北京5例例 2 表示五个球队比赛请况。用五个点表示五个球队比赛请况。用五个点v1,v2,v3,v4,v5分别表示五个球队，点与分别表示五个球队，点与点之间的连线表示对应的两个球队已经点之间的连线表示对应的两个球队已经比赛过。比赛过。甲甲 v1乙乙 v2 v3 丙丙 v4 丁丁
3、戊戊 v56例例 3 用八个点用八个点v1,v2,v3,v4,v5,v6,v7,v8 表示八种表示八种化学药品，其间有连线的表示该两种化学药品化学药品，其间有连线的表示该两种化学药品不能存放在一个仓库里，问至少要设几个仓库不能存放在一个仓库里，问至少要设几个仓库来存放这些药品？由图可见，至少要设四个仓来存放这些药品？由图可见，至少要设四个仓库。库。v1v8v2v3v4v5v6v77图是反映对象之间关系的一种工具，其中点表示对象，点间连图是反映对象之间关系的一种工具，其中点表示对象，点间连线表示对象之间的关系。线表示对象之间的关系。 一般而言，图中点的位置，点间连线的长短曲直对于反映对象一般而言
4、，图中点的位置，点间连线的长短曲直对于反映对象及其之间的关系并不重要。及其之间的关系并不重要。v1v2 v3 v4 v5v1v2 v3 v4 v5 在前面两例中，对象之间的关系在前面两例中，对象之间的关系是是“对称对称的的”，这种对称的关，这种对称的关系可用两点之间的连线表示。但有些关系不是对称的，不可用两系可用两点之间的连线表示。但有些关系不是对称的，不可用两点之间的连线表示，却可以用两点之间的一条箭线来表示。如两点之间的连线表示，却可以用两点之间的一条箭线来表示。如两个球队进行过比赛，这种关系是对称的；但谁胜谁负就不是对称个球队进行过比赛，这种关系是对称的；但谁胜谁负就不是对称的。若甲胜乙
5、负，那么可以用从甲到乙划一条箭线来表示。的。若甲胜乙负，那么可以用从甲到乙划一条箭线来表示。甲甲乙乙。8甲甲 v1乙乙 v2 v3 丙丙 v4 丁丁戊戊 v5 图论中的图论中的图图，是指，是指点点以及点与点之间的以及点与点之间的连线连线所组成的集合。所组成的集合。如果如果联线没有方向（不是箭线）就叫做联线没有方向（不是箭线）就叫做边边，如果，如果联线有方向联线有方向（即箭线）就叫做（即箭线）就叫做弧。弧。 如果一个图如果一个图 G (Graph)是由点与边组成，就叫是由点与边组成，就叫无向图无向图（也简称（也简称为图）。记为为图）。记为 G=（V，E），），其中其中V表示点的集合，表示点的集合
6、，E 表示边表示边(Edge)的集合。的集合。如果一个图如果一个图 D(Diagram)是点与弧是点与弧的集合就叫的集合就叫有向图有向图，记为：记为：D=（V，A），），其中其中V表示点的集合，表示点的集合，A表示弧表示弧（Arc)的集合。的集合。 连接连接 vi与与vj 的边记为的边记为 vi ，vj 或或 vj , vi 。 由由 vi指向指向vj 的弧的弧记为记为 （vi ，vj ）。9V1V2V3V4253 页页 图图 107例如右图（无向图，见例如右图（无向图，见 253页）可表为：页）可表为：e1e7e6e5e4e3e2G=V,E,其中：其中：V= ， ， ， E=e1 ， e2，
7、 e3 ， e4 ， e5 ， e6 ， e7 V1V2 V3V 4V1V2V3V4a1a6a5a4a3a2其中其中又又： 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 V1V2 V3V 4其中其中又又： a1=(V1 ,V2), a2=(V1 ,V2),a3=(V2 ,V3), a4=(V4 ,V3), a5=(V1 ,V4), a
8、6=(V1 ,V3), 图的实例图的实例10 图图G(或图或图D)的点数记为的点数记为p（G）(或或P（D）)，边（或弧）的条数记为边（或弧）的条数记为q(G) (或或q(D),在不会引起误会时，也分别简记为在不会引起误会时，也分别简记为p,q . 下面介绍一些基本名词和记号，先考虑无向图下面介绍一些基本名词和记号，先考虑无向图 G=（V，E）：）：若若 e=u,v ,则称则称 u ,v 是是 e 的的端点端点 ,也称也称 u ,v 是是相邻相邻的。称的。称 e 是点是点 u , v 的的关关联边联边。若边的两个端点相同，则该边成为。若边的两个端点相同，则该边成为环环（如图（如图107中的中的
9、 e7 ）；）；如两如两点之间有多条边，则称这些边为点之间有多条边，则称这些边为多重边多重边。（如图（如图107中的中的e1， e2 ）。）。一个无环、无多重边的图称一个无环、无多重边的图称简单图简单图，无环但，无环但有多重边的图称有多重边的图称多重图多重图。以。以 v 为端点的边的为端点的边的条数称为点条数称为点 v 的的次数，次数，记为记为 d ( v ) ，如在右如在右图中：图中：d ( v1) = 4, d ( v2) = 3, d ( v 4 ) = 4 ( 环环 e7在计算在计算d ( v 4) 时算作两次时算作两次)。 称次数为一的点为称次数为一的点为悬挂点悬挂点，悬挂点，悬挂点
10、的关联边为的关联边为悬挂边悬挂边，次数为，次数为 0 的点称为的点称为孤立点孤立点（点击）。次数为奇数的点称为（点击）。次数为奇数的点称为奇点奇点，次数为偶数的点称为，次数为偶数的点称为偶点偶点.V1V2V3V4253 页页 图图 107e1e7e6e5e4e3e2V5V6次与简次与简单图单图11端点的度 d(v)：点 v 作为边端点的个数；奇点：d(v)=奇数； 偶点：d(v)=偶数；悬挂点：d(v)=1；悬挂边：与悬挂点连接的边；孤立点：d(v)=0；空图：E = ，无边图12 定理1 所有顶点次数之和等于所有边数的2倍。 定理2 在任一图中，奇点的个数必为偶数。 基本定理基本定理13链：
11、 由两两相邻的点及其相关联的边构成的点边序列;如: v0 ,e1 ,v1 ,e2 ,v2 ，e3 ,v3 ,vn-1, en , vn ; v0 ，vn分别为链的起点和终点； 初等链：链中所含的点均不相同 简单链：链中所含的边均不相同；链14圈第一个点和最后一个点相同的链叫第一个点和最后一个点相同的链叫圈圈。中间点皆不相同的圈叫中间点皆不相同的圈叫初等圈初等圈。所有边。所有边皆不相同的圈叫皆不相同的圈叫简单圈简单圈。15连通图给定图给定图G，若其中任何两点之间至少有若其中任何两点之间至少有一条链，则称一条链，则称G为为连通图连通图，否则称为，否则称为不连不连通图通图；若若G 不是连通图，则可将
12、它分为不是连通图，则可将它分为若干个连通的若干个连通的分图分图。16v8v9e10v2v1v4e4e1e2e3v3v6v5v7e5e6e9e7e8在图10-9中，链（v1,v2,v3,v4,v5,v3,v6,v7)是简单链，非初等链。链（v1,v2,v3,v6,v7)是初等链。 （v1,v2,v3,v4,v1)是初等圈。（v4,v1,v2,v3,v5,v7,v6,v3,v4)是简单圈，非初等圈（中间有相同点）。17V1V3V4V5V2图图 G图图 G VV3图图 G的一个的一个支撑子图支撑子图V1V4V5V2V1V3V4V5V2给定一个图给定一个图G=（V，E）如果图如果图G= （V，E），）
13、，满足条满足条件：件：V=V， E E，则称则称 G是是 G 的一个的一个支撑子图支撑子图。即去掉。即去掉G的一些的一些边（边的端点并不随边一起去掉）后所得的图称边（边的端点并不随边一起去掉）后所得的图称G的支撑的支撑子图。子图。 设设 vV(G),用用 Vv表示从表示从 G中去掉点中去掉点v及其关联边后所及其关联边后所的到的图。的到的图。18V1V3V4V5V2图图 GV1V3V4V5V2V1V3V4V5V2V1V3V4V5V2图图 G的支撑子图的支撑子图V1V3V4V5V2基本概念419以下讨论有向图。设有一个有向图以下讨论有向图。设有一个有向图D=（V，A），），去掉去掉D中所有弧上的箭
14、中所有弧上的箭头，得一无向图，叫头，得一无向图，叫D 的的基础图基础图，记为，记为G（D）。）。 给定弧给定弧a=( u,v ),称称 u 为为 a 的的始点始点，称，称 v 为为 a 的的终点终点。 有向图有向图D中的一个点弧交错序列，如果在其基础图中的一个点弧交错序列，如果在其基础图G（D）中对应一条链，则称中对应一条链，则称D的这一点弧交错序列为图的这一点弧交错序列为图D的一条的一条链链。若若D的链上每条弧的左右两点分别是该弧的始点和终点，就的链上每条弧的左右两点分别是该弧的始点和终点，就称该链为一条称该链为一条路路。若。若路路的第一个点与最后一个点相同，就称的第一个点与最后一个点相同，
15、就称之为之为回路回路。初等路初等路是中间点皆不相同的路。是中间点皆不相同的路。V1V2V3V4V5V6a1a2a3a4a5a6a7a8a9a10a11V7 如点弧交错序列如点弧交错序列 ：V1,a2,V3,a8,V5,a10,V6,a11,V7 是链不是路。是链不是路。 而而点弧交错序列：点弧交错序列：V1, a1,V2, a5,V4, a7,V6 , a11,V7 是链也是路。是链也是路。基本概基本概念念5202.1树及其性质在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。21已知有五个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话（允许通过其它城市），并且
16、电话线的根数最少。不含圈的连通图v2v3v5v4v122定义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是一个树的充分必要条件是任意两个顶点之间有且仅有一条链。23从以上定理，不难得出以下结论： （1）从一个树中任意去掉一条边，那么剩下的图不是连通图，亦即，在点集合相同的图中，树是含边数最少的连通图。（2）在树中不相邻的两个点之间加上一条
17、边，那么恰好得到一个圈。242.2图的支撑树定义2 设图T=(V,E)是图G=(V,E)的支撑子图,如果图T=(V,E)是一个树,那么称T是G的一个支撑树。v6v5v2v3v4v1图1014av6v2v4v1bv3v525若若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 。26定理定理 7 图图G有支撑树的充分必要条有支撑树的充分必要条件是件是 G 连通连通。必要性显然。必要性显然。充分性充分性 设设G连通。若连通
18、。若G是树，则是树，则G是它自是它自己的支撑树。若己的支撑树。若G非树，则非树，则 G含圈，从该含圈，从该圈中任意去掉一边，得圈中任意去掉一边，得G的支撑子图的支撑子图G，若，若G为树，则是为树，则是G的支撑树；若的支撑树；若 G 非树，则非树，则G 含圈，又去掉圈中任意一含圈，又去掉圈中任意一条边，如此反复进行，因边数有限，最条边，如此反复进行，因边数有限，最后必得后必得G的一个支撑树。证毕！的一个支撑树。证毕！27上定理的证明过程实际上给出了寻找一上定理的证明过程实际上给出了寻找一个图的支撑树的一个方法，名个图的支撑树的一个方法，名“破圈破圈法法”，就是任取图中一个圈，去掉圈中，就是任取图
19、中一个圈，去掉圈中一条边，如此反复进行直到获得一个一条边，如此反复进行直到获得一个支撑树为止。支撑树为止。28例6:用破圈法求出图的一个支撑树取一个圈(v1,v2,v3,v1)，在一个圈中去 掉边e3 。在剩下的图中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4 。再从圈（v3,v4 v5,v3）中去掉边e6 。再从圈 (v1,v2,v5,v4,v3,v1 ）中去掉边e8，这样，剩下的图不含圈，于是得到一个支撑树。V5V4V2V3V1e6e5e4e3e2e1e8e7v3v2e1e2e5e7v1v4v529例6:用避圈法求出图的一个支撑树V1V2V3V4V5V6e1e2e3e4e5e6
20、e7e8e9302.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的的最小最小支撑树支撑树，简称，简称最小树最小树。311、 “避圈法避
21、圈法”生长法生长法 Kruskalv6v5v2v3v4(a)v162753544v3v2v1v4v6v5513142(b)322、 “破圈法破圈法”v6v5v2v3v4(a)v1627535441(b)v3v2v1v4v6v55314233第3节最短路径问题最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。也可以用于解决其它的最优化问题。34例10 如图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从v1出发，经过这个交通网到达v8，要寻求是总路程最短的线
22、路。v2v3v4v5v6v7v8v9613622144262331010v13.1 引例35 一般意义下的最短路问题：设一个赋权有向图D =（V，A），对于每一个弧a =（vi,vj），相应地有一个权wij。vs,vt是D中的两个顶点，P是D中从vs到vt的任意一条路，定义路的权是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）一般不相等。363.2最短路算法
23、(Dijkstra 1959) 下面介绍在一个赋权有向图中寻求最短路的方法Dijkstra算法，它是在1959年提出来的。目前公认，在所有的权wij 0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj的最短路。37Dijkstra算法的基本思想从vs出发，逐步向外寻找最短路。在运算过程中，与每个点对应，记录一个数(称为这个点的标号)。它或者表示从vs到该点的最短路权（叫做P 标号,即永久标号），或者表示从vs到该点最短路权的上界（叫做T 标号,即临时标即临时标表号表号）。算法的每一步是去修改T 标号，把某一个具有T 标号的点改变为具有P
24、标号的点，使图D 中具有P 标号的顶点多一个。这样，至多经过p-1步，就可求出从vs到各点vj的最短路。38以例10为例说明这个基本思想。VS=V1。因为Wij 0，d（v1,v1）=0。这时，v1是具有P标号的点。现在看从v1出发的三条弧（v1,v2），（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
25、,v2）到达v2，或者沿（v1,v3）到达v3，而这时的路程已是6或者3单位。39看从v1出发的三条弧（v1,v2），（v1,v3）和（v1,v4），mind(v1,v1)+w12 ,d(v1,v1)+w13 , d(v1,v1)+w14 = d（v1,v4）=1。v2v3v4v5v6v7v8v9613622144262331010v1由于所有的权wij 0，因此，不论他如何再从v2或者v3到达v4，所经过的总路程都不会比1少，于是就有d（v1,v4）=1。这样就使V4变成具有P标号的点。40现在看从v1和v4指向其余点的弧。如上所述，从V1出发，分别沿（v1,v2），（v1,v3）到达v2，
26、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）=3。这样，又使点v3变为具有P 标号的点，不断重复以上过程，就可以求出从vs到达任一点vj的最短路。v2v3v4v5v6v7v8v9613622144262331010v141在下述的Dijkstra算法中，以P，T 分别表示某一个点的P 标号，T 标号。Si表示在第i
27、步时，具有P 标号点的集合，为了在算出从vs到各点的距离的同时，也找出从vs到各点的最短路，于是，给每一个点v一个值。当算法结束时，如果(v)= m，则表示在从vs到v 的最短路上，v 的前一个点是vm。如果(v)=M，则表示在图D 中不含有从vs 到达v 的路。(v)=0，表示v=vs。42Dijkstra算法的步骤开始（开始（i i=0=0） 令令S S0 0=v vs s ，P P（v vs s）=0=0，( (v vs s)=0)=0，对对每每一一个个v v v vs s，令令T T（v v）=+=+，( (v v)=)=M M ，令令k k= =s s；43（1）如果Si=V，则算法
28、结束，对每一个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，44如果T(vji)=0,简记简记 c i j ,表示该弧表示该弧的最大通过能力。常称的最大通过能力。常称D为为网络网络，记为，记为D=（V，A，C）。）。 所谓网络上的所谓网络上的流流，是指定义在每一条弧，是指定义在每一条弧（ v i ， v j ）A上的一个函数集上的一个函数集 : f = f（ v i ， v
29、 j ）= f i j , 并称并称 f i j 为为 弧弧（ v i ， v j ）上的上的 流量流量。502、可行流与最大流定义定义 7 满足下述条件的流满足下述条件的流 f 称为称为可行流可行流：(1) 容量限制条件容量限制条件对每一条弧对每一条弧 ( v i ， v j ),流量不得超过容量流量不得超过容量 0 f i j c i j ，(2)平衡条件平衡条件注意：零流，即所有注意：零流，即所有f i j=0,（ v i ， v j ）A，的流，是可行流！，的流，是可行流！51网络最大流问题就是在网络上求一个可行流就是在网络上求一个可行流f i j使流量使流量v（ f ）达到最大。）达
30、到最大。523、增广链在在D=（V，A，C）上给定一个可行流）上给定一个可行流f i j饱和弧：饱和弧：f i j=c i j非饱和弧：非饱和弧： f i j053网络D=（V，A，C）上取出一条从发点到收点的链u：前向弧,方向与链一致，全体记为u后向弧,方向与链相反，全体记为u定义8，增广链给定一条从发点到收点的链，若链上所给定一条从发点到收点的链，若链上所有前向弧皆非饱和，而所有有前向弧皆非饱和，而所有 后向弧皆非后向弧皆非零流弧，则称该链为零流弧，则称该链为增广链增广链54 容量网络G =（V1，E，C），vs为始点，vt为终点。如果把V分成两个非空集合 使 ，则所有始点属于V1，而终点
31、属于 的弧的集合，称为由V1决定的截集,记作 。截集 中所有弧的容量之和，称为这个截集的容量，记为 。 vsv1v2v4v3vt374556378S4、截集与截量55vsvtv1v3v2v4( 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)。割容量为：割容
32、量为：5+2=7网络最大流的流量网络最大流的流量=容量最小的割容量容量最小的割容量56定理定理 8 可行流可行流 f* 是最大流当且仅当不存是最大流当且仅当不存在关于在关于 f* 的增广链。的增广链。574.2寻求最大流的标号法（Ford ,Fulkerson) 1、标号过程2、调整过程58272 页页 例例14vsvtv1v3v2v4( 3,3 )( 4,3 )( 5,1 )( 2,2 )( 1,1 )( 1,1 )( 5,3 )( 3,0 )( 3,1 )( c ij,fij )0,+vs,4v1,1v2,1v4,1v3vsvtv1v2v4( 3,3 )( 4,4 )( 5,2 )( 2,
33、2 )( 1,0 )( 1,1 )( 5,4 )( 3,0 )( 3,1 )( c ij,fij )0, +vs,359第第5节节 最小费用最大流最小费用最大流寻找最小费用的最大流方案（寻找最小费用的最大流方案（274276页）页）60 设设D=（V，A，C）是一个容量网络，再给出每条弧是一个容量网络，再给出每条弧（ v i ， v j ）上的单位上的单位运价运价 bi j , 并以（并以（c i j , ，b ij ）表示表示弧弧（ v i ， v j ）上的容量与单位运价。上的容量与单位运价。假定假定D有增广链有增广链，所谓所谓增广链增广链的费用是指沿的费用是指沿增广链增广链增加一单位物资
34、所增加增加一单位物资所增加的费用：的费用： bi j - - bi j ，寻找关于可行流寻找关于可行流f f 的最小费用链的方法如下：的最小费用链的方法如下：+ + - -对于对于 f ，定义一个赋权有向图如下：其顶点集与定义一个赋权有向图如下：其顶点集与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 。. 注意注意,长度为长度为+的弧可以抹去的弧可
35、以抹去.614vsvtv1v2v34123162vsvtv1v2v3按最短路根据弧按最短路根据弧的容量调整运量的容量调整运量得流量图下图得流量图下图.W(f (0)0000vsvtv1v2v3(a )( b )f (1),v(f (1 )=51-23162vsvtv1v2v3-1-1W(f (1)(c )作相应赋权有向图并求出最短路作相应赋权有向图并求出最短路bi j ,若若 f i j 0+, , 若若 f i j = 0w i j =w j i =以以0流流 f(0)=0为初始为初始流构造赋权有向图流构造赋权有向图并算得最短路如右并算得最短路如右000555276页各图的解释：页各图的解释
36、：(4,10)(1,8)(2,5)(3,10)(1 ,7)(6,2)(2,4)(bij,cij)（运价运价，容量），容量）276页解释页解释62140550500vsvtv1v2v3( b )f (1),v(f (1 )=513162vsvtv1v2v3-1W(f (1)(c )作相应赋权有向图并求出最短路作相应赋权有向图并求出最短路0550500vsvtv1vsv2v3( d )43-162vsvtv1v2v3-1W(f (2)(e )-4沿最短路调整沿最短路调整,得左下图得左下图作相应赋权有向图作相应赋权有向图并求出最短路并求出最短路vsvtv1v2v3bi j ,若若 f i j 0+,
37、 , 若若 f i j = 0w i j =w j i =题题目目-127(4,10)(1,8)(2,5)(3,10)(1,7)(6,2)(2,4)(bij,cij)-2-2同上同上16312550700vsvtv1vsv2v3( d )43-162vsvtv1v2v3-1W(f (2)(e )-4作相应赋权有向图作相应赋权有向图并求出最短路并求出最短路4-23-162vsvtv2v3-1W(f (3)(g )-4-2-32550700vsvtv1v2v3( f )f ( 3),v(f ( 3 ) )=10作相应赋权有向图作相应赋权有向图并求出最短路并求出最短路沿最沿最短路调整流量短路调整流量
38、bi j ,若若 f i j 0+, , 若若 f i j = 0w i j =w j i =vsvtv1v2v3题题目目833p.276(4,10)(1,8)(2,5)(3,10)(1,7)(6,2)(2,4)(bij,cij)-2同上同上2642853703vtv1vsv2v3( h )f ( 4),v(f ( 4 ) )=114-23-162vsvtv2v3-1W(f (3)(g )-4-2-32853703vsvtv1v2v3( f )f ( 3),v(f ( 3 ) )=104-23-16vsvtv2v3-1W(f (4)(i )-4-2-32从发点到收点的路长为无限大从发点到收点的
39、路长为无限大,故左边的网络流是最小费用最大流故左边的网络流是最小费用最大流.完完!vsvtv1v2v3bi j ,若若 f i j 0+, , 若若 f i j = 0w i j =w j i =沿最沿最短路调整流量短路调整流量作相应赋权有向图作相应赋权有向图并求出最短路并求出最短路作相应赋权有向图作相应赋权有向图并求出最短路并求出最短路题题目目3444v1v1p.276(4,10)(1,8)(2,5)(3,10)(1,7)(6,2)(2,4)(bij,cij)同上同上65同上，终同上，终5642724vsvtv1v2v32853703vtv1vsv2v334444-23-16vsv2v3-1
40、W(f (4)(i )-4-22vtv1(4,10)(1,8)(2,5)(3,10)(1,7)(6,2)(2,4)vsvtv1v2v3(bij,cij)题题目目p.276这是刚才获得的一个最小费用最大流方案这是刚才获得的一个最小费用最大流方案, V（f）=11,cost=55以下也是一个最大流方案以下也是一个最大流方案, V（f）=11 ;但费用较大但费用较大,cost=67。66例例 十名研究生参加六门课程的考试十名研究生参加六门课程的考试 ，个人选修课程不同，个人选修课程不同 ，每人，每人参加考试的课程（打参加考试的课程（打*号者）见下表号者）见下表 ：规定三天内靠完：规定三天内靠完 ，每
41、天上、，每天上、下午各考一门。考下午各考一门。考 生希望每天最多考一门，又课程生希望每天最多考一门，又课程A必须在第一必须在第一天上午考，天上午考，F安排在最后一门考，安排在最后一门考，B只能安排在上午考，试列出一只能安排在上午考，试列出一张满足各方要求的考试日程表。张满足各方要求的考试日程表。 课程课程研究生研究生A B C D E F1*2*3*4*5*6*7*8*9*10*67解：每门课程用一个点表示，同一个人参加的课程用边联起来，得图如下：解：每门课程用一个点表示，同一个人参加的课程用边联起来，得图如下：课程课程A、E可排在同一天，可排在同一天，B、C可排在同一天，可排在同一天， D、
42、F也可排在同一天。再根也可排在同一天。再根根据其他要求可得满足各方面要求的考试日程表如下：根据其他要求可得满足各方面要求的考试日程表如下：课程课程研究生研究生A B C D E F1*2*3*4*5*6*7*8*9*10*ABCDEF第一天第一天第二天第二天第三天第三天上午上午下午下午AEBCDF68如下图所示，某人从住处到工作地上班，图中各弧旁的数字为该弧的长度（单位：公里）。试问该人应选择哪条线路，使从家出发到工作地的路程最短。用Dijkstra标号法求解上述问题。（要求写出主要过程）69最大流问题如下图所示，图中弧旁数字为容量，求下图网络中到的最大流量 sv4v1v3v2vtv343155212sv4v1v3v2vtv34355212svsv4v4v1v1v3v3v2v2vtvtv343155212svsv4v4v1v1v3v3v2v2vtvtv3435521270下面左图表示一个网络，弧旁的数字为（bij,cij），右图为一个可行方案，试在右图所示可行流的基础上按最小费用最大流的求解方法进行下一步变换（只要求作一步计算，不需完整计算；要求作出赋权有向图、找出最小费用增广链和调整后的网络图）。 71
