图论及网络流

1、 图的基本概念与基本定理 树和最小支撑树 最短路问题 网络系统最大流问题 网络系统的最小费用最大流问题 中国邮递员问题本章内容重点引引 言言 图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。引引 言言 随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问

2、题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。引引 言言 1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如图8.1a所示。引引 言言AB图8.1 aCD引引 言言 当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。 为了寻找答案，1736年欧拉将这个问题抽象成图8.1b所示图形的一笔画问题。即能否从某一点开始

3、不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。引引 言言图8.1 bACDB 在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。 例8.1:图8.2是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。1.1.图的基本概念与基本定理图的基本概念与基本定理1.1.图的基本概念与基本定理图的基本概念与基本定理太原重庆武汉南京徐州

4、连云港上海郑州石家庄塘沽青岛济南天津北京图8.2 例8.2:有六支球队进行足球比赛，我们分别用点v1v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用图8.3所示的有向图反映出来。1.1.图的基本概念与基本定理图的基本概念与基本定理1.1.图的基本概念与基本定理图的基本概念与基本定理v3v1v2v4v6v5图8.3 从以上的几个例子可以看出，我们用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。一般来说，通常用点表示研究对象用点与点之间的线表示研究对象之间的特定关系。由

5、于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。1.1.图的基本概念与基本定理图的基本概念与基本定理 综上所述，图论中的图是由点和点与点之间的线所组成的。通常，我们把点与点之间不带箭头的线叫做边，带箭头的线叫做弧。 如果一个图是由点和边所构成的，那么，称为为无向图，记作G =(V，E)，其中V表示图G的点集合，E表示图G的边集合。连接点vi,vjV的边记作vi,vj，或者vj,vi。 如果一个图是由点和弧所构成的，那么称为它为有向图，记作D =(V,A)，其中V 表示有向图D的点集合，A表示

6、有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。1.1.图的基本概念与基本定理图的基本概念与基本定理例如.图8.4是一个无向图G=（V，E）其中V=v1,v2,v3,v4 E=v1,v2,v2,v1,v2,v3, v3,v4,v1,v4,v2,v4, v3,v31.1.图的基本概念与基本定理图的基本概念与基本定理v3v2v1v4图8.4图8.5是一个有向图D=（V，A）其中V=v1,v2,v3,v4,v5,v6,v7 A=(v1,v2),(v,v3),(v3,v2), (v3,v4),(v2,v4),(v4,v5), (v4,v6),(v,v3),(v5,v4), (v5,v

7、6),(v6,v7)1.1.图的基本概念与基本定理图的基本概念与基本定理v7v5v3v4v2v1v6图8.5 下面介绍一些常用的名词： 一个图G或有向图D中的点数,记作P(G)或P(D),简记作P,边数或者弧数,记作q(G)或者q(D),简记作q。 如果边vi,vjE,那么称vi,vj是边的端点，或者vi,vj是相邻的。如果一个图G中，一条边的两个端点是相同的,那么称为这条边是环，如图8.4中的边v,v3是环。如果两个端点之间有两个端点之间有两条以上的边，那么称为它们为多重边，如图8.4中的边v1,v2 ,v2,v1。一个无环，无多重边的图标为简单图，一个无环，有多重边的图标图称为多重图。1.

8、1.图的基本概念与基本定理图的基本概念与基本定理 以点v为端点的边的个数称为点v的度，记作d(v),如图84中d(v1)=3， d(v2)=4,d(v3)=4,d(v4)=3。 度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。1.1.图的基本概念与基本定理图的基本概念与基本定理端点的度 d(v)：点 v 作为边端点的个数；奇点：d(v)=奇数； 偶点：d(v)=偶数；悬挂点：d(v)=1；悬挂边：与悬挂点连接的边；孤立点：d(v)=0；空图：E = ，无边图1.1.图的基本概念与基本定理图的基本概念与基本定理 定理8.1 所有顶点次

9、数之和等于所有边数的2倍。 定理8.2 在任一图中，奇点的个数必为偶数。 1.1.图的基本概念与基本定理图的基本概念与基本定理 图的连通性： 链： 由两两相邻的点及其相关联的边构成的点边序列;如: v0 ,e1 ,v1 ,e2 ,v2 ，e3 ,v3 ,vn-1, en , vn ; v0 ，vn分别为链的起点和终点； 简单链：链中所含的边均不相同； 初等链：链中所含的点均不相同,也称通路；1.1.图的基本概念与基本定理图的基本概念与基本定理圈： 除起点和终点外链中所含的点 均不相同的闭链；回路： 若 v0 vn 分称该链为开链， 否则称为闭链或回路；连通图：图中任意两点之间均至少有一 条通路

