运筹学课件图与网络优化

1图论的起源与发展

1736年，Euler哥尼斯堡七桥问题(KönigsbergBridgeProblem)BACD一笔画定理：连通图中，与偶数条线相连的点叫偶点，与奇数条线相连的点叫奇点，奇点个数超过两个的图形不能一笔画出。ABCD第十一章图与网络优化2

1847年，kirchhoff，电网络，“树”；

1852年，《四色猜想》；

1964年，华罗庚，《统筹方法平话》。

1857年，Cogley，同分异构，“树”；

1956年，杜邦公司，CPM，关键路线法；

1958年，美国海军部，PERT，计划评审技术；

1962年，管梅谷，《中国邮路问题》；3一、引例例1(P294)北京、上海等十个城市间的铁路交通图。北京天津济南青岛武汉南京上海郑州连云港徐州第一节图的基本概念与此类似的还有电话线分布图、煤气管道图、航空路线图等。4例2(P294)分别用点v1,v2,v3,v4,v5分别代表甲、乙、丙、丁、戊五支球队。若有两支球队之间比赛过，就在相应的点之间联一条线，且这条线不过其他点。如下图所示：v1v2v3v4v5由图可知各队之间的比赛情况如下：甲——

乙、丙、丁、戊乙——

甲、丙丙——

甲、乙、丁丁——

甲、丙、戊戊——

甲、丁5边两点之间不带箭头的联线。如e3.记为e3=[v1,v4]或[v4,v1]v1v4a3

弧两点之间带箭头的联线。如a3.记为a3=（v1,v4）v1v4e3端点及关联边若边e=[u,v]∈E，则称u,v

为e的端点，也称u,v是相邻的，称e是点u(及点v)的关联边。如：v1,v4为e3的端点，v1,v4是相邻的，e3是v1（v4

）的关联边。二、基本概念6有向图

由点及弧所构成的图，记为D=(V,A)，

V,A分别是D的点集合与弧集合。无向图由点及边所构成的图。记为G=(V,E),V,E分别是G的点集合与边集合。v1v2v3v4v1v2v3v4a1a2a3a4a5e1e2e3e4e5a6e67环若在图G中，某个边e的两个端点相同，则称e是环。如

e7v1v2v3v4e1e2e3e4e5e6e7多重边若两个点之间有多于一条的边，称这些边为多重边。如

e1,e2简单图一个无环、无多重边的图。多重图一个无环、但允许有多重边的图。8点的次以点vi为端点边的个数，记为dG(vi)或d(vi)。v1v2v3v4e1e2e3e4e5e6e7如d(v4)=5d(v2)=4v5悬挂点：次为1的点，如v5

悬挂边：悬挂点的关联边，如e8e8

孤立点：次为0的点

偶点：次为偶数的点，如v2奇点：次为奇数的点,

如v59链中间点初等链圈初等圈简单圈

v1v2v5v6v7v3v4e1e2e4e3e5e6e7e8e9在上图中,(v1,v2,v3,v4,v5,v3,v6,v7)是一条链,但不是初等链在该链中,v2,v3,v4,v5,v3,v6是中间点(v1,v2,v3,v6,v7)是一条初等链(v1,v2,v3,v4,v1)是一个初等圈(v4,v1,v2,v3,v5,v7,v6,v3,v4)是一个简单圈10连通图图G中，若任何两个点之间，至少有一条链，称为连通图。否则称为不连通图。连通分图(分图)若G是不连通图，则它的每个连通的部分称为连通分图。v1v2v3v4e1e2e3e4e5e6v5v6e7如左图就是个不连通图，它是由两个连通分图构成的。11支撑子图给定一个图G=(V,E)，如果图G’=(V’,E’)，使V’=V及E’E，则称G’是G的一个支撑子图。v4v1v2v3(G)v1v2v3v4(G’)基础图给定一个有向图D=(V,A)，从D中去掉所有弧上的箭头，所得到的无向图称为基础图。记之为G(D)。v1v2v3v4a1a2a3a4a5a6D=(V,A)v1v2v3v4e1e2e3e4e5e6G(D)12v1v2v3v4a1a2a3a4a5a6a7a8a9a10a11v6v7路初等路回路v5简单有向图多重有向图13定理1图G=(V,E)中，所有点的次之和是边数的两倍，即定理2任一图中奇点的个数为偶数。三、基本定理14一、定义：

