《运筹学》课件 第7章 图论

图论第七章图与网络分析主要内容：7.1图的基本概念与基本定理7.2树和最小支撑树7.3最短路问题7.4最大流问题7.5最小费用流问题什麼是图？图论中所谓的图是由一些点(vertices)，和一些连接兩点的边(edges)所形成的7.1图的基本概念与基本定理

图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。关于图的第一篇论文是瑞士数学家欧拉（E.Euler）在1736年发表的解决“哥尼斯堡”七桥难题的论文；德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉将这个问题抽象成图所示图形的一笔画问题。Königsberg(Koenigsberg)哥尼斯堡，原为东普鲁士(Prussia)首府，现属俄罗斯(飞地)，名为加里宁格勒(Kaliningrad)现德国拜仁的哥尼斯堡哥尼斯堡七橋問題:要如何走過每座橋恰一次，再返回出發點？普瑞格爾河哥尼斯堡七橋問題可以看成是：對這樣一個封閉的圖形，是否可以一筆畫完成它並且回到原點數學家歐拉(Euler,1707-1783)於1736年嚴格地證明了上述哥尼斯堡七橋問題無解，並且由此開創了圖論的典型思維方式及論證方式即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。

在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。图论应用举例例如，在组织生产中，为完成某项任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。各种通信网络的合理架设交通网络的合理分布等环游世界与Hamilton问题十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？Hamilton圈（环球旅行游戏）地图着色与四色问题任意一张地图，最少需要用多少颜色來着色，才能让相邻的两块涂上不同的颜色？1852年提出四色猜想1879年A.Kempe宣布证明了四色定理1890年Heawood发现Kempe的错误1976年美国数学家K.Appel及W.Haken在计算机的辅助下解決图论的应用广播频道与着色问题当两个广播电台距离太近时,若给它们相同的频道会产生干扰。如何设置每个电台的频道,使得它们既不相互干扰,又使频道总数最少?AB广播频道与着色问题图的点着色(Coloring)药品存放与无关集化学药品存放问题某些药品放置太近可能爆炸，有两个实验室，最多能有多少药品能放在一起碰!!药品存放与无关集配对问题与匹配(Matching)配对问题有一些机器人要分配任务，并不是所有机器人都能够完成所有的任务，要求每个机器人都要分配一项工作，怎么分？ABCcba信息流传与广播问题(Broadcasting)信息流传问题班上有一件事情要宣布，班长想打电話告訴全班。但若他一个个打似乎太慢了。假设一个班有五十人，打一通电话需要一分钟，那总共就需要四十九分钟。但若是他打了第一个电话后，便请第一个同学再打给別人；第二通电话打了之后，又再请第二个同学打给別人；依此类推，但问题是，也许某些同学沒有某些同学的电话，那么这时，怎样在最短时间內打完所有电话？5次6次计算机网络与连通度(Connectivity)问题计算机网络断线问题一公司内有多部计算机并连成网络,我们想知道其网络设计得好不好。考虑若有某线路毁损后,所有的机器是否仍可彼此互通?进一步,讨论该网络设计可保证在同时至多有几条线路毁损后仍互通?例6.1

图6.2是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。石家庄太原北京天津塘沽济南青岛徐州连云港南京上海郑州武汉重庆图6.2

例6.2

有六支球队进行足球比赛，我们分别用点v1，…，v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2

队，v2队战胜v3

队，v3队战胜v5队，如此等等。这个胜负情况，可以用图6.3所示的有向图反映出来图6.3v3v5v2v4v6v1

从以上的几个例子可以看出，我们用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。一般来说，通常用点表示研究对象，用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。

综上所述，图论中的图是由点和点与点之间的线所组成的。通常，我们把点与点之间不带箭头的线叫做边，带箭头的线叫做弧。如果一个图是由点和边所构成的，那么，称为无向图，记作G=(V，E)，其中V表示图G

的点集合，E表示图G的边集合。连接点vi,vj