10、，否则称作不连通图。1.1.图的基本概念与基本定理图的基本概念与基本定理 子图 设 G1= V1 , E1 ,G2= V2 ,E2 子图定义：如果 V2 V1 , E2 E1 称 G2 是 G1 的子图； 真子图：如果 V2 V1 , E2 E1 称 G2 是 G1 的真子图； 部分图（支撑子图）：如果 V2 = V1 , E2 E1 称 G2 是 G1 的部分图； 导出子图： 如果V2 V1, E2=vi,vjvi,vjV2,称 G2 是 G1 中由V2 导出的导出子图。1.1.图的基本概念与基本定理图的基本概念与基本定理G G1 11.1.图的基本概念与基本定理图的基本概念与基本定理G G

11、1 1= = V V1 1 , E , E1 1 G G2 2真子图真子图G G2 2真子图真子图1.1.图的基本概念与基本定理图的基本概念与基本定理G G2 2= = V V2 2 ,E ,E2 2 子图、真子图G G3 3子图子图部分图部分图（支撑子图）（支撑子图）1.1.图的基本概念与基本定理图的基本概念与基本定理部分图：V3 = V1 , E3 E1 称 G3 是 G1 的部分图；G G4 4导出子图导出子图G G4 4导出子图导出子图1.1.图的基本概念与基本定理图的基本概念与基本定理导出子图：V4 V1,E4=vi,vjvi,vjV4,称 G4 是 G1 中由V4 导出的导出子图。

12、 G G5 5生成树生成树（部分图）（部分图）1.1.图的基本概念与基本定理图的基本概念与基本定理 G G6 6G G5 5余树余树（部分图）（部分图）1.1.图的基本概念与基本定理图的基本概念与基本定理有向图：关联边有方向弧：有向图的边a=(u ,v),起点u,终点v；路：若有从 u 到 v 不考虑方向的链,且 各方向一致,则称之为从u到v的路；初等路: 各顶点都不相同的路； 初等回路:u = v 的初等 路; 连通图： 若不考虑方向 是无向连通图; 强连通图：任两点有路;1.1.图的基本概念与基本定理图的基本概念与基本定理2.2.树和最小支撑树树和最小支撑树 一、树及其性质 在各种各样的图

13、中，有一类图是十分简单又非常具有应用价值的图，这就是树。 例8.3：已知有六个城市，它们之间 要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。2.2.树和最小支撑树树和最小支撑树 如果用六个点v1v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。由于任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图8.8是一个不含圈的连通图，代表了一个电话线网。2.2.树和最小支撑树树和最小支撑树图8.8v6v3v4v2v5v12

14、.2.树和最小支撑树和最小支撑树树 定义8.1 一个无圈的连通图叫做树。 下面介绍树的一些重要性质： 定理8.3 设图G=（V，E）是一个树P(G) 2，那么图G中至少有两个悬挂点。 定理8.4 图G=（V，E）是一个树的充要条件是G不含圈，并且有且仅有P-1条边。 定理8.5 图G=（V，E）是一个树的充要条件是G是连通图，并且有且仅有P-1条边。 定理8.6 图G是一个树的充分必要条件是任意两个顶点之间有且仅有一条链。2.2.树和最小支撑树树和最小支撑树 从以上定理，不难得出以下结论： （1）从一个树中任意去掉一条边，那么剩下的图不是连通图，亦即，在点集合相同的图中，树是含边数最少的连通图

15、。 （2）在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。2.2.树和最小支撑树树和最小支撑树 二.支撑树 定义8.2 设图K=(V,E)是图G=(V,E)的一支撑子图,如果图K=(V,E)是一个树,那么称K是G的一个支撑树。 例如,图8.10b 是图8.10a 的一个支撑树。 v6v5v2v3v4v1v6v5v2v3v4v1图8.10ab2.2.树和最小支撑树树和最小支撑树 显然,如果图K=( V, E )是图G=(V, E)的一个支撑树,那么K 的边数是p(G)-1，G中不属于支撑树K的边数是q(G)-p(G)+1。 定理8.7 一个图G有支撑树的充要条件是G是连通图。2.2.树和

16、最小支撑树树和最小支撑树证明证明: : 必要性显然； 充分性: 设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个支撑树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图G的一支撑子图G1。若G1不含圈，则G1是G的一个支撑树。若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图G的一支撑子图G2。依此类推，可以得到图G的一个支撑子图GK，且不含圈，从而GK是一个支撑树。2.2.树和最小支撑树树和最小支撑树 定理8.7充分性的证明，提供了一个寻找连通图支撑树的方法叫做“破圈法”。就是从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时