无圈的连通图例3(P298例4)在五个城市之间架设电话线，要求任两个城市之间都可以相互通话（允许通过其他城市），并且电话线的根数最少。v1v5v2v3v4用v1,v2,v3,v4,v5代表五个城市,如果在某两个城市之间架设电话线,则在相应的两点之间联一条边,这样一个电话线网就可以用一个图来表示。显然,这个图必须是连通的,而且是不含圈的连通图。如左图所示。第二节树15例4(P298例5)某工厂的组织机构如下图所示厂长行政办公室生产办公室生产计划科技术科设计组工艺组供销科财务科行政科一车间铸造工段锻压工段二车间三车间四车间该厂的组织机构图就是一个树。16例5

树图倒置的树，根(root)在上，叶(leaf)在下17定理1

设图G=(V,E)是一个树，p(G)≥2，

则G中至少有两个悬挂点。二、性质证明：设P=(v1,v2,…,vk)是G中含边数最多的一条初等链，因p(G)≥2，并且G是连通的，故链P中至少有一条边，从而v1与vk是不同的。下面证明v1是悬挂点，即d(v1)=1。（反证法）假设d(v1)≥2，则存在边[v1,vm]，使m≠2。（i）若点vm在P上，则(v1,v2,…,vm,v1)是G中的一个圈，这与树的定义矛盾。（ii）若点vm不在P上，则(vm,v1,v2,…,vk)是G中的一条初等链，它的边数比P多一条，这与P是边数最多的初等链矛盾。故原假设不成立，于是d(v1)=1，即v1是悬挂点。同理可证vk也是悬挂点，故G至少有两个悬挂点。18定理2

图G=(V,E)是一个树的充分必要条件是

G中不含圈，且恰有p-1条边。证明：19定理3

图G=(V,E)是一个树的充分必要条件是

G是连通图，并且q(G)=p(G)-1。证明：由定理2，必要性显然。20定理4

图G是树的充分必要条件是任意两个顶点之间恰有一条链。证明：由树的定义，必要性显然。因为任两个顶点间恰有一条链，显然G是连通的。如果G中含有圈的话，则其中至少有两个顶点间有两条链，这与题设矛盾。充分性得证。推论：

从一个树中去掉一条边，则余下的图是不连通的。

在树中不相邻的两个点间添上一条边，则恰好得到一个圈。21三、图的支撑树定义：设图T=(V,E’)是图G的支撑子图，如果图T=(V,E’)

是一个树，则称T是G的一个支撑树。定理：图G有支撑树的充分必要条件是图G是连通的。证明：必要性显然。再证充分性。设图G是连通图，若G不含圈，则G本身是一个树，从而G是它自身的一个支撑树。如果G含圈，任取一个圈，从圈中任意地去掉一条边，得到图G的一个支撑子图G1。如果G1不含圈，那么G1是G的一个支撑树；如果G1仍含圈，那么从G1中任取一个圈，从圈中再任意去掉一条边，得到图G的一个支撑子图G2，如此重复，最终可以得到G的一个支撑子图Gk,它不含圈，于是Gk是G的一个支撑树。22破圈法例6用破圈法求解图的一个支撑树v1v2v3v4v5e1e2e3e4e5e6e7e8这就得到了该图的一个支撑树。支撑树的求解方法23避圈法v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9这就得到了该图的一个支撑树。24定义1

给定图G=(V,E)，对G中的每一条边[vi,vj]，相应地有一个数wij，则称图G为赋权图，wij称为边[vi,vj]上的权。1.定义定义2