V的边记作[vi,vj]，或者[vj,vi]。如果一个图是由点和弧所构成的，那么称为它为有向图，记作D=(V,A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。例如.图6.4是一个无向图G=（V，E），其中V={v1,v2,v3,v4}E={[v1,v2],[v2,v1],[v2,v3],[v3,v4],[v1,v4],[v2,v4],[v3,v3]}v3v2v1v4图6.4图6.5

是一个有向图D=（V，A）其中V={v1,v2,v3,v4,v5,v6,v7}A={(v1,v2),(v1,v3),(v3,v2)(v3,v4),(v2,v4),(v4,v5),(v4,v6),(v5,v3),(v5,v4),(v5,v6),(v6,v7)}图6.5v7v5v3v4v2v6v1下面介绍一些常用的名词：一个图G或有向图D中的点数,记作P(G)或P(D),简记作P,边数或者弧数,记作q(G)或者q(D),简记作q。如果边[vi,vj]

E,那么称vi,vj

是边的端点，或者vi,vj是相邻的。如果一个图G中，一条边的两个端点是相同的,那么称为这条边是环，如图6.4中的边[v3,v3]是环。如果两个端点之间有两条以上的边，那么称为它们为多重边，如图6.4中的边[v1

,v2],[v2

,v1]。一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。

以点v为端点的边的个数称为点v的度，记作d(v),如图6.4中d(v1)=3，d(v2)=4,d(v3)=4,d(v4)=3。度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。端点的度

d(v)：点v作为端点的边的个数奇点：d(v)=奇数；偶点：d(v)=偶数；悬挂点：d(v)=1；悬挂边：与悬挂点连接的边；孤立点：d(v)=0；空图：E=

，无边图v1v2v3v4v5v6v1v7v6v5v4v3v2V={v1,v2,v3,v4,v5,v6,v7}d(v1)=3;d(v2)=5;d(v3)=4;d(v4)=4;d(v5)=1;d(v6)=3;d(v7)=0其中v5

为悬挂点，v7为孤立点。

定理6.1

所有顶点度数之和等于所有边数的2倍。

证明：因为在计算各个点的度时，每条边被它的两个端点个用了一次。v1v5v4v3v2简单图（2）（4）（3）（3）（2）v1v5v4v3v2多重图（4）（6）（3）（3）（2）定理6.2

在任一图中，奇点的个数必为偶数。证明：设V1，V2

分别是图G中奇点和偶点的集合，由定理6.1，有因为是偶数，也是偶数，因此也必是偶数，从而V1

中的点数是偶数。图的连通性：链：由两两相邻的点及其相关联的边构成的点边序列。如:v0,e1

,v1

,e2

,v2，e3

,v3

,…,vn-1,en

，

vn;v0，vn分别为链的起点和终点

。记作（v0,v1

,v2，,v3

,…,vn-1,vn）简单链：链中所含的边均不相同；初等链：链中所含的点均不相同,也称通路；圈：若v0≠vn则称该链为开链，否则称为闭链或回路或圈；简单圈：如果在一个圈中所含的边均不相同初等圈：除起点和终点外链中所含的点均不相同的圈；v1v2v4v3v5v6v7v5v9初等链:(v1,v2,v3,v6,v7,v5)初等圈：(v1,v2,v3,v5,v4,v1)简单链：(v1,v2,v3,v4,v5,v3)

简单圈：(v4,v1,v2,v3,v5,v7,v6,v3,v4)以后除特别声明，均指初等链和初等圈。v1v2v3v4v5不连通图v1v5v4v3v2v6连通图：图中任意两点之间均至少有一条通路，否则称为不连通图。

连通图子图定义：如果V2

V1,E2

E1

称G2是G1

的子图；真子图：如果V2

V1,E2

E1

称G2

是G1

的真子图；部分图：如果V2=V1,E2

E1

称G2

是G1

的部分图或支撑子图；

导出子图：如果V2

V1,E2={[vi,vj]∣vi,vj

V2},称G2

是G1

中由V2

导出的导出子图。设G1=[V1,E1],G2=[V2,E2]G1G2真子图G3子图

部分图G4导出子图有向图：关联边有方向弧：有向图的边a=(u,v),起点u,终点v；路：若有从u

到v

不考虑方向的链,且各方向一致,则称之为从u到v的路；初等路:

各顶点都不相同的路；初等回路:u=v

的初等路;连通图：

若不考虑方向是无向连通图;

强连通图：任两点有路;

基本概念点边,弧无向图链端点关联边有向图圈始点,终点多重边简单图初等链/圈次环多重图简单链/圈奇点,偶点连通图基础图悬挂点悬挂边不连通图路弧立点支撑子图回路

例一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过河到河东.由于船小,一次只能带一物过河，并且狼与羊,羊与菜不能独处.给出渡河方法.

解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1,否则取0),共有24=16种状态.在河东岸的状态类似记作.