17、为止，这样就得到一个支撑树。 例8.4:用破圈法求出图8-11的一个支撑树。V5V4V2V3V1e6e5e4e3e2e1e7e82.2.树和最小支撑树树和最小支撑树 取一个圈(v1,v2,v3,v1)，在一个圈中去 掉边e3 。在剩下的图中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4 。再从圈（v3,v4 v5,v3）中去掉边e6 。再从圈 (v1,v2,v5,v4,v3,v1 ）中去掉边e7， 这样，剩下的图不含圈，于是得到一个 支撑树，如图8.12所示。v2e1e2e5e8v1v3v42.2.树和最小支撑树树和最小支撑树 三.最小支撑树问题 定义8.3 如果图G =（V，E），

18、对于G中的每一条边vi,vj，相应地有一个数Wij，那么称这样的图G为赋权图，Wij称为边vi,vj的权。这里所指的权，是具有广义的数量值。根据实际研究问题的不同，可以具有不同的含义。例如长度，费用、流量等等。 赋权图在图论及实际应用方面有着重要的地位，被广泛应用于现代科学管理和工程技术等领域，最小支撑树问题就是赋权图的最优化问题之一。2.2.树和最小支撑树树和最小支撑树 定义8.4 如果图T =（V，E）是图G 的一个支撑树，那么称E上所有边的权的和为支撑树T 的权，记作S(T)。 如果图G 的支撑树T* 的权S(T*)，在G 的所有支撑树T 中的权最小，即S(T*) = minS(T)，那

19、么称T*是G 的最小支撑树。 如前所述，在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，一个问题的 解决可以归结为最小支撑树问题。 再如，城市间交通线的建造等，都可以归结为这一类问题。2.2.树和最小支撑树树和最小支撑树常用的有破圈法和生长法（避圈法）两个方法： 在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树； 去掉该圈中权数最大的边； 反复重复 两步，直到最短树。2.2.树和最小支撑树树和最小支撑树例8.5 某六个城市之间的道路网如图8.13a所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。2.2.树和最小支撑树树和最小支撑

20、树v6v5v2v3v4图8.13av162753544v3v2v1v4v6v5513142图8.13b2.2.树和最小支撑树树和最小支撑树 解：这个问题的解决就是要求所示赋权图8.13a中的最小支撑树。用破圈法求解。任取一个圈，例如（ v1,v2,v3,v1 ），去掉这个圈中权最大的边v1,v3。再取一个圈（ v3,v5,v2,v3），去掉边v2,v5。再取一个圈（ v3,v5,v4,v2,v3），去掉边v3,v5。再取一个圈（v5,v6,v4,v5），这个圈中，有两条权最大的边v5,v6和v4,v6。任意去掉其中的一条，例如v5,v6。这时得到一个不含圈的图，如图8.13b所示，即是最小支撑

21、树。2.2.树和最小支撑树树和最小支撑树 从网络图中依次寻找权数较小的边，寻找过程中，节点不得重复，即不得构成圈。注意在找较小权数边时不考虑已选过的边和可能造成圈的边。如此反复进行，直到得到最短树或证明网络不存在最短树。2.2.树和最小支撑树树和最小支撑树再用“生长法”求解例8.5解：考虑赋权图8.13a，用生长法求解。任取一点，例如 从v1 取权较小的边（v1 ,v2 ）， 再从v2 取权较小的边（v2 ,v3 ）， 再从v3 取权较小的边（v3 ,v4 ）， 同理依次取（v4 ,v5）， （v4 ,v6 ）。这时也得到了如图8.13b所示的最小支撑树。3.3.最短路径问题最短路径问题一.引

22、言 最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。也可以用于解决其它的最优化问题。 3.3.最短路径问题最短路径问题例86: 如图8.14所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从v1出发，经过这个交通网到达v8，要寻求是总路程最短的线路。图8.14v1v4v2v8v7v6v5v96362341023126241013.3.最短路径问题最短路径问题 从v1到v8的路线是很多的。比如从v1出发，经过v2,v5到达v8或者从v1出发，经过v4，v6，

23、v7到达v8等等。但不同的路线，经过的总长度是不同的。例如，按照第一个线路，总长度是6+1+6=13单位，按照第二个路线，总长度是1+10+2+4=17单位。3.3.最短路径问题最短路径问题 一般意义下的最短路问题：设一个赋权有向图D =（V，A），对于每一个弧a =（vi,vj），相应地有一个权wij。vs,vt是D中的两个顶点，P是D中从vs到vt的任意一条路，定义路的权是P 中所有弧的权的和，记作S(p)。最短路问题就是要在所有从vs到vt的路P 中，寻找一个权最小的路P0，亦即S(P0)=minS(p)。P0叫做从vs到vs的最短路。P0的权S(P0)叫做从vs到vt的距离，记作d（v

24、s，vt）。由于D是有向图，很明显d（vs，vt）与d（vt，vs）一般不相等。3.3.最短路径问题最短路径问题 二.Dijkstra算法 下面介绍在一个赋权有向图中寻求最短路的方法Dijkstra算法，它是在1959年提出来的。目前公认，在所有的权wij 0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj的最短路。3.3.最短路径问题最短路径问题Dijkstra算法的基本思想是从vs出发，逐步向外寻找最短路。在运算过程中，与每个点对应，记录一个数，叫做一个点的标号。它或者表示从vs到该点的最短路权（叫做P 标号），或者表示从vs到该点最

25、短路权的上界（叫做T 标号）。算法的每一步是去修改T 标号，把某一个具有T 标号的点改变为具有P 标号的点，使图D 中具有P 标号的顶点多一个。这样，至多经过P -1步，就可求出从vs到各点vj的最短路。 3.3.最短路径问题最短路径问题 以例1为例说明这个基本思想。在例1中，S=1。因为Wij 0，d（v1,v1）=0。这时，v1是具有P标号的点。现在看从v1出发的三条弧（v1,v2），（v1,v3）和（v1,v4）。如果一个人从v1出发沿（v1,v2）到达v2，这时的路程是d（v1,v1）+w12=6单位。如果从v1出发，沿（v1,v3）到达v3，则是d（v1,v1）+w13=3单位。同理

26、，沿（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单位。例1说明： 看从v1出发的三条弧（v1,v2），（v1,v3）和（v1,v4），mind(v1,v1)+w12 ,d(v1,v1)+w13 , d(v1,v1)+w14 = d（v1,v4）=1。P(V4)v2v8v7v6v5v963623410231262410P(V1)13.3.最短路径问题最短路径问题

27、 由于所有的权wij 0，因此，不论他如何再从v2或者v3到达v4，所经过的总路程都不会比1少，于是就有d（v1,v4）=1。这样就使V4变成具有P标号的点。现在看从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）=3。这样，

28、又使点v3变为具有P 标号的点，不断重复以上过程，就可以求出从vs到达任一点vj的最短路。例1说明： 再看从v1和v4指向其余点的弧, mind（v1,v1）+w12，d（v1,v1）+w13，d（v1,v4）+w46=d（v1,v1）+w13=3 。P(V4)v2v8v7v6v5v963623410231262410P(V1)P(V3)13.3.最短路径问题最短路径问题 在下述的Dijkstra算法中，以P，T 分别表示某一个点的P 标号，T 标号。Si表示在第i步时，具有P 标号点的集合，为了在算出从vs到各点的距离的同时，也找出从vs到各点的最短路，于是，给每一个点v一个值。当算法结束时

29、，如果(v)= m，则表示在从vs到v 的最短路上，v 的前一个点是vm。如果(v)=M，则表示在图D 中不含有从vs 到达v 的路。(v)=0，表示v=vs。 Dijkstra算法的步骤如下：3.3.最短路径问题最短路径问题 开始（开始（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； （1 1）如果如果S Si i= =V V，则算法结束，对每一个，则算法结束，对每一个v S Si i，d d（vs

30、,v）= =P P（v）。否则转入）。否则转入（2 2）；）； （2 2）考察每一个使（考察每一个使（v vi i,v,vj j） A A，且，且v vj j不不属于属于S Si i的点的点v vj j，如果，如果T T( (v vj j)P(vP(vk k)+)+w wkjkj ，则把则把T T(v(vj j) )改变为改变为P P( (v vk k)+)+w wkjkj，把，把( (v vj j) )改改变为变为k k，否则转入（，否则转入（3 3）；）；3.3.最短路径问题最短路径问题 （3）令(vji)=minT(vj)vjSi，如果T(vji)+，则把vji的T 标号改变为P 标号P

31、(vji)=T(vji)，令Si+1=Sivji，k=ji，把i换成i+1，转入（1）；否则结束。 这时，对每一个vSi，d(vs,v)=P(v)。对每一个v不属于Si，d（vs,v）=T（v）。3.3.最短路径问题最短路径问题 现在用Dijkstra算法求例1中从vs到各个 点 的 最 短 路 ， 此 时S= 1 .i= 0 ：S0=v1,P(v1)=0,(v1)=0,T(vi)=+, (vi)=m,i=2,3,9,k=1。 （2）因为（v1,v2）A，v2不属于S0，P(v1)+w12w32+P(v3)，将T(v2)改变为 P(v3)+w32=5，(v2)改变为3。 （3）在所有的T标号中

32、，T(v2)=5最小， 于 是令P(v2)=5，S3=v1,v4,v3，k=2。 i=3： （2）将T(v5)改变为P(v2)+w25=6，(v5) 改变为2。 （3）在所有的T标号中，T(v5)=6最小，于 是令P(v5)=6，S4=v1,v4,v3，k=5。 i=4:3.3.最短路径问题最短路径问题 （2）将T(v6)，T(v7)，T(v8)分别改变为10， 9，12，将(v0)，(v7)，(v8)改变为5。 （3）在所有的T标号中，T(v7)=9最小，于 是令P(v7)=9，S5=v1,v4,v3,v2,v5,v7，v=7。 i=5： （2）（v7,v8）A，v8不属于S5， 但T(v8

33、)=0,只要将Dijkstra算法中的“（2）看作每一个使（vk,vj）A，且vjSj的点vj”改变为“（2）看作每一个使vk,vjE，且vjSj的点vj”而其他的条件不变，同样可以求出从vs到各点的最短路（对于无向图叫做最短链）。 作为习题，将例8.6中所示的赋权有向图的箭头去掉，然后求出无向图中从vs到各点的最短路。3.3.最短路径问题最短路径问题 下面证明Dijkstra算法的正确性。只要证明每一个点vSi,P()是从vs到v的最短路权，即P()=d(vs.v). 证:用数学归纳法。当i=0时，结论显然成立。假设i=n时，结论成立。看i=n+1的情形，由于Sn+1=Snvjn,所以只要证

34、明P(vjn)=d(vs,vj)根据算法，vj m是最具有最小T标号的点，即Tn(vjn)=minTn(vj)，其中vjSm.这里，用Tn()表示当i=n时，执行步骤（3）时点的T标号。设H是图D中任意一条从vs到vjn的路。 3.3.最短路径问题最短路径问题 因为vsSn,而vjn Sn,所以从vs出发，沿H必存在一条弧，其始点属于Sn，而终点不属于Sn。令 （vr, vl） 是 第 一 条 这 样 的 弧 ， 于 是H= (vsvr, vlvj n) ,s(H) =S( (vs, vr)+wrl+S(vlvjn)。由归纳假设，P(vr)是从v s到v r的 最 短 路 权 ， 于 是 ，

35、有S（H）=P(vr)+wrl+S(vlvjn).根据算法中的T标号修改规则，因为vrSn,vl Sn,故P（vr）+wrl=Tn(vjn),且S（vlvjn）=所以S（H）=Tn(vjn)+S(vl,vjn)=Tn(vjn).这样，就证明了Tn(vjn)是从vs到vjn的最短权。根据算法，P(vjn)=Tn(vjn),于是就有P(vjn)=d(vs,vjn).3.3.最短路径问题最短路径问题 Dijkstra算法仅适合于所有的权wij=0的情形。如果当赋权有向图中存在有负权弧时，则该算法失效。例如图8.16中，根据Dijkstra算法，可以得出从v1到v2最短路权是2，但是这显然不对，因为从

36、v1到v2的最短路是（v1,v3,v2）,权是-1。v1v3v222-3图8.163.3.最短路径问题最短路径问题 下面介绍当赋权有向图中，存在负权弧时，寻求最短路的方法: 首先，设从任一点首先，设从任一点v vi i到任一点到任一点v vj j都有一条弧，如果在图都有一条弧，如果在图 D D 中，（中，（v vi i,v,vj j）不属于）不属于A A, ,则添加弧则添加弧( (v vi i,v,vj j),),并且令并且令w wijij=+.=+. 很明显，从vs到vj的最短路是从vs点出发，沿着这条路到某个点vi的再沿弧(vi,vj)到点vj。显然，从vs到vi的这条路必定是从vs到vi

37、的最短路。否则从vs到vj的这条路将不是最短路。于是，从从v vs s到到v vj j的距离的距离d d( (v vs s,v,vj j) )满足以下条件满足以下条件， d(vs,vj)=mind(vs,vi)+wij, i i=1,p, p=p(D). 3.3.最短路径问题最短路径问题 这个关系式的解这个关系式的解d d( (v vs s,v,v1 1) )d d( (v vs s,v,vp p).).可利用如可利用如下的下的 递推公式递推公式 求解求解 d d(1)(1)( (v vs s,v,vj j)=)=w wsjsj, ,j j=1=1p.p. d d(t)(t)( (v vs s

38、,v,vj j)=min)=mind d(t-1)(t-1)( (v vs s,v,vi i)+ )+ w wijij, , t t=2,3=2,3 i i 当计算到第当计算到第K K步时步时, ,对一切的对一切的j j=1=1p p, ,有有 d d(k)(k)( (v vs s,v,vj j)=)=d d(k-1)(k-1)( (v vs s,v,vj j) ) 则则d d(k)(k)( (v vs s,v,vj j),),j j=1=1p p, ,就是从就是从v vs s到各点到各点v vj j的的最短路径的权最短路径的权。 设C是赋权函数有向图D中的一个回路。如果回路C的权S（C）是负

39、数那么称C是D中的一个负回路。 可以证明以下的结论： 1.如果赋权有向图D不含有负回路，那么从vs到任一点的最短路至多包含P-2个中间点，并且必可取为初等路。 2.如果赋权有向图D不含有负回路，那么上述递推算法至多经过P-1次迭代必收敛，可以求出从vs到各个点的最短路权。 3.如果上述算法经过P-1次迭代，还存在在着某个j，使得d(p)(vs,vj)d(p-1)(vs,vj),那么D中含有负回路。这时，不存在从vs到vj的路（权无界）。结论3.3.最短路径问题最短路径问题例例8 87: 7: 在如图在如图8.178.17所示的赋权有向图中求所示的赋权有向图中求从从v v1 1到各点的最短路。到

40、各点的最短路。 解解: :利用上述递推公式，将求解结果列出利用上述递推公式，将求解结果列出如表如表8.188.18所示。所示。 可以看出，当可以看出，当t t=4=4时，有时，有 d d(t)(t)( (v vs s,v,vj j)=)=d d(t-1)(t-1)( (v vs s,v,vj j) ) j j=1=18.8.因此，表因此，表中的最后一列，就是从中的最后一列，就是从v v1 1到到v v1 1,v,v2,.,2,.,v v8 8的最的最短路权短路权。3.3.最短路径问题最短路径问题v8v2v4v7v5v1v3v6图8.1711111123355223678终点 起点V1V2V3V

41、4V5V6V7V8t=1t=2t=3t=4V10-1-23 0000V2602-1-5-5-5V3 -30-51-2-2-2-2V4802 3-7-7-7V5 -101-3-3V61017-1-1-1V7-105-5-5V8-3-5066wij d(t)(vs,vj) 3.3.最短路径问题最短路径问题 为了求出从v1到各个点的最短路，一般采用反向追踪的方法：如果已知d(vi,vj),那么寻求一个点vk,使得d(vs,vk)+wkj=d(vs,vj),然后记录下(vk,vj).在看d(vs,vk),寻求一个点vi,使得d(vs,vi)+wij=d(vs,vk)依次类推，一直到达为止。这样，从vs

42、到vj的最短路是（vs,vi,vk,vj） 在本例中，有表8.18知，d(v1,v8)=6,由于)d(v1,v6)+w6 8=(-1)+7记录下v6.由于d(v1,v3)+w3 6=d(v1,v6),j记录下v3.由于d(v1,v1)+w13=d(v1,v3),于是，从v1到v8的最短路是(v1,v3,v6,v8)。 1.狄克斯拉方法 适用于满足所有权系数大于等于0（lij0）的网络最短路问题，能求出起点 v1 到所有其他点 vj 的最短距离； 2.海斯方法 基本思想是在最短路线上任意两点间路线也是最短路线。利用 vi 到vj 的一步距离求出 vi 到 vj 的两步距离再求出 vi 到 vj

43、的四步距离经有限次迭代可求出 vi 到vj 的最短距离；3.3.最短路径问题最短路径问题 3.福德方法 适用于有负权系数，但无负回路的有向或无向网络的最短路问题，能求出起点 v1 到所有其它点 vj 的最短距离。 4 .4 .网络系统的最大流问题网络系统的最大流问题 一 引言 在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。4 .4 .网络系统的最大流问题网络系统的最大流问题图8.19vtv3v2v1v4vs1735108611453

44、C Cijij图图8.198.19是一个网络。每一个弧旁边的权就是对应的容量是一个网络。每一个弧旁边的权就是对应的容量（最大通过能力）（最大通过能力）。要求指定一个运输方案，使得从要求指定一个运输方案，使得从v vs s到到v vt t的货运量最大，这是寻求网络系统的最大流问题的货运量最大，这是寻求网络系统的最大流问题。 4. 4.网络系统的最大流问题网络系统的最大流问题二二 基本概念基本概念 定义定义8.5 8.5 设一个赋权有向图设一个赋权有向图D D = =（V,AV,A）, ,在在v v中指定一个中指定一个发点发点v vs s和一个和一个收点收点v vt t, ,其他的其他的点叫做中间

45、点。对于点叫做中间点。对于D D中的每一个弧（中的每一个弧（v vi i,v,vj j）A A, ,都有一个权都有一个权 c cijij 叫做叫做弧的容量弧的容量。我们把。我们把这样的图这样的图 D D 叫做一个叫做一个网络系统网络系统，简称网络，简称网络，记做记做D D = =（V V，A A，C C）。）。 网络网络D D上的流上的流，是指定义在弧集合，是指定义在弧集合A A上的一个上的一个函数函数f f=f f( (v vi i,v,vj j)=)=f fijij f f( (v vi i,v,vj j)=)=f fijij叫做叫做弧在弧在( (v vi i,v,vj j) )上的流量上

46、的流量。 4. 4.网络系统的最大流问题网络系统的最大流问题v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）f fijij图8.20网络上的一个流（运输方案）每一个弧上的流量fij就是运输量例如fs1=5,fs2=3,f13=2等等vt 4. 4.网络系统的最大流问题网络系统的最大流问题网络系统上流流的特点：(1)发点的总流出量和收点的总流入量必相等；(2)每一个中间点的流入量与流出量的代数和等于零；(3)每一个弧上的流量不能超过它的最大通过能力（即容量）。 4. 4.网络系统的最大流问题网络系统的最大流问题 定义定义8.6 8.6 网络上的一个流f叫做可行流，

47、如果f满足以下条件 （1）容量条件容量条件：对于每一个弧（vi,vj）A,有 0 0 f fijij c cijij. . （2）平衡条件平衡条件： 对于发点vs，有fsj-fjs=v(f) 对于收点vt，有ftj-fjt=-v(f) 对于中间点，有fij-fji=0 其中发点的总流量（或收点的总流量） v v( (f f) )叫做这个可行流的流量叫做这个可行流的流量。 4. 4.网络系统的最大流问题网络系统的最大流问题 任意一个网络上的可行流总是存在的。例如零流v(f)=0,就是满足以上条件的可行流。 网络系统中最大流问题就是在给定的网络上寻求一个可行流f,其流量v(f)达到最大值。 设流f

48、=fij是网络D上的一个可行流。我们把D中fij=cij的弧叫做饱和弧饱和弧，fij0的弧为非零流非零流弧弧，fij=0的弧叫做零流弧零流弧。 4. 4.网络系统的最大流问题网络系统的最大流问题 设是网络D中连接发点s和收点vt的一条链。定义链的方向是从vs到vt，于是链上的弧被分为两类：一是弧的方向与链的方向相同，叫做前向弧，前向弧的集合记做+。二是弧的方向与链的方向相反，叫做后向弧，后向弧的集合记做-。在下图（图8.19与8.20合并图）中，(v4,v3)是饱和弧，其他的弧是非饱和弧，并且都是非零流弧。v3v2v1v4vs（17,2）（3,3）（5,2）（10,5）（8,3）（6,3）（1

49、1,6）（4,1）（5,1）（3,2）f fijij如图，在链（v vs s,v,v1 1,v,v2 2,v,v3 3,v,v4 4,v,vt t) )中， + +=(=(v vs s,v,v1 1),(),(v v1 1,v,v2 2),(),(v v2 2,v,v3 3),(),(v v4 4,v,vt t),), - -=(=(v v4 4,v,v3 3).).vt 4. 4.网络系统的最大流问题网络系统的最大流问题增广链增广链，如果链满足以下条件： 1在弧（vi,vj）+上，有0=fijcij,即+中的每一条弧是非饱和弧。 2在弧（vi,vj）-上，有0fij=cij,即-中的每一条弧

