运筹学课件-图与网络分析

1第五章

图与网络分析

图的基本概念与基本定理

树和最小支撑树

最短路问题

网络系统最大流问题

网络系统的最小费用最大流问题中国邮递员问题本章内容重点2引言

图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。3引言

随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。4引言

1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如图8.1a所示。引言AB图8.1aCD6引言

当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉将这个问题抽象成图8.1b所示图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。7引言图8.1bACDB8

在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。

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

例8.2:有六支球队进行足球比赛，我们分别用点v1…v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用图8.3所示的有向图反映出来。1.图的基本概念与基本定理111.图的基本概念与基本定理v3v1v2v4v6v5图8.312

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

13

综上所述，图论中的图是由点和点与点之间的线所组成的。通常，我们把点与点之间不带箭头的线叫做边，带箭头的线叫做弧。如果一个图是由点和边所构成的，那么，称为为无向图，记作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)。1.图的基本概念与基本定理14例如.图8.4是一个无向图G=（V，E）其中V={v1,v2,v3,v4}

E={[v1,v2],[v2,v1],[v2,v3],[v3,v4],[v1,v4],[v2,v4],[v3,v3]}1.图的基本概念与基本定理v3v2v1v4图8.415图8.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)}1.图的基本概念与基本定理v7v5v3v4v2v1v6图8.516

下面介绍一些常用的名词：一个图G或有向图D中的点数,记作P(G)或P(D),简记作P,边数或者弧数,记作q(G)或者q(D),简记作q。如果边[vi,vj]

E,那么称vi,vj是边的端点，或者vi,vj是相邻的。如果一个图G中，一条边的两个端点是相同的,那么称为这条边是环，如图8.4中的边[v,v3]是环。如果两个端点之间有两个端点之间有两条以上的边，那么称为它们为多重边，如图8.4中的边[v1,v2],[v2,v1]。一个无环，无多重边的图标为简单图，一个无环，有多重边的图标图称为多重图。1.图的基本概念与基本定理17

以点v为端点的边的个数称为点v的次，记作d(v),如图8—4中d(v1)=3，d(v2)=4,d(v3)=4,d(v4)=3。次为零的点称为弧立点，次为1的点称为悬挂点。悬挂点的边称为悬挂边。次为奇数的点称为奇点，次为偶数的点称为偶点。1.图的基本概念与基本定理18端点的次d(v)：点v

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

，无边图，即图中所有的点都是孤立点。1.图的基本概念与基本定理

定理8.1所有顶点次数之和等于所有边数的2倍。

定理8.2在任一图中，奇点的个数必为偶数。

1.图的基本概念与基本定理20

图的连通性：

链：由两两相邻的点及其相关联的边构成的点边序列;如:v0,e1,v1,e2,v2

，e3,v3,…,vn-1,en,vn

;

v0

，vn分别为链的起点和终点；

简单链：链中所含的边均不相同；

初等链：链中所含的点均不相同,也称通路；1.图的基本概念与基本定理21圈：除起点和终点外链中所含的点均不相同的闭链；回路：若v0≠vn

分称该链为开链，否则称为闭链或回路；连通图：图中任意两点之间均至少有一条通路，否则称作不连通图。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,vj]∣vi,vj

V2},称G2

是G1

中由V2

导出的导出子图。1.图的基本概念与基本定理23G11.图的基本概念与基本定理G1=[V1,E1]24G2真子图G2真子图1.图的基本概念与基本定理G2=[V2,E2]子图、真子图25G3子图

部分图

（支撑子图）1.图的基本概念与基本定理部分图：V3

=V1,E3

E1

称G3

是G1

的部分图；26G4导出子图G4导出子图1.图的基本概念与基本定理导出子图：V4

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

V4},称G4

是G1

中由V4

导出的导出子图。27G5

生成树

（部分图）1.图的基本概念与基本定理28

G6

G5余树