由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的,从而对应状态(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允许的.

以可允许的10个状态向量作为顶点,将可能互相转移的状态用线段连接起来构成一个图.

根据此图便可找到渡河方法.(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,1,0,0)(0,1,0,1)(0,1,0,1)(0,1,0,0)(0,0,1,0)(0,0,0,1)(0,0,0,0)(1,0,1,0)(1,0,1,1)(1,1,0,1)(1,1,1,0)(1,1,1,1)河西=(人,狼,羊,菜)河东=(人,狼,羊,菜)

将10个顶点分别记为A1,A2,…,A10,则渡河问题化为在该图中求一条从A1到A10的路.

从图中易得到两条路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.图的矩阵表示1.邻接矩阵Adjacencymatrix表示图中两点之间的相互关系两点之间有弧或边的，用1表示，否则用0表示，构成一个矩阵Av2v4v6v5v1v3v1v2v3v4v5v6v1011000v2101110v3110010v4010011v5011101v6000110v1v2v3v4v5多重边v1v2v3v4v5v101100v210110v311001v401001v500110有向图v1v7v2v5v3v4v6v8v9v1v2v3v4v5v6v7v8v9v1011100000v2000010000v3010100000v4000001000v5000101110v6000010100v7000000010v8000000000v9000010010矩阵A的元素全为0的行所对应的点称为汇点上图v8矩阵A的元素全为0的列所对应的点称为源点上图v1、v97.2树和最小支撑树一、树及其性质在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。

例6.3

已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。如果用六个点v1…v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。表示任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图6.2.1是一个不含圈的连通图，代表了一个电话线网。图6.2.1v6v3v4v2v5v1树及其性质树：既简单又很有用树：一个无圈的连通图组织结构图ManagerSubordSubord荣国公贾代善贾赦贾政贾琏贾珠贾宝玉贾环贾兰定理定理1：设G=(V,E)是一个树，p(G)>=2则G中至少有两个悬挂点。定理2：图G=(V,E)是一个树的充要条件是G不含圈，且恰有p-1条边。定理3：图G=(V,E)是一个树的充要条件是G是连通图，且q(G)=p(G)-1。定理4：图G=(V,E)是一个树的充要条件是任意两个顶点之间恰有一条链。推论从一个树中去掉任意一条边，则余下的图是不连通的。在树中不相邻的两个点间添上一条边，则恰好得到一个圈图的支撑树设图T=(V,E‘)是图G=(V,E)的一个支撑子图，如果T是一个树，则称T是G的一个支撑树定理5：图G有支撑树的充要条件是图G是连通的。破圈法：任取一个圈，从中去掉一条边，再对余下的图重复直到不再含圈时为止。破圈法避圈法在图中任取一条边，找到一条与之不构成圈的边，再找一条前两边不构成圈的边重复直到不再能进行为止取出的边数为p-1条避圈法最小支撑树问题给定图G=(V,E)，对G中的每一条边[vi,vj]，相应地有一个数wij，则称这样的图为赋权图wij称为边[vi,vj]上的权权是与边有关的数量指标，可以是距离、时间、费用等。赋权图不仅指出各个点之间的邻接关系，而且同时也表示出各点之间的数量关系广泛应用于解决工程技术及管理等领域的最优化问题最小支撑树问题就是赋权图上的最优化问题之一。设有一个连通图G=(V,E)，每一边e=[vi,vj]有一个非负权w(e)=wij(wij>0)如果T=(V,E’)，是G的一个支撑树，称E’中所有边的权之和为支撑树T

的权，记为w(T)如果支撑树T*的权w(T*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树（最小树），即式中对G的所有支撑树T取最小最小支撑树问题就是要求G的最小支撑树。方法有二：避圈法Kruskal破圈法常见求赋权图的最小树。

例6.4某厂内联结六个车间的道路网如下所示，已知每条路的长，要求沿道路架设联结六个车间的电话线网，使电话线的总长最小。v1v2v4v6v3v5657152344避圈法求最小支撑树v1v2v4v6v3v515234i=1,E0=Φ。从E中选最小权边。依次选最小权边，并使之不构成圈。共选5条边v1v2v4v6v5657152344最后，电话线总长1+2+3+4+5=15v3破圈法求最小支撑树任取一个圈，从中去掉一条权最大的边。依次重复，直到不含圈为止。v1v2v4v6v5657152344最后，电话线总长1+2+3+4+5=15v3矩阵计算方法TTTTTTTTTTTTTTTTTTTTT矩阵计算结果一.引言最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。也可以用于解决其它的最优化问题。

7.3最短路问题例6.5已知如图所示的单行线交通网，每弧旁的数字表示这条单行线的距离。现在某人要从v1出发，通过这个交通网到达v8

，求使总距离最短的旅行线路。v1v7v2v5616321v32v4v610310v8v9246234?路很多v1v7v2v5616321v32v4v610310v8v92462341+10+2+4=176+1+6=133+2+1+3+4=133+2+10+10+6=31哪一条最短？最短路算法如果P是D中从vs到vi的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。所有wij≥0的情形—Dijkstra法1959Dijkstra法基本思路：从vs出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为此点的标号)，它或者表示从vs到该点的最短路的权(称为P标号)，或者是从vs到该点的最短路的权的上界(称为T标号)方法的每一步是修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的点多一个，如此经过p-1步，就可以求出从vs到各点的最短路。Dijkstra法具体步骤开始(i=0)，令S0={vs},P(vs)=0,λ(vs)=0,对每一个v≠

vs，令

T(v)=+∞,λ(v)=M,令k=s如果Si=V，算法终止，这时，对每个v

Si，d(vs,v)=P(v)

；否则转入步骤2考察每个使(vk,vj)

A且vj

Si的点vj。如果T(v)>P(vk)+wkj，则把T(vj)修改为P(vk)

+wkj

，把λ(vj)修改为k；否则转入步骤33.令T(vji)=min{T(vj)}如果T(vji)<∞则把vji的T标号变为P标号P(vji)=T(vji)，令Si+1=SiU{vji}，k=ji,把i换成i+1，转入步骤1；否则终止，这时对每一个，而对每一个v

Si，d(vs,v)=T(v)v1v2v3v4v5v6v7v80v2v3v4v5v6v7v8PTλ0∞0M∞M∞M∞M∞M∞M∞Mv1v7v2v5616321v32v4v610310v8v9246234若T(v)>P(vk)+wkj则T(v)=P(vk)+wkj

λ(vj)修改为k找到min{T(vj)}，将其T

P标号P(vj)=T(vj)，S=

{v1，

}6311111v4,v3,1143535v2,626v5,105951259v7,10v6,12v8,v1到v8最短路V13258Dijkstra'sShortestPathAlgorithmFindshortestpathfromstot.s3t267452418291415530204416116196Dijkstra'sShortestPathAlgorithms3t267452418291415530204416116196

0

distancelabelS={}PQ={s,2,3,4,5,6,7,t}Dijkstra'sShortestPathAlgorithms3t267452418291415530204416116196

0

distancelabelS={}PQ={s,2,3,4,5,6,7,t}delminDijkstra'sShortestPathAlgorithms3t267452418291415530204416116196

15

9

14

0

distancelabelS={s}PQ={2,3,4,5,6,7,t}decreasekey

X

XXDijkstra'sShortestPathAlgorithms3t267452418291415530204416116196

15

9

14

0

distancelabelS={s}PQ={2,3,4,5,6,7,t}

X

XXdelmins3t267452418291415530204416116196

15

9

14

0S={s,2}PQ={3,4,5,6,7,t}

X

XXs3t267452418291415530204416116196

15

9

14

0S={s,2}PQ={3,4,5,6,7,t}

X

XXdecreasekeyX

33s3t267452418291415530204416116196

15

9

14

0S={s,2}PQ={3,4,5,6,7,t}

X

XXX

33delmins3t267452418291415530204416116196

15

9

14

0S={s,2,6}PQ={3,4,5,7,t}

X

XXX

33

44XX

32s3t267452418291415530204416116196

15

9

14

0S={s,2,6}PQ={3,4,5,7,t}

X

XX

44Xdelmin

X

33X

32s3t2674518291415530204416116196

15

9

14

0S={s,2,6,7}PQ={3,4,5,t}

X

XX

44X

35X

59X24

X

33X

32s3t267452418291415530204416116196

15

9

14

0S={s,2,6,7}PQ={3,4,5,t}

X

XX

44X

35X

59Xdelmin

X

33X

32s3t267452418291415530204416116196

15

9

14

0S={s,2,3,6,7}PQ={4,5,t}

X

XX

44X

35X

59XX

51X

34

X

33X

32s3t2674518291415530204416116196

15

9

14

0S={s,2,3,6,7}PQ={4,5,t}

X

XX

44X

35X

59XX

51X

34delmin

X

33X

3224s3t2674518291415530204416116196

15

9

14

0S={s,2,3,5,6,7}PQ={4,t}

X

XX

44X

35X

59XX

51X

3424X

50X

45

X

33X

32s3t2674518291415530204416116196

15

9

14

0S={s,2,3,5,6,7}PQ={4,t}

X

XX

44X

35X

59XX

51X

3424X

50X

45delmin

X

33X

32s3t2674518291415530204416116196

15

9

14

0S={s,2,3,4,5,6,7}PQ={t}

X

XX

44X

35X

59XX

51X

3424X

50X

45

X

33X

32s3t2674518291415530204416116196

15

9

14

0S={s,2,3,4,5,6,7}PQ={t}

X

XX

44X

35X

59XX

51X

34X

50X

45delmin

X

33X

3224s3t267452418291415530204416116196

15

9

14

0S={s,2,3,4,5,6,7,t}PQ={}

X

XX

44X

35X

59XX

51X

34X

50X

45

X

33X

32s3t267452418291415530204416116196

15

9

14

0S={s,2,3,4,5,6,7,t}PQ={}

X

XX

44X

35X

59XX

51X

34X

50X

45

X

33X

32237184566134105275934682练习：求从1到8的最短路径237184566134105275934682X={1},w1=0min{c12,c14,c16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0237184566134105275934682X={1,4}min{c12,c16,c42,c47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},p2=2p1=0p4=1p2=2237184566134105275934682X={1,2,4}min{c13,c23,c25,c47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},p6=3p2=2p4=1p1=0p6=3237184566134105275934682X={1,2,4,6}min{c23,c25,c47,c67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},p7=3p2=2p4=1p1=0p6=3p7=3237184566134105275934682X={1,2,4,6,7}min{c23,c25,c75,c78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},p5=6p2=2p4=1p1=0p6=3p7=3p5=6237184566134105275934682X={1,2,4,6,7}min{c23,c53,c58,c78}=min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8X={1,2,3,4,5,6,7},p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8237184566134105275934682X={1,2,3,4,6,7}min{c38,c58,c78}=min{8+6,6+4,3+7}=min{14,10,11}=10X={1,2,3,4,5,6,7,8},p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10237184566134105275934682X={1,2,3,4,6,7,8}1到8的最短路径为{1，4，7，5，8}，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10无向图最短路的求法无向图最短路的求法只将前述Dijkstra步骤（2）改动一下即可。点标号：b(i)—起点vs到点vj的最短路长；边标号：k(i，j)=b(i)+cij，步骤：(1)令起点的标号；b(s)＝0。(3)计算集合B中边标号：k[i，j]=b(i)+cij(4)选一个点标号:

返回到第(2)步。(2)找出所有一端vi已标号另一端vj未标号的边集合

B={[i，j]}如果这样的边不存在或vt已标号则计算结束；求图所示v1到各点的最短路及最短距离①②③④⑤⑥⑦⑧4526178393261216180452231039612641166188122482418所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。237184562421182151124829

现问从u1到u8,的各条链中,哪一条的总长度最短?（0，1）

8211（2，1）

现问从u1到u8,的各条链中,哪一条的总长度最短?（0，1）2371845624211821511248298211（2，1）

67（4，3）

4最短链问题

现问从u1到u8,的各条链中,哪一条的总长度最短?（0，1）2371845624211821511248298211（2，1）

67（4，3）

4516（5，4）

最短链问题

现问从u1到u8,的各条链中,哪一条的总长度最短?（0，1）2371845624211821511248298211（2，1）

67（4，3）

4516（5，4）

7139（6，3）

最短链问题

现问从u1到u8,的各条链中,哪一条的总长度最短?（0，1）2371845624211821511248298211（2，1）

67（4，3）

4516（5，4）

7139（6，3）

15（7，6）

最短链问题

现问从u1到u8,的各条链中,哪一条的总长度最短?（0，1）

2371845624211821511248298211（2，1）

67（4，3）

4516（5，4）

7139（6，3）

15（7，6）

8（8，5）

最短链问题从u1到u8,的各条链中,最短链为1-3-4-6-5—8（0，1）

2371845624211821511248298211（2，1）

67（4，3）

4516（5，4）

7139（6，3）

15（7，6）

8（8，5）

最短链问题应用举例设备更新问题。某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧的，则需支付一定的维修费用。现在的问题是如何制定一个几年之内的设备更新计划，使得总的支付费用最少。我们用一个五年之内要更新某种设备的计划为例，若已知该种设备在各年年初的价格如下表，还知使用不同时间的设备所需要的维修费用如下表。第1年第2年第3年第4年第5年1111121213使用年限0-11-22-33-44-5维修费用5681118可供选择的设备更新方案显然是很多的。例如，每年都购置一台新设备，则其购置费用为11+11+12+12+13=59，而每年支付的维修费用为5，五年合计为25。于是5年的总费用为59+25=84再如，每1，3，5年各购进一台。此时设备购置费用为11+12+13=36，维修费用为5+6+5+6+5=27，5年总费用为36+27=63。如何制定总费用最省的设备更新计划呢？转化为最短路问题。用点代表“第年年初购进一台新设备”

这样上述设备更新问题就变为：在有向赋权图G=(V,E,F)(图解如下)中求v1到v6的最短路问题.

由实际问题可知,设备使用三年后应当更新,因此删除该图中v1到v5,v1到v6,v2到v6的连线；又设备使用一年后就更新则不划算,因此再删除该图中v1v2,v2v3,v3v4,v4v5,v5v6五条连线后得到从上图中容易得到v1到v6只有两条路：v1v3v6和v1v4v6.

而这两条路都是v1到v6的最短路.五年的总费用为53。例拣货路径问题Pickpath货架分布要拣货物第1步

从第1通道到第2通道

每条路径代表图中的一条边第2步

找出从第2通道到第3通道的每条路径第3步

找出从第3通道到第4通道的每条路径第4步

找出从第4通道到完成的每条路径FindtheshortestpathoftheassociatedgraphTheshortestpathontheassociatedgraphgivesanefficientpickpathinwarehouse对应图的最短路给出了仓库的有效拣选路径7.4网路的最大流和最小截量7.4.1网路的最大流的概念网路流一般在有向图上讨论定义网路上支路的容量为其最大通过能力，记为cij，支路上的实际流量记为fij图中规定一个发点s，一个收点t节点没有容量限制，流在节点不会存储容量限制条件：0

fij

cij平衡条件：

满足上述条件的网路流称为可行流，总存在最大可行流当支路上fij=cij，称为饱和弧最大流问题也是一个线性规划问题viA(vi)B(vi)链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。前向弧：与链的方向相同的弧称为前向弧。后向弧：与链的方向相反的弧称为后向弧。增广链:

设f

是一个可行流，如果存在一条从vs到vt的链，满足：1.所有前向弧上fij<Cij2.所有后向弧上fij>0则该链称为增广链①②③④⑤⑥前向弧后向弧容量流量这是一条增广链84469（5）(2)(3)(4)(6)

前向弧、后向弧示例423561fvc24=5c52=3c23=6c13=6c34=7c53=5c45=4c46=15c56=6c12=124323161361fij21fij=12cij=1221fij=4cij=12饱和弧、不饱和弧、流量的间隙

（1，2）是饱和的2、如果fij<cij，边从i到j的方向是不饱和的；（1，2）是不饱和的间隙为θ12=c12-f12=12-4=81、如果fij=cij，边从i到j的方向是饱和的；对于前向弧来讲：53fij=0cij=553fij=5cij=53、如果fij=0，边从j到i的方向是饱和的；（5，3）是饱和的4、如果fij>0，边从j到i的方向是不饱和的；（5，3）是不饱和的间隙为θ53=f53=5对于后向弧来讲(正向为3-5）饱和弧、不饱和弧、流量的间隙7.4.2确定网路最大流的标号法从任一个初始可行流出发，如0流基本算法：找一条从s

到t

点的增广链(augmentingpath)若在当前可行流下找不到增广链，则已得到最大流增广链中与s

到t方向一致的弧称为前向弧，反之后向弧

增广过程：前向弧f

ij=fij+q,后向弧f

ij=fij

q

增广后仍是可行流

最大流最小截量的标号法步骤第一步：标号过程，找一条增广链1、给源点s

标号[s+,q(s)=]，表示从s点有无限流出潜力2、找出与已标号节点i

相邻的所有未标号节点j，若(1)(i,j)是前向弧且饱和，则节点

j

不标号；(2)(i,j)是前向弧且未饱和，则节点

j

标号为[i+,q(j)]，表示从节点i

正向流出，可增广q(j)=min[q(i),cij

fij]；(3)(j,i)是后向弧，若fji=0，则节点j

不标号；(4)(j,i)是后向弧，若fji>0，则节点j

标号为[i

,q(j)]，表示从节点j

流向

i，可增广q(j)=min[q(i),fji]；3、重复步骤2，可能出现两种情况：(1)节点t

尚未标号，但无法继续标记，说明网路中已不存在增广链，当前流v(f)就是最大流；所有获标号的节点在V

中，未获标号节点在V

中，V与V

间的弧即为最小截量集；算法结束(2)节点t

获得标号，找到一条增广链，由节点t

标号回溯可找出该增广链；到第二步

最大流最小截量的标号法步骤第二步：增广过程1、对增广链中的前向弧，令f=f+q(t)，q(t)为节点t

的标记值2、对增广链中的后向弧，令f=f

q(t)3、非增广链上的所有支路流量保持不变第三步：抹除图上所有标号，回到第一步以上算法是按广探法描述的，但在实际图上作业时，按深探法进行更快捷一次只找一条增广链，增广一次换一张图最后一次用广探法，以便找出最小截量集最大流最小截量集的标号法举例(s+,)(s+,6)(2

,6)(3+,1)(4+,1)(s+,)(s+,5)(2+,2)(5

,2)(4+,2)(s+,)(s+,3)(2

,3)最小截量集ExampleFordFulkersonMethod10000s42t

110010000010010000s42t

1100100000100111XXX10010s42t

1100100110100101XXX200iterationspossible.FordFulkersonMethodEdmonds-Karpalgorithm10000s42t

110010000010010000s42t

1100100000100100XX1001001000s42t

110010000100100Edmonds-Karpalgorithm1001000s42t

110010000100100X100X1002iterations

Ford-Fulkerson算法

运筹学华东交通大学工业工程与物流管理系s2345t

10

10

9

8

4

10

10

6

200000000G:Flowvalue=00flowcapacitys2345t

10

10

9

8

4

10

10

6

200000000G:s2345t

10

9

4

10

6

2Gf:10

8

10888XXX0Flowvalue=0capacityresidualcapacityflows2345t

10

10

9

8

4

10

10

6

2800008800G:s2345t

10

4

10

6Gf:

8

8

8

9

22

210210XXX2XFlowvalue=80s2345t

10

10

9

8

4

10

10

6

21000021082G:s2345t

4

2Gf:

10

8102

107

10

6X666XX8XFlowvalue=10s2345t

10

10

9

8

4

10

10

6

21006681082G:s2345t1

6Gf:

10

8

10866

6

4

4

4

2X828XX0XFlowvalue=16s2345t

10

10

9

8

4

10

10

6

21028881080G:s2345t

6

2Gf:

10

1086

88

2

21

2

8

2X979XX9XX3Flowvalue=18s2345t

10

10

9

8

4

10

10

6

21039991070G:s2345t

19

1

1

6

2Gf:

10

7

106

99

3

1Flowvalue=19s2345t

10

10

9

8

4

10

10

6

21039991070G:s2345t9

1

1

6

2Gf:

10

7

106

99

3

1Flowvalue=19Cutcapacity=19

1定义：把网路分割为两个成分的弧的最小集合，其中一个成分包含s

点，另一个包含t

点。一般包含s

点的成分中的节点集合用V表示，包含t

点的成分中的节点集合用V表示截量集容量是指截量集中正向弧的容量之和

福特-富克森定理：网路的最大流等于最小截量集容量①②③④⑤⑥68441226796401322106如下图所示的截集为上图所示的截集为所有截量中此截量最小且等于最大流量，此截集称为最小截集。7.5最小费用最大流问题

在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。

我们首先考察，在一个网络D中，当沿可行流f的一条增广链μ，以调整量θ=1改进f，得到的新可行流f'的流量，有v(f`)==v(f)+1，而此时总费用b(f`

)比b(f)增加了

设一个网络D=（V，A，C），对于每一个弧(vi,vj)∈A,给定一个单位流量的费用bij

0，网络系统的最小费用最大流问题，是指要寻求一个最大流f，并且流的总费用达到最小。结论：如果可行流f

在流量为v(f)的所有可行流中的费用最小，并且是关于f的所有增广链中的费用最小的增广链，那么沿增广链我们将叫做这条增广链的费用。μ调整可行流f，得到的新可行流f，

，也是流量为v(f’)的所有可行流中的最小费用流。依次类推，当f，是最大流时，就是所要求的最小费用最大流。

显然，零流f={0}是流量为0的最小费用流。一般地，寻求最小费用流，总可以从零流f={0}开始。下面的问题是：如果已知f是流量为v(f)的最小费用流，那么就要去寻找关于f的最小费用增广链。

对此，重新构造一个赋权有向图M(f)，其顶点是原网络D的顶点，而将D中的每一条弧(vi,vj)变成两个相反方向的弧（vi,vj）和(vj,vi)，并且定义M(f)中弧的权wij为：并且将权为+∞的弧从M(f)

中略去。

这样，在网络D中寻找关于f的最小费用增广链就等于价于在M(f)中寻求从vs到vt

的最短路。

算法开始，取零流f(0)

={0}.一般地，如果在第K-1步得到最小费用流f

(K-1),则构造图M(f(k-1))。在图M(f(k-1))中，寻求从vs到vt的最短路。如果存在最短路，则f(k-1)就是最小费用最大流。如果存在最短路，则在原网络D中得到相对应（一一对应）的增广链μ0

在增广链μ上对f(k–1)进行调整，取调整量令：得到一个新的可行流f(k)，在对f(k)重复以上的步骤，直到D中找不到相对应的增广链时为止。

例求图6.5.1所示网络中的最小费用最大流，弧旁的权是（bij,cij）.(bij,cij)(1,8)(3,10)(2,4)(6,2)(1,7)(4,10)(2,5)v1v2vsv3vt图6.5.1

解：（1）取初始可行流为零流f(0)={0},构造赋权有向图M(f(0)),求出从vs到vt的最短路(vs,v2,v1,vt),如图5.5.1

a

中双箭头所示。(1)(3)(2)(6)(1)(4)(2)M(f(0))v1vsv2v3vt图6.5.1a

（2）在原网络D中，与这条最短路相对应的增广链为μ=（vs

,v2

,v1

,vt）。（3）在μ上对f(0)={0}进行调整，取θ=5，得到新可行流f(1)，如图5.5.1b所示。按照以上的算法，依次类推，可以得到f(1)，f(2)，f(3)，f(4)，流量分别为5，7，10，11，并且分别构造相对应的赋权有向图M(f(1)),M(f(2)),M(f(3)),M(f(4))。由于在M(f(4))中已经不存在从vs到vt的最短路，因此，可行流f(4)，v(f(1))=11是最小费用最大流。(8,5)(10,0)(4,0)(2,0)(7,5)(10,0)(5,5)图6.5.1bf(1),v(f(1))=5v1vsv2v2vtM(f(1))图6.5.1cv1(2)(-1)v3(1)(3)(6)(1)(4)(-2)(-1)vsv2vt(2,0)(5,5)(8,5)(4,0)(7,7)(10,2)(10,0)图6.5.1df(2),v(f(2))=7v1vsv2v3vtM(f(2)

)图6.5.1e(1)(3)(2)(6)(-1)(4)(-2)(-1)(-4)v1vsv3vtv2(8,8)(10,3)(4,3)(2,0)(7,7)(10,2)(5,5)图6.5.1ff(3),v(f(3))=10v1vsv2v3vt(-1)(3)(2)(6)(-1)(4)(-2)(-4)M(f(3))图6.5.1g(-2)(-3)v1vsv2v3vt(8,8)(10,4)(4,4)(2,0)(7,7)(10,3)(5,4)图6.5.1hf(4),v(f(4))=11v1vsv2v3vt(-1)(3)(-2)(6)(-1)(4)(2)(-4)M(f(4)

)图6.5.1i(-2)(-3)v1vsv2v3vtApplicationsofNetworkOptimization网络最优化模型的应