50、是非零流弧。 例如在图8.20中，链=（vs,v1,v2,v3,v4,vt）就是一条增广链。 设图D=(V，A，C)，点集S,TV,ST=中。将起点在S，终点在T 的所有弧作成集合，记做（S，T）。 4. 4.网络系统的最大流问题网络系统的最大流问题 定义8.8 设一个网络D=（V，A，C）。如果点集V被剖分为两个非空集合V1和V1，发点vsV1,收点vtV1,那么将弧集（V1,V1）叫做是分离vs和vt的截集。 定义8.9 设一个截集（V1, V1）.将截集（V1,V1）中所有的弧的容量的和叫做截集的截量，记做s(V1,V1),亦即s(V1,V1)=cij。 (vi,vj)(V1,V1) 4

51、. 4.网络系统的最大流问题网络系统的最大流问题 下面的事实是显然的：一个网络D中，任何一个可行流f的流量v(f)都小于或等于这个网络中任何一个截集(V1,V1)的截量。并且，如果网络上的一个可行流f*和网络中的一个截集（V1*,V1*），满足条件v*(f*)=c(V1*,V1*),那么f*一定是D上的最大流，而（V1*,V1*）一定是D的所有的截集中截量最小的一个（即最小截集）。 4. 4.网络系统的最大流问题网络系统的最大流问题 定理8.8网络中的一个可行流f*是最大流的充分必要条件是，不存在关于f*的增广链。 定理8.9在一个网络D中，最大流的流量等于分离vs和vt的最小截集的截量。 定