（部分图）1.图的基本概念与基本定理有向图：关联边有方向弧：有向图的边a=(u,v),起点u,终点v；路：若有从u到v不考虑方向的链,且各方向一致,则称之为从u到v的路；初等路:各顶点都不相同的路；

初等回路:u=v的初等路;

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

强连通图：任两点有路;1.图的基本概念与基本定理302.树和最小支撑树

一、树及其性质在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。例8.3：已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。312.树和最小支撑树

如果用六个点v1…v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。由于任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图8.8是一个不含圈的连通图，代表了一个电话线网。322.树和最小支撑树图8.8v6v3v4v2v5v1332.树和最小支撑树

定义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是一个树的充分必要条件是任意两个顶点之间有且仅有一条链。342.树和最小支撑树

从以上定理，不难得出以下结论：（1）从一个树中任意去掉一条边，那么剩下的图不是连通图，亦即，在点集合相同的图中，树是含边数最少的连通图。（2）在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。2.树和最小支撑树

二.支撑树定义8.2设图K=(V,E’)是图G=(V,E)的一支撑子图,如果图K=(V,E’)是一个树,那么称K是G的一个支撑树。例如,图8.10b是图8.10a的一个支撑树。v6v5v2v3v4v1v6v5v2v3v4v1图8.10ab362.树和最小支撑树

显然,如果图K=(V,E’)是图G=(V,E)的一个支撑树,那么K的边数是p(G)-1，G中不属于支撑树K的边数是q(G)-p(G)+1。定理8.7一个图G有支撑树的充要条件是G是连通图。372.树和最小支撑树证明:必要性显然；充分性:设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个支撑树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图G的一支撑子图G1。若G1不含圈，则G1是G的一个支撑树。若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图G的一支撑子图G2。依此类推，可以得到图G的一个支撑子图GK，且不含圈，从而GK是一个支撑树。382.树和最小支撑树

定理8.7充分性的证明，提供了一个寻找连通图支撑树的方法叫做“破圈法”。就是从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个支撑树。例8.4:用破圈法求出图8-11的一个支撑树。V5V4V2V3V1e6e5e4e3e2e1e7e8392.树和最小支撑树

取一个圈(v1,v2,v3,v1)，在一个圈中去掉边e3

。在剩下的图中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4

。再从圈（v3,v4v5,v3）中去掉边e6

。再从圈