如果T=(V,E’)是G的一个支撑树，称E’中所有边的权之和为支撑树T的权，记为w(T)，即最小支撑树：如果支撑树T*的权w(T*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树(简称最小树),即四、最小支撑树252.最小支撑树的求法方法一：避圈法

开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈。v1v2v3v4v5v6651572344这就得到了该图的一个最小支撑树。26方法二：破圈法

任取一个圈，从圈中去掉一条权最大的边。在余下的图中，重复这个步骤，直到得到不含圈的图为止，这时的图便是最小树。v1v2v3v4v5v6651572344这就得到了该图的一个最小支撑树。27第三节最短路问题一、最短路问题的提出v1v2v3v4v5v6v7v8v9132216610410423236例7(P304例10)左图为单行线交通网，弧旁数字表示通过这条单行线所需要的费用。求从v1出发到v8总费用最小的路线。28二、求解方法

情形一：所有的权均为非负（wij≥0）寻找起点已标号而终点未标号的最小值(0,0)(v1,1)第一步：v1v2v3v4v5v6v7v8v9132216610410423236狄克斯特拉方法

(Dijkstra,1959)29v1v2v3v4v5v6v7v8v9132216610410423236(0,0)(v1,3)(v1,1)第二步：30第三步：v1v2v3v4v5v6v7v8v9132216610410423236(0,0)(v1,3)(v1,1)(v3,5)31第四步：v1v2v3v4v5v6v7v8v9132216610410423236(0,0)(v1,3)(v1,1)(v3,5)(v2,6)32第五步：(v5,9)v1v2v3v4v5v6v7v8v9132216610410423236(0,0)(v1,3)(v1,1)(v3,5)(v2,6)33第六步：(v5,9)v1v2v3v4v5v6v7v8v9132216610410423236(0,0)(v1,3)(v1,1)(v3,5)(v2,6)(v5,10)34第七步：(v5,12)(v5,9)v1v2v3v4v5v6v7v8v9132216610410423236(0,0)(v1,3)(v1,1)(v3,5)(v2,6)(v5,10)35v1到v8的最短路为(v1,v3,v2,v5,v8),其长度为12.v1v2v3v4v5v6v7v8v9132216610410423236(v1,1)(v4,11)(v5,10)(v5,9)(v5,12)(v2,6)(v3,5)(0,0)(v1,3)36计算步骤：

(1)令vs的P标号值为0，其它所有点的T标号值为+∞；

(2)考察从所有P标号点(已求出最短距离的点)出发的弧的终点vj(P标号的点除外)

，计算起点vs到vj的距离dsj(vi的P标号值＋Wij)，修改vj的T标号；若vj不存在，算法终止，转(4)。

(3)增加新的P标号点。比较所有T标号，最小者对应的点成为新的P标号点，即求出了vs到某个vj的最短距离dsj*，转(2)。

(4)逆着计算过程反推，找出最短路。优点：能找出从起点到所有点的最短路缺点：不能解决带有负权的图的最短路问题37Dijkstra算法失效只能采用最原始的思想，即找出vs到vj的所有路线的权，才能确定vs到vj的最短距离。具体算法如下：设有向图中有n个点，从vi到vj的最短路线不一定从vi直达vj，也可能经过一个、两个或n－2个中间点才能到达vj

。把从vi直达vj，称为走一步，经过一个中间点称为走二步，则vi到vj的最短路线最多走n－1步。情形二：赋权有向图中存在具有负权的弧38应用条件：图中不存在负回路。v1v2v3v4v5v6v7v8例8(P309例12)求v1到图中其他各点的最短路。

6-1-283-3-5-121112-1-3-57(0,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)①d(1)(v1,v1)=w11=0d(1)(v1,v2)=w12=-1d(1)(v1,v3)=w13=-2d(1)(v1,v4)=w14=3d(1)(v1,v5)=w15=d(1)(v1,v6)=w16=d(1)(v1,v7)=w17=d(1)(v1,v8)=ω18=d(1)(v1,vj)=wsj走1步时39v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(0,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)(v3,-5)(v3,-7)(v3,-1)②(v4,5)(v2,1)d(1)(v1,v1)+w12d(1)(v1,v2)+w22d(1)(v1,v3)+w32d(1)(v1,v4)+w42d(1)(v1,v5)+w52d(1)(v1,v6)+w62d(1)(v1,v7)+w72d(1)(v1,v8)+w82d(2)(v1,v2)=Min40走2步时v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(0,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v3,-5)(v3,-7)(v3,-1)(v2,1)(v4,5)(v6,6)③(v2,-3)(v4,-5)41走3步时v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(0,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)(v3,-5)(v3,-7)(v3,-1)(v2,-3)(v4,-5)(v6,6)(v5,-4)(v7,-6)(v8,3)(v8,1)④42走4步时wijd(t)(v1

,vj)

v1v2v3v4v5v6v7v8t=1t=2t=3t=4v10-1-230000v2602-1-5-5-5v3-30-51-2-2-2-2v48023-7-7-7v5-101-3-3v61017-1-1-1v7-105-5-5v8-3-5066说明：表中空格处为+。缺点：不能解决负回路的情况。表格法44三、应用举例例9(P311例13)

设备更新问题。某企业使用一台设备，在每年年初都要决定是购置新设备还是继续使用旧的。购置新设备要支付一定的购置费，使用旧设备则要支付维修费。试制定一个五年的设备更新计划，使得总支付费用最少。已知该设备在各年年初的价格为：第一年第二年第三年第四年第五年1111121213已知使用不同时间的设备维修费用为：使用年数0~11~22~33~44~5维修费用568111845设以vi(i=1,2,3,4,5)表示“第i年初购进一台新设备”这种状态，以v6表示“第5年末”这种状态；以弧(vi,

vj)表示“第i年初购置的一台设备一直使用到第j年初”这一方案，以wij表示这一方案所需购置费和维修费之和。这样，可建立本例的网络模型。于是，该问题就可归结为从图中找出一条从v1到v6的最短路问题。从图中可以得出两条最短路：

v1—v3—v6,

v1—v4—v646v1v2v3v5v6v4163022165941224130173123172318(0,0)(v1,16)①47v1v2v3v5v6v4163022165941224130173123172318(0,0)(v1,16)(v1,22)②48v1v2v3v5v6v4163022165941224130173123172318(0,0)(v1,16)(v1,22)(v1,30)③49v1v2v3v5v6v4163022165941224130173123172318(0,0)(v1,16)(v1,22)(v1,30)(v1,41)④50v1v2v3v5v6v4163022165941224130173123172318(0,0)(v1,16)(v1,22)(v1,30)(v1,41)(v3,53)(v4,53)⑤51第四节网络最大流问题

一、问题的提出

如下是一运输网络，弧上的数字表示每条弧上的容量，问：该网络的最大流量是多少？vsv2v1v3v4vt43211523452vsv2v1v3v4vt43211523453二、求解方法（一）概念1.可行流容量限制条件：0fijcij

平衡条件：2.零流弧:

fij=0的弧,若是网络中连接起点vs和终点vt的一条链，定义链的方向是从vs到vt，则链上的弧被分成两类：前向弧：弧的方向与链的方向一致,+表示中前向弧的集合后向弧：弧的方向与链的方向相反,-表示中后向弧的集合3.前向弧、后向弧饱和弧:

fij=cij的弧54设f是一可行流，是从vs到vt的一条链，若满足下列条件，则称之为（关于流f的）一条增广链：在弧(vi,vj)+上，0fij<cij

在弧(vi,vj)-上，0<

fijcij4.增广链vsv2v1v3v4vt10(5)8(3)4(1)5(2)3(2)6(3)3(3)11(6)17(2)5(1)在左图中,(vs,v1,v2,v3,v4,vt)是一条增广链,因为+

和-中的弧满足增广链的条件。如：555.可扩充量6.调整后的流量56v5v1v2v3v4v6(2,2)(8,3)(3,1)(2,2)(4,1)(2,1)(2,2)(5,3)(二)标号法求最大流(FordFulkerson)例10

思路：从一可行流出发，检查关于此流是否存在增广链。若存在增广链，则增大流量，使此链变为非增广链；这时再检查是否还有增广链，若还有，继续调整，直至不存在增广链为止。57v5v1v2v3v4v6(2,2)(8,3)(3,1)(2,2)(4,1)(2,1)(2,2)(5,3)(0,+)(v1,5)(v3,3)(-v4,1)(v2,1)(v5,1)按θ=1进行调整，可得下图：58v5v1v2v3v4v6(2,2)(8,4)(3,0)(2,2)(4,2)(2,2)(2,2)(5,4)(0,+)(v1,4)(v3,2)按同样的步骤找可行流。此时,标号过程无法进行下去，算法结束。59三、标号算法的理论依据定理1

可行流f*是最大流的充要条件是不存在关于f*的增广链。证明:60定义

截集截量61定理2（最大流最小截量定理）

任一个网络D中，从起点vs到终点vt的最大流的流量等于分离vs,vt的最小截集的截量.62v5v1v2v3v4v6(2,2)(8,4)(3,0)(2,2)(4,2)(2,2)(2,2)(5,4)(0,+)(v1,4)(v3,2)例：63四、最大流最小截集的标号法举例st134256(14,14)(9,9)(15,9)(16,15)(3,1)(12,10)(6,6)(4,3)(5,5)(22,22)(13,12)(7,5)(6,3)(19,10)(0,+)(-v2,6)(v3,1)(v4,1)st134256(14,14)(9,9)(15,10)(16,15)(3,1)(12,10)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,3)(19,11)(0,)(vs,5)(v2,2)(-v5,2)(v4,2)(vs,6)(1)(2)64st134256(14,14)(9,9)(15,10)(16,15)(3,1)(12,10)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,3)(19,11)(0,)(vs,5)(v2,2)(-v5,2)(v4,2)st134256(14,14)(9,9)(15,12)(16,15)(3,1)(12,12)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,1)(19,13)(0,)(vs,3)(-v2,3)最小截集(3)(2)65一、问题的提出v1v2vsv3vt(4,10)(1,8)(6,2)(3,10)(2,5)(1,7)(2,4)第五节最小费用最大流问题66二、算法的理论基础