52、理定理8.88.8实际上提供了一个寻求网络系统最实际上提供了一个寻求网络系统最大流的方法：如果网络大流的方法：如果网络D D中有一个可行流中有一个可行流f f，只要，只要判断网络是否存在关于可行流判断网络是否存在关于可行流f f的增广链的增广链 。如果。如果没有增广链，那么没有增广链，那么f f一定是最大流。如有增广链，一定是最大流。如有增广链，那么可以按照定理那么可以按照定理8.98.9，不断改进和增大可行流，不断改进和增大可行流f f的流量，最终可以得到网络中的一个最大流。的流量，最终可以得到网络中的一个最大流。4.4.网络系统的最大流问题网络系统的最大流问题 三标号法 从网络中的一个可行

53、流f出发（如果D中没有f，可以令f是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。 用给顶点标号的方法来定义V1*.在标号过程中，有标号的顶点是V1*中的点，没有标号的点不是V1*中的点。如果vt有了标号，表示存在一条关于f的增广链。如果标号过程无法进行下去，并且vt未被标号，则表示不存在关于f的增广链。这样，就得到了网络中的一个最大流和最小截集。 4. 4.网络系统的最大流问题网络系统的最大流问题 1 标号过程 在标号过程中，网络中的点或者是标号点（分为已检查和未检查两种）。或者是未标号点。每个标号点的标号包含两部分：第一个标号表示这个标号是从那一点得到的。以便找出