(v1,v2,v5,v4,v3,v1

）中去掉边e7，

这样，剩下的图不含圈，于是得到一个支撑树，如图8.12所示。v2e1e2e5e8v1v3v4402.树和最小支撑树

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

的所有支撑树T中的权最小，即S(T*)=minS(T)，那么称T*是G的最小支撑树。如前所述，在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，一个问题的解决可以归结为最小支撑树问题。再如，城市间交通线的建造等，都可以归结为这一类问题。422.树和最小支撑树常用的有破圈法和生长法（避圈法）两个方法：

①在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树；

②去掉该圈中权数最大的边；反复重复①②两步，直到最短树。1.破圈法432.树和最小支撑树例8.5

某六个城市之间的道路网如图8.13a所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。2.树和最小支撑树v6v5v2v3v4图8.13av162753544v3v2v1v4v6v5513142图8.13b452.树和最小支撑树

解：这个问题的解决就是要求所示赋权图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所示，即是最小支撑树。462.树和最小支撑树

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

）。这时也得到了如图8.13b所示的最小支撑树。483.最短路径问题一.引言

最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。也可以用于解决其它的最优化问题。

493.最短路径问题

例8．6:如图8.14所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从v1出发，经过这个交通网到达v8，要寻求是总路程最短的线路。图8.14v1v4v2v8v7v6v5v9636234102312624101503.最短路径问题

从v1到v8的路线是很多的。比如从v1出发，经过v2,v5到达v8或者从v1出发，经过v4，v6，v7到达v8等等。但不同的路线，经过的总长度是不同的。例如，按照第一个线路，总长度是6+1+6=13单位，按照第二个路线，总长度是1+10+2+4=17单位。513.最短路径问题

一般意义下的最短路问题：设一个赋权有向图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（vs，vt）。由于D是有向图，很明显d（vs，vt）与d（vt，vs）一般不相等。523.最短路径问题

二.Dijkstra算法下面介绍在一个赋权有向图中寻求最短路的方法——Dijkstra算法，它是在1959年提出来的。目前公认，在所有的权wij

≥0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj的最短路。533.最短路径问题Dijkstra算法的基本思想是从vs出发，逐步向外寻找最短路。在运算过程中，与每个点对应，记录一个数，叫做一个点的标号。它或者表示从vs到该点的最短路权（叫做P标号），或者表示从vs到该点最短路权的上界（叫做T标号）。算法的每一步是去修改T标号，把某一个具有T标号的点改变为具有P标号的点，使图D中具有P标号的顶点多一个。这样，至多经过P-1步，就可求出从vs到各点vj的最短路。543.最短路径问题

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

由于所有的权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单位。而min{d（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的最短路。57例1说明：再看从v1和v4指向其余点的弧,min{d（v1,v1）+w12，d（v1,v1）+w13，d（v1,v4）+w46}=d（v1,v1）+w13=3。P(V4)v2v8v7v6v5v963623410231262410P(V1)P(V3)1583.最短路径问题

在下述的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。

Dijkstra算法的步骤如下：593.最短路径问题开始（i=0）

令S0={vs}，P（vs）=0，λ(vs)=0，对每一个v≠vs，令T（v）=+∞，λ(v)=M，令k=s；（1）如果Si=V，则算法结束，对每一个v

Si，d（vs,v）=P（v）。否则转入（2）；（2）考察每一个使（vi,vj）

A，且vj不属于Si的点vj，如果T(vj)>P(vk)+wkj

，则把T(vj)改变为P(vk)+wkj，把λ(vj)改变为k，否则转入（3）；603.最短路径问题（3）令(vji)=min{T(vj)

vj

Si}，如果T(vji)<+∞，则把vji的T标号改变为P标号P(vji)=T(vji)，令Si+1=Si∪{vji}，k=ji，把i换成i+1，转入（1）；否则结束。这时，对每一个v

Si，d(vs,v)=P(v)。对每一个v不属于Si，d（vs,v）=T（v）。613.最短路径问题

现在用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)+w12<T(v2)，故将T(v2)改变为P(v1)+w12=6，λ(v2)改变为1。同理，将T(v3)改变为P(v1)+w13=3，λ(v3)改变为1，将T(v4)改变为P(v1)+w14=1，λ(v4)改变为1。623.最短路径问题

（3）在所有的T标号中，T(v4)=1最小，于是令P(v4)=1，S1=S0∪{v4}={v1,v4},k=4。

i=1：（2）将T(v6)改变为P(v4)+w46=11，λ(v6)

改变为4。（3）在所有的T标号中，T(v3)=3最小，于是令P(v3)=3，S2={v1,v4,v3}，k=3。

i=2：

633.最短路径问题

（2）（v3,v2）∈A，v2不属于S2，

T(v2)>w32+P(v3)，将T(v2)改变为

P(v3)+w32=5，λ(v2)改变为3。（3）在所有的T标号中，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.最短路径问题

（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)<w78+P(v7)，故T(v8)不变。（3）在所有的T标号中，T(v6)=10最小，于是,令P(v6)=10，S6={v1,v4,v3,v2,v5,v7,v6}，

k=6。

i=6：3.最短路径问题

（2）从v6出发没有弧指向不属于S6的点，因此转入（3）。（3）在所有的T标号中，T(v8)=12最小，令

P(v8)=12，S7={v1,v4,v3,v2,v5,v7,v6,v8}，

k=8。

i=7：这时，仅有T标号的点为v9，T（v9）=+∞，算法结束。此时，把P标号和λ值标在图中，如图8.15所示663.最短路径问题v4v2v8v7v6v5v963623410231262410图8.15P(V6)=10P(V7)=9