由于同一流量存在多个可行流f，所以一定存在费用最小的可行流f。设是关于可行流f的一条增广链，以=1调整f得到新的可行流f’

，b(f’)比b(f)增加的费用为：把调整后增加的费用称为这条增广链的费用。67

已知最小费用流f，问题的关键是如何找到关于f

的最小费用增广链，从而沿去调整f，得到新的最小费用流f’

。(1)若f是流量为v(f)

的所有可行流中费用最小者，而是关于f

的所有增广链中费用最小的增广链，那么沿去调整f，得到的可行流f’

，就是流量为v(f’)的所有可行流中的最小费用流。这样，当f’

是最大流时,也就得到了我们所要的最小费用最大流。68

由上面的分析可知，只要网络中存在增广链，经变换后就一定能找到与增广链相对应的一条路，且增广链的费用与其对应的路的长度相等。因此找一条最小费用增广链等价于找一条从vs到vt的最短路。为此，要求构造的路必须对应的是增广链。如何找一条关于f

的最小费用增广链呢？vsv2vtv1bs1b21b2t已知下图为关于f

的一条增广链。增广链的费用为：

bs1+b2t－b21-bs1-b21-b2t从vs到vt的路为vsv1

v2

vt，距离为bs1+b2t－b21

，与增广链的费用相等。经变换后对应一条路69三、求解方法S2：构造赋权有向图W（f（i））：顶点为网络D的顶点，把D中的每条弧(vi,vj)变成方向相反的两条弧(vi,vj)