54、增广链。第二个标号是为了用来确定增广链上的调整量。 标号过程开始，先给vs标号（0，+）。这时，vs是标号未检查的点，其他都是未标号点。一般地，取一个标号未检查点vi，对一切未标号点vj： 4. 4.网络系统的最大流问题网络系统的最大流问题 1）如果在弧（vi,vj）上，fij0,那么给vj标号（-vi, l(vj)）.其中l(vj)=minl(vi),cij-fij.这时，vj成为标号未检查点。 于是vi成为标号已检查的点。重复以上步骤，如果所有的标号都已经检查过，而标号过程无法进行下去，则标号法结束。这时的可行流就是最大流。但是，如果vt被标上号，表示得到一条增广链，转入下一步调整过程。

55、2.调整过程 首先按照vt和其他的点的第一个标号，反向追踪，找出增广链。例如，令vt的第一个标号是vk，则弧（vk,vt）在上。再看vk的第一个标号，若是vi，则弧(vi,vk)都在上。依次类推，直到vs为止。这时，所找出的弧就成为网络D的一条增广链。取调整量= l(vt),即vt的第二个标号， 4. 4.网络系统的最大流问题网络系统的最大流问题 fij+，当(vi,vj)+ 令fij= fij-，当(vi,vj)- 其他不变 再去掉所有的标号，对新的可行流f=fij,重新进行标号过程，直到找到网络D的最大流为止。 4. 4.网络系统的最大流问题网络系统的最大流问题4.4.网络系统的最大流问题