(V1)=0P(V1)=0P(V4)=1

(V4)=1

(V6)=5

(V5)=2P(V2)=5P(V5)=6P(V8)=12

(V7)=5

(V2)=3

(V8)=5T(V9)=+

(V9)=MP(V3)=3

(V3)=11最短路：V1-(V4-)V3-V2-V5-(V6-V7-)V8673.最短路径问题

从图8.15中，不难看出从v1到v8的最短路。因为λ（v8）=5，故最短路经过点v5有因为λ（v5）=2，故最短路经过点v2。依次类推，λ（v2）=3，λ（v3）=1于是，最短路经过点v3，v1。这样，从v1到v8的最短路是（v1，v3，v2，v5，v8）。同理，可以求出从v1到任一点vi的最短路，显然不存在从v1到v9的最短路。683.最短路径问题

对于一个赋权(无向)图G=（V，E），因为边[vi,vj]可以看作2条弧（vi,vj）和(vj,vi)，并且具有相同的权wij。这样，在一个赋权（无向）图中，如果有所有的权wij>=0,只要将Dijkstra算法中的“（2）看作每一个使（vk,vj）

A，且vj

Sj的点vj”改变为“（2）看作每一个使[vk,vj]

E，且vj

Sj的点vj”而其他的条件不变，同样可以求出从vs到各点的最短路（对于无向图叫做最短链）。作为习题，将例8.6中所示的赋权有向图的箭头去掉，然后求出无向图中从vs到各点的最短路。693.最短路径问题

下面证明Dijkstra算法的正确性。只要证明每一个点v∈Si,P(ν)是从vs到v的最短路权，即P(ν)=d(vs.v).

证:用数学归纳法。当i=0时，结论显然成立。假设i=n时，结论成立。看i=n+1的情形，由于Sn+1=Sn∪{vjn},所以只要证明P(vjn)=d(vs,vj)根据算法，vjm是最具有最小T标号的点，即Tn(vjn)=min{Tn(vj)}，其中vj

Sm.这里，用Tn(ν)表示当i=n时，执行步骤（3）时点ν的T标号。设H是图D中任意一条从vs到vjn的路。703.最短路径问题

因为vs∈Sn,而vjn

Sn,所以从vs出发，沿H必存在一条弧，其始点属于Sn，而终点不属于Sn。令（vr,vl）是第一条这样的弧，于是H=(vs…vr,vl…vjn),s(H)=S((vs,vr))+wrl+S((vl…vjn))。由归纳假设，P(vr)是从vs到vr的最短路权，于是，有S（H）>=P(vr)+wrl+S((vl…vjn)).根据算法中的T标号修改规则，因为vr∈Sn,vl

Sn,故P（vr）+wrl>=Tn(vjn),且S（（vl…vjn））>=所以S（H）>=Tn(vjn)+S((vl,…vjn))>=Tn(vjn).这样，就证明了Tn(vjn)是从vs到vjn的最短权。根据算法，P(vjn)=Tn(vjn),于是就有P(vjn)=d(vs,vjn).713.最短路径问题

Dijkstra算法仅适合于所有的权wij>=0的情形。如果当赋权有向图中存在有负权弧时，则该算法失效。例如图8.16中，根据Dijkstra算法，可以得出从v1到v2最短路权是2，但是这显然不对，因为从v1到v2的最短路是（v1,v3,v2）,权是-1。v1v3v222-3图8.163.最短路径问题

下面介绍当赋权有向图中，存在负权弧时，寻求最短路的方法:首先，设从任一点vi到任一点vj都有一条弧，如果在图D中，（vi,vj）不属于A,则添加弧(vi,vj),并且令wij=+∞.