,(vj,vi)，定义W（f（i））中弧的权为：S3：求W（f（i））起点到终点的最短路，对与这条最短路相应的增广链进行调整。转S2，直到不存在最短路。70v1v2vsv3vt(0,10)(0,8)(0,2)(0,10)(0,5)(0,7)(0,4)解：（1）取f（0）=0为初始可行流。如下图所示，弧旁数字为(fij,cij)。71v1v2vsv3vt4

16

32

1

2构造赋权有向图W（f（0）），用标号法求其最短路。(vs,1)(0,0)v1v2vsv3vt(0,10)(0,2)(0,10)(0,4)(0,8)(0,5)(0,7)72v1v2vsv3vt

3

1(vs,1)(0,0)(v2,3)

22

14673v1v2vsv3vt

3

1(vs,1)(0,0)(v2,3)(v2,4)4

122674v1v2vsv3vt

3

1(vs,1)(0,0)(v2,3)(v2,4)(v1,4)622

1

475由此得到从vs到vt的最短路：v1v2vsv3vt(4,10)(1,8)(6,2)(3,10)(2,5)(1,7)(2,4)(vs,1)(v2,3)(v1,4)76v1v2vsv3vt(0,10)(0,8)(0,2)(0,10)(0,5)(0,7)(0,4)与上述最短路相应的增广链为μ＝(vs,v2,v1,vt)。以

=5调整该增广链，得到流f（1），过程如下图所示：(5,8)(5,5)(5,7)77（2）构造赋权有向图W（f（1）），用标号法求出最短路：v1v2vsv3vt4

1

6

3

1

2-1-2-1v1v2vsv3vt(0,10)(0,2)(0,10)(0,4)(5,8)(5,5)(5,7)78v1v2vsv3vt(0,10)(5,8)(0,2)(0,10)(5,5)(5,7)(0,4)以

=2调整最短路对应的增广链，得到流f（2）。(2,10)(7,7)79（3）构造赋权有向图W（f（2）），用标号法求出最短路：v1v2vsv3vt

4

1

6

3

-1

2-1-2-4v1v2vsv3vt(2,10)(0,2)(0,10)(0,4)(5,8)(5,5)(7,7)80以

=3调整最短路对应的增广链，得到流f（3）。v1v2vsv3vt(0,10)