56、网络系统的最大流问题V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,1）（2,2）（5,3）（1,1）（1,1）(Cij,fij)Vt图8.21 例8.8: 求图8.21的网络最大流，弧旁的权数表示（cij,fij）。 解.用标号法。 1.标号过程。 （1）首先给vs标号（0，+） （2）看vs:在弧(vs,v2)上,fs2=cs3=3,不具备标号条件。在弧(vs,v1)上,fs1=10,故给v2标号（-v1, l(v2)）,其中l(v2)=minl(v1),f21=min4,1=1. 4. 4.网络系统的最大流问题网络系统的最大流问题 （4）看v2:在弧（v2,v4）上，f

57、24=30,故给v3标号（-v2，l(v3),其中l(l(v3)=minl(v2),f32=min1,1=1。 （5）在v3,v4中任意选一个，比如v3,在弧（v3,vt）上，f3 t= 1 =0，网络系统的最小费用最大流问题，是指要寻求一个最大流f，并且流的总费用b(f)=bijfij达到最小。 （Vi,Vj）A5.5.网络系统的网络系统的 最小费用最大流问题最小费用最大流问题 在一个网络D中，当沿可行流f的一条增广链，以调整量=1改进f，得到的新可行流f的流量，有v(f)=v(f)+1，而此时总费用b(f)比b(f)增加了b(f)-b(f)=bij(fij-fij)- bij(fij-fi

58、j)= bij-bij + - + - 将bij-bij叫做这条增广链的费用。5.5.网络系统的网络系统的 最小费用最大流问题最小费用最大流问题5.5.网络系统的网络系统的 最小费用最大流问题最小费用最大流问题 如果可行流在流量为v(f)的所有可行流中的费用最小，并且是关于f的所有增广链中的费用最小的增广链。那么沿增广链调整可行流f，得到的新可行流f，也是流量为v(f)的所有可行流中的最小费用流。 依次类推，当f是最大流时，就是所要求的最小费用最大流。 显然，零流f=0是流量为0的最小费用流。一般地，寻求最小费用流，总可以从零流f=0开始。下面的问题是：如果已知f是流量为v(f)的最小费用流，

59、那么就要去寻找关于f的最小费用增广链。 对此，重新构造一个赋权有向图M(f)，其顶点是原网络D的顶点，而将D中的每一条弧(vi,vj)变成两个相反方向的弧（vi,vj）和(vj,vi)，并且定义M(f)中弧的权wij为：5.5.网络系统的网络系统的 最小费用最大流问题最小费用最大流问题 bij,当fij0wij= +,当fij=0 并且将权为+的弧从M(f)中略去。 即当 0 fij =3。 当q=3时，显然G是欧拉图。假设q=n时成立，看q=m+1的情形：由于G是无奇点的连通图，并且G的点数p=3，因此存在三个点，v,w,使得，v,w,vE。从G中去掉边，v,w,v，增加新的边，w，得到一个

60、新的多重图G1，G1有q-1条边，且仍不含奇点，G1至多有两个分图。6.6.中国邮递员问题中国邮递员问题 若G1是连通的，则由归纳假设，G1有欧拉圈C1。把C1中的边w,换成,v,w,v，即是G中的欧拉圈。若G1有两个分图G1，G1，令v在G1中。由归纳假设，G1，G1分别有欧拉圈C1，C1，把C1”中的边,w换成,v,C1及v,w即是G中的欧拉圈。 推论 一个多重连通图G有欧拉链的充分必要条件是G有且仅有两个奇点。 这个推论的证明留给读者作为习题。 从这个定理的证明可以看出，识别一个连通图能否一笔画出的条件是它是否有奇点。若有奇点，就不能一笔画出。若没有奇点，就能够一笔画出，并回到原出发地。