很明显，从vs到vj的最短路是从vs点出发，沿着这条路到某个点vi的再沿弧(vi,vj)到点vj。显然，从vs到vi的这条路必定是从vs到vi的最短路。否则从vs到vj的这条路将不是最短路。于是，从vs到vj的距离d(vs,vj)满足以下条件，

d(vs,vj)=min{d(vs,vi)+wij},

ii=1,…,p,p=p(D).

3.最短路径问题这个关系式的解d(vs,v1)…d(vs,vp).可利用如下的递推公式求解

d(1)(vs,vj)=wsj,j=1…p.d(t)(vs,vj)=min{d(t-1)(vs,vi)+wij},t=2,3…

i当计算到第K步时,对一切的j=1…p,有

d(k)(vs,vj)=d(k-1)(vs,vj)

则d(k)(vs,vj),j=1…p,就是从vs到各点vj的最短路径的权。74设C是赋权函数有向图D中的一个回路。如果回路C的权S（C）是负数那么称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的路（权无界）。结论753.最短路径问题例8．7:在如图8.17所示的赋权有向图中求从v1到各点的最短路。解:利用上述递推公式，将求解结果列出如表8.18所示。可以看出，当t=4时，有

d(t)(vs,vj)=d(t-1)(vs,vj)j=1…8.因此，表中的最后一列，就是从v1到v1,v2,..,v8的最短路权。763.最短路径问题v8v2v4v7v5v1v3v6图8.17111－1－1－1－2－3－3－5－5223678终点

起点V1V2V3V4V5V6V7V8t=1t=2t=3t=4V10-1-23

0000V260

2

-1-5-5-5V3

-30-5

1

-2-2-2-2V48

0

2

3-7-7-7V5

-1

0

1-3-3V6

1017

-1-1-1V7

-1

0

5-5-5V8

-3

-50

66wij

d(t)(vs,vj)

783.最短路径问题

为了求出从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到vj的最短路是（vs,…vi,vk,vj）在本例中，有表8.18知，d(v1,v8)=6,由于)d(v1,v6)+w68=(-1)+7记录下v6.由于d(v1,v3)+w36=d(v1,v6),j记录下v3.由于d(v1,v1)+w13=d(v1,v3),于是，从v1到v8的最短路是(v1,v3,v6,v8)。

1.狄克斯拉方法适用于满足所有权系数大于等于0（lij≥0）的网络最短路问题，能求出起点

v1

到所有其他点vj

的最短距离；

2.海斯方法基本思想是在最短路线上任意两点间路线也是最短路线。利用vi

到vj

的一步距离求出vi

到vj

的两步距离再求出vi

到vj

的四步距离……经有限次迭代可求出vi

到vj

的最短距离；3.最短路径问题

3.福德方法适用于有负权系数，但无负回路的有向或无向网络的最短路问题，能求出起点

v1

到所有其它点vj的最短距离。

4.网络系统的最大流问题

一

引言在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。814.网络系统的最大流问题图8.19vtv3v2v1v4vs1735108611453Cij图8.19是一个网络。每一个弧旁边的权就是对应的容量（最大通过能力）。要求指定一个运输方案，使得从vs到vt的货运量最大，这是寻求网络系统的最大流问题。82

4.网络系统的最大流问题二基本概念

定义8.5设一个赋权有向图D=（V,A）,在v中指定一个发点vs和一个收点vt,其他的点叫做中间点。对于D中的每一个弧（vi,vj）∈A,都有一个权cij

叫做弧的容量。我们把这样的图D叫做一个网络系统，简称网络，记做D=（V，A，C）。网络D上的流，是指定义在弧集合A上的一个函数f={f(vi,vj)}={fij}f(vi,vj)=fij叫做弧在(vi,vj)上的流量。83

4.网络系统的最大流问题v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fij图8.20网络上的一个流（运输方案）每一个弧上的流量fij就是运输量例如fs1=5,fs2=3,f13=2等等vt84

4.网络系统的最大流问题网络系统上流的特点：(1)发点的总流出量和收点的总流入量必相等；(2)每一个中间点的流入量与流出量的代数和等于零；(3)每一个弧上的流量不能超过它的最大通过能力（即容量）。85

4.网络系统的最大流问题

定义8.6网络上的一个流f叫做可行流，如果f满足以下条件（1）容量条件：对于每一个弧（vi,vj）∈A,有0

fij

cij.

（2）平衡条件：对于发点vs，有∑fsj-∑fjs=v(f)

对于收点vt，有∑ftj-∑fjt=-v(f)

对于中间点，有∑fij-∑fji=0

其中发点的总流量（或收点的总流量）v(f)叫做这个可行流的流量。86

4.网络系统的最大流问题任意一个网络上的可行流总是存在的。例如零流v(f)=0,就是满足以上条件的可行流。网络系统中最大流问题就是在给定的网络上寻求一个可行流f,其流量v(f)达到最大值。设流f={fij}是网络D上的一个可行流。我们把D中fij=cij的弧叫做饱和弧，fij<cij的弧叫做非饱和弧，fij>0的弧为非零流弧，fij=0的弧叫做零流弧。

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

μ+={(vs,v1),(v1,v2),(v2,v3),(v4,vt)},

μ-={(v4,v3)}.vt

4.网络系统的最大流问题增广链，如果链μ满足以下条件：

1．在弧（vi,vj）∈μ+上，有0<=fij<cij,即μ+中的每一条弧是非饱和弧。

2．在弧（vi,vj）∈μ-上，有0<fij<=cij,即μ-中的每一条弧是非零流弧。

例如在图8.20中，链μ=（vs,v1,v2,v3,v4,vt）就是一条增广链。设图D=(V，A，C)，点集S,T

V,S∩T=ф中。将起点在S，终点在T的所有弧作成集合，记做（S，T）。90

4.网络系统的最大流问题定义8.8设一个网络D=（V，A，C）。如果点集V被剖分为两个非空集合V1和V2，发点vs∈V1,收点vt∈V2,那么将弧集（V1,V2）叫做是分离vs和vt的截集。定义8.9设一个截集（V1,V2）.将截集（V1,V2）中所有的弧的容量的和叫做截集的截量，记做s(V1,V2),亦即s(V1,V2)=∑cij。

(vi,vj)∈(V1,V2)91

4.网络系统的最大流问题

下面的事实是显然的：一个网络D中，任何一个可行流f的流量v(f)都小于或等于这个网络中任何一个截集(V1,V2)的截量。并且，如果网络上的一个可行流f*和网络中的一个截集（V1*,V2*），满足条件v*(f*)=c(V1*,V2*),那么f*一定是D上的最大流，而（V1*,V2*）一定是D的所有的截集中截量最小的一个（即最小截集）。92

4.网络系统的最大流问题定理8.8网络中的一个可行流f*是最大流的充分必要条件是，不存在关于f*的增广链。定理8.9在一个网络D中，最大流的流量等于分离vs和vt的最小截集的截量。

定理8.8实际上提供了一个寻求网络系统最大流的方法：如果网络D中有一个可行流f，只要判断网络是否存在关于可行流f的增广链。如果没有增广链，那么f一定是最大流。如有增广链，那么可以按照定理8.9，不断改进和增大可行流f的流量，最终可以得到网络中的一个最大流。934.网络系统的最大流问题三．标号法从网络中的一个可行流f出发（如果D中没有f，可以令f是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。用给顶点标号的方法来定义V1*.在标号过程中，有标号的顶点是V1*中的点，没有标号的点不是V1*中的点。如果vt有了标号，表示存在一条关于f的增广链。如果标号过程无法进行下去，并且vt未被标号，则表示不存在关于f的增广链。这样，就得到了网络中的一个最大流和最小截集。

4.网络系统的最大流问题

1．

标号过程在标号过程中，网络中的点或者是标号点（分为已检查和未检查两种）。或者是未标号点。每个标号点的标号包含两部分：第一个标号表示这个标号是从那一点得到的。以便找出增广链。第二个标号是为了用来确定增广链上的调整量θ。标号过程开始，（1）先给源点vs标号（0，+∞）。表示从s点有无限流出潜力。（2）找出与已标号节点i相邻的所有未标号节点j，若95（A)(i,j)是前向弧且饱和，则节点j不标号。(B)(i,j)是前向弧且未饱和，则节点j标号为[i,q(j)],表示从节点i正向流出，从始点到节点Vj为止的链最大可增广（前向弧增大，后向弧减小）q(j)=min[q(i),](C)(j,i)是后向弧，若，则节点j不标号。（D)(j,i)是后向弧,若则节点j标号[-i,q(j)],表示从节点j流向i,从始点到节点Vj为止的链最大可增广（前向弧增大，后向弧减小）q(j)=min[q(i),]96（A)节点t尚未标号，但无法继续标记，说明网络中已不存在增广链，当前流v(f)就是最大流;所有获标号的节点在V1中，未获标号的节点在V2中，V1与V2间的弧即为最小截集，算法结束。(B)节点t获得标号，找到一条增广链，由节点t标号回溯可找出该增广链，到步骤（3）；（3）重复步骤（2），可能出现如下两种情况：97

2.调整过程首先按照vt和其他的点的第一个标号，反向追踪，找出增广链μ。例如，令vt的第一个标号是vk，则弧（vk,vt）在μ上。再看vk的第一个标号，若是vi，则弧(vi,vk)都在μ上。依次类推，直到vs为止。这时，所找出的弧就成为网络D的一条增广链μ。取调整量θ=l(vt),即vt的第二个标号，

4.网络系统的最大流问题98

fij+θ，当(vi,vj)∈μ+

令f’ij=fij-θ，当(vi,vj)∈μ-

其他不变

再去掉所有的标号，对新的可行流f’={f’ij},重新进行标号过程，直到找到网络D的最大流为止。

4.网络系统的最大流问题994.网络系统的最大流问题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=1<cs1=5,故给v1标号(vs,l(v1)),其中l(v1)=min[l(vs),(cs1-fs1)]=min[+∞,5-1]=4.

（3）看v1:在弧（v1,v3）上,f13=c13=2,不具备标号条件.在弧(v2,v1)上,f21=1>0,故给v2标号（-v1,l(v2)）,其中l(v2)=min[l(v1),f21]=min[4,1]=1.

4.网络系统的最大流问题（4）看v2:在弧（v2,v4）上，f24=3<c24=4,故给v4标号（v2,l(v4)）其中

l(v4)=min[l(v2),(c24-f24)]=min[1,1]=1.

在弧（v3,v2)上，f32=1>0,

故给v3标号（-v2，l(v3)),其中

l(l(v3)=min[l(v2),f32]=min[1,1]=1。（5）在v3,v4中任意选一个，比如v3,在弧（v3,vt）上，f3t=1<c3t=2,故给vt标号(v3,l(vt)),其中l(vt)=min[l(v3),(c3t-f3t)]=min[1,1]=1.因为vt被标上号，根据标号法，转入调整过程。

4.网络系统的最大流问题102

2.调整过程从vt开始，按照标号点的第一个标号，用反向追踪的方法，找出一条从vs到vt的增广链μ，如图8.22中双箭线所示。不难看出,μ+={(vs,v1),(v3,vt)},μ-={(v2,v1),(v3,v2)},取θ=1，在μ上调整f，得到

fs1+θ=1+1=2在μ+上

f3t+θ=1+1=2在μ+上

f*=f21-θ=1-1=0在μ-上

f32-θ=1-1=0在μ-上其他的不变4.网络系统的最大流问题103

4.网络系统的最大流问题V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,1）（2,2）（5,3）（1,1）（1,1）(Cij,fij)Vt(v2,1)(0，+∞)(-v1,1)(vs,4)(-V2,1)图8.22104

调整后的可行流f*，如图8.23所示，再对这个可行流从新进行标号过程，寻找增广链。首先给vs标号（0，+∞），看vs,给v1标号（vs,3）。看v1,在弧（v1,v3）上，f13=c13,弧（v2,v1）上，f21=0,均不符合条件。因此标号过程无法进行下去，不存在从VS到Vt的增广链，算法结束。这时，网络中的可行流f*即是最大流，最大流的流量V(f*)=fs1+fs2=5.同时，也找出D的最小截集（V1，V2），其中V1是标号的集合，V2是未标号的集合。最小截集（V1，V2）={({(vs,v2),(v1,v3)}.

4.网络系统的最大流问题4.网络系统的最大流问题V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,2）（2,2）（5,3）（1,0）Vt(0，+∞)(vs,3)图8.23(Cij,fij)（1,0）106t(5,3)(8,5)(3,1)(7,6)(4,1)(6,3)(6,1)(7,4)(8,4)23s45t例8.8:求下图网络最大流及最小割集。107t(5,3)(8,5)(3,1)(7,6)(4,1)(6,3)(6,1)(7,4)(8,4)23s45t(Vs,2)(V2,2)(V4,2)解1:确定一初始可行流，流量为V(f0)=8;2:标号寻找一条增广链，如下图所示，（s,2,4,t)为增广链，增广流量为2。(0，+∞)108t(5,5)(8,5)(3,1)(7,6)(4,1)(6,5)(6,1)(7,6)(8,4)23s45t3:增广过程对（s,2,4,t)为增广链上弧进行增广，得如下图的新的可行流，流量为V(f1)=10

。109t(5,5)(8,5)(3,1)(7,6)(4,1)(6,5)(6,1)(7,6)(8,4)23s45t(Vs,3)(-V3,2)(V2,1)(V4,1)4:标号寻找一条增广链，在上图的基础上，重新寻找另一条增广链如下图所示，从图可知（s,3，2,4,t)为增广链，增广流量为1。(0，+∞)110t(5,5)(8,6)(3,0)(7,6)(4,1)(6,6)(6,1)(7,7)(8,4)23s45t5:增广过程对增广链（s,3，2,4,t)上弧进行增广，得如下图的新的可行流，流量为V(f2)=11

。1116:标号寻找一条增广链，在上图的基础上，重新寻找另一条增广链如下图所示，从图可知（s,3，5,t)为增广链，增广流量为1。t(5,5)(8,6)(3,0)(7,6)(4,1)(6,6)(6,1)(7,7)(8,4)23s45t(Vs,2)(V3,1)(V5,1)(0，+∞)112t(5,5)(8,7)(3,0)(7,7)(4,1)(6,6)(6,1)(7,7)(8,5)23s45t7:增广过程对增广链（s,3，5,t)上弧进行增广，得如下图的新的可行流，流量为V(f3)=12

。113t(5,5)(8,7)(3,0)(7,7)(4,1)(6,6)(6,1)(7,7)(8,5)23s45t8:标号寻找一条增广链，在上图的基础上，重新寻找另一条增广链如下图所示，从图可知标号进行到节点3时已无法进行下去，说明上图的可行流已不存在增广链，上图的可行流即为所求的最大流，最大流的流量为V(f*)=12

。(Vs,1)(0，+∞)1149:另外，从上图还可知，已标号节点为s和V3，即V1={s,V3}是标号的集合，V2={V2,V4,V5,t}是未标号的集合,所以可得最小截集为:

（V1，V2）={(s,V2),(V3,V5)}.115

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

设一个网络D=（V1，A，C），对于每一个弧(vi,vj)∈A,给定一个单位流量的费用bij>=0，网络系统的最小费用最大流问题，是指要寻求一个最大流f，并且流的总费用b(f)=∑bijfij达到最小。

（Vi,Vj）∈A5.网络系统的

最小费用最大流问题在一个网络D中，当沿可行流f的一条增广链μ，以调整量θ=1