第10章 图与网络优化

1、图与网络分析图与网络分析 (graph theory and network analysis) 图与网络的基本知识图与网络的基本知识 最短路问题最短路问题 树及最小树问题树及最小树问题 最大流问题最大流问题 b d a c a b c d 哥尼斯堡七空桥哥尼斯堡七空桥 一笔画问题一笔画问题 一、一、 图与网络的基本知识图与网络的基本知识 （一）、（一）、图与网络的基本概念图与网络的基本概念 e a d cb 1、一个图是由点和连线组成。（连线可带箭头，也可不带，、一个图是由点和连线组成。（连线可带箭头，也可不带， 前者叫弧，后者叫边）前者叫弧，后者叫边） 一个图是由点集一个图是由点集 和和

2、中元素的无序对的一个中元素的无序对的一个 集合集合 构成的二元组，记为构成的二元组，记为g g =(=(v v，e e) )，其中其中 v v 中中 的元素的元素 叫做顶点，叫做顶点，v 表示图表示图 g 的点集合；的点集合；e 中的元中的元 素素 叫做边，叫做边，e 表示图表示图 g 的边集合。的边集合。 j vv k ee j v k e v v1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 例例 654321 ,vvvvvvv , 10987654321 eeeeeeeeeee， , 211 vve , 212 vve , 323 vve

3、, 434 vve , 315 vve , 536 vve , 537 vve , 658 vve , 669 vve , 6110 vve 图图1 2、如果一个图是由点和边所构成的，则称其为无向图，记作、如果一个图是由点和边所构成的，则称其为无向图，记作 g = (v，e)，连接点的边记作连接点的边记作vi , vj，或者或者vj , vi。 3、如果一个图是由点和弧所构成的，那么称它为有向图，记、如果一个图是由点和弧所构成的，那么称它为有向图，记 作作d=(v, a)，其中其中v 表示有向图表示有向图d 的点集合，的点集合，a 表示有向图表示有向图d 的弧的弧 集合。一条方向从集合。一条方

4、向从vi指向指向vj 的弧，记作的弧，记作(vi , vj)。 v4 v6 v1 v2 v3 v5 v = v1 , v2 , v3 , v4 , v5 , v6 ， a = (v1 , v3 ) , (v2 , v1) , (v2 , v3 ) , (v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) 图图2 4 4、一条边的两个端点是相同的、一条边的两个端点是相同的, ,那么称为这条边是环那么称为这条边是环 5 5、如果两个端点之间有两条以上的边，那么称为它们、如果两个端点之间有两条以上的边，那么称为它们 为多重边。为

5、多重边。 6 6、一个无环，无多重边的图称为简单图，一个无环，、一个无环，无多重边的图称为简单图，一个无环， 有多重边的图称为多重图。有多重边的图称为多重图。 7、每一对顶点间都有边相连的无向简单图称为完全图、每一对顶点间都有边相连的无向简单图称为完全图 有向完全图则是指任意两个顶点之间有且仅有一条有有向完全图则是指任意两个顶点之间有且仅有一条有 向边的简单图。向边的简单图。 v1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 度为零的点称为弧立度为零的点称为弧立 点，度为点，度为1 1的点称为悬的点称为悬 挂点。悬挂点的关联挂点。悬挂点的关联 边

6、称为悬挂边。度为边称为悬挂边。度为 奇数的点称为奇点，奇数的点称为奇点， 度为偶数的点称为偶度为偶数的点称为偶 点。点。 8 8、以点、以点v v为端点的边的个数称为点为端点的边的个数称为点v v 的度（次），记的度（次），记 作作 。)(vd 图中图中 d(v1)= 4，d(v6)= 4（环计两度环计两度） 定理定理1 1 所有顶点度数之和等于所有边数的所有顶点度数之和等于所有边数的2 2倍。倍。 在任一图中，奇点的个数必为偶数。在任一图中，奇点的个数必为偶数。 所有顶点的入次之和等于所有顶点的出次之和。所有顶点的入次之和等于所有顶点的出次之和。 有向图中，以有向图中，以 v vi i 为始

7、点的边数称为点 为始点的边数称为点v vi i的出次，用的出次，用 表示；以表示；以 v vi i 为终点的边数称为点 为终点的边数称为点v vi i 的入次， 的入次， 用用 表示；表示；v vi i 点的出次和入次之和就是该点的次。 点的出次和入次之和就是该点的次。 )( i vd )( i vd 如果如果 v2 v1 , , e2 e1 , ,称称 g2 是是g1 的子图；如果的子图；如果 v2 = v1 , , e2 e1 称称 g2 是是 g1 的部分图或支撑子图。的部分图或支撑子图。 v1 v2 v3 v4 v5v6 v7 e1 e2 e3 e4 e5 e6 e7 e8 e9 e1

8、0 e11 (a) e5 e7 v1 v2 v5v6 v7 e1 e6 e8 (b) 子图子图 v1 v2 v3 v4 v5v6 v7 e1 e6 e7 e9 e10 e11 (c) 支撑子图支撑子图 在实际应用中，给定一个图在实际应用中，给定一个图g=（v，e）或有向图或有向图d= （v，a），在在v中指定两个点，一个称为始点（或发中指定两个点，一个称为始点（或发 点），记作点），记作v1 ，一个称为终点（或收点），记作一个称为终点（或收点），记作vn ，其其 余的点称为中间点。对每一条弧余的点称为中间点。对每一条弧 ，对应一，对应一 个数个数 ，称为弧上的，称为弧上的“权权”。通常把这种赋

9、权的图。通常把这种赋权的图 称为网络。称为网络。 avv ji ),( ji w 10、由两两相邻的点及其相关联的边构成的点边序列称、由两两相邻的点及其相关联的边构成的点边序列称 为链。为链。 如如:v0 ，e1，v1，e2，v2，e3 ， v3 ,vn-1 , en ， vn，记作记作 （ v0 ， v1 ， v2， v3 , , vn-1 ， vn ） e3 v1 v2 v3 v4 v5 v6 e7 e8 e1 e2 e4 e5 e6 e9 e10 11 11、图中任意两点之间均至少有一条通路，则称此图、图中任意两点之间均至少有一条通路，则称此图 为连通图，否则称为不连通图。为连通图，否则

10、称为不连通图。 其链长为其链长为 n ，其中其中 v0 ，vn 分别称为链的起点和终点分别称为链的起点和终点 。 若链中所含的边均不相同，则称此链为简单链；所含的点若链中所含的边均不相同，则称此链为简单链；所含的点 均不相同的链称为初等链均不相同的链称为初等链 , , 也称通路。也称通路。 （二）、（二）、 图的矩阵表示图的矩阵表示 对于网络（赋权图）对于网络（赋权图）g=（v，e），其中边其中边 有权有权 ，构造矩阵，构造矩阵 ，其中：，其中： 称矩阵称矩阵a a为网络为网络g g的权矩阵。的权矩阵。 ),( ji vv ji w evv evvw a ji jiji ji ),(0 ),(

11、 nnji aa )( nnji aa )( evv evv a ji ji ji ),(0 ),(1 设图设图g=（v，e）中顶点的个数为中顶点的个数为n，构造一个矩阵构造一个矩阵 ，其中：，其中： 称矩阵称矩阵a a为网络为网络g g的邻接矩阵。的邻接矩阵。 654321 6 5 4 3 2 1 010101 101001 010111 101010 001101 111010 vvvvvv v v v v v v b 例例 权矩阵为：权矩阵为： 邻接矩阵为：邻接矩阵为： v5 v1v2 v3 v4 v6 4 3 3 2 2 5 6 4 3 7 654321 6 5 4 3 2 1 030

12、303 302004 020576 305020 007204 346040 vvvvvv v v v v v v a 二、二、 树及最小树问题树及最小树问题 v1 v2 v3 v4 v5 v6 1 1、一个连通的无圈的无向图叫做树。、一个连通的无圈的无向图叫做树。 树中次为树中次为1 1的点称为树叶，次大于的点称为树叶，次大于1 1的点称为分支点。的点称为分支点。 已知有六个城市，它们之间要架设电话线，要求任意两个城市已知有六个城市，它们之间要架设电话线，要求任意两个城市 均可以互相通话，并且电话线的总长度最短。均可以互相通话，并且电话线的总长度最短。 树树 的性质：的性质： （1）树必连通

13、，但无回路（圈）。）树必连通，但无回路（圈）。 （2）n 个顶点的树必有个顶点的树必有n-1 条边。条边。 （3）树中任意两个顶点之间，恰有且仅有一条链（初等链）。）树中任意两个顶点之间，恰有且仅有一条链（初等链）。 （4）树连通，但去掉任一条边，必变为不连通。）树连通，但去掉任一条边，必变为不连通。 （5）树无回路（圈），但不相邻的两个点之间加一条边，恰得）树无回路（圈），但不相邻的两个点之间加一条边，恰得 到一个回路（圈）。到一个回路（圈）。 v1 v2 v3 v4 v5 v6 2 2、 设图设图 是图是图g=(v , e )的一支撑子图，如果图的一支撑子图，如果图 是一个树是一个树, ,

14、那么称那么称k 是是g 的一个生成树的一个生成树( (支撑树支撑树) )， 或简称为图或简称为图g 的树。图的树。图g中属于生成树的边称为树枝，不在中属于生成树的边称为树枝，不在 生成树中的边称为弦。生成树中的边称为弦。 ),( 1 evk 一个图一个图g 有生成树的充要条件是有生成树的充要条件是g 是连通图。是连通图。 v1 v2 v3v4 v5 v1 v2 v3 v4 v5 ),( 1 evk 用破圈法求出下图的一个生成树。用破圈法求出下图的一个生成树。 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 e8 v1 v2 v3 v4 v5 e2 e4 e6 e8 v1

15、 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 e8 在图在图g中任意取一个圈，中任意取一个圈， 从圈上任意舍弃一条从圈上任意舍弃一条 边边,将此圈破掉。重复将此圈破掉。重复 此步骤直到图此步骤直到图g中没有中没有 圈为止。圈为止。 （一）（一）破圈法破圈法 （二）（二）避圈法避圈法（加边法）（加边法） 在图中任取一条边在图中任取一条边e1，找一条与找一条与e1不构成圈的边不构成圈的边e2，再找一条再找一条 与与e1，e2不构成圈的边不构成圈的边e3。一般设已有一般设已有e1，e2，ek，找一找一 条与条与e1，e2，ek中任何一些边不构成圈的边中任何一些边不构成圈的边ek

16、+1，重复这重复这 个过程，直到不能进行为止。个过程，直到不能进行为止。 v1 v2 v3 v4 v5 v6v1 v3 v1 v3 v2 v1 v3 v2 v5 v6 v1 v3 v2 v5 v6 v4 v1 v3 v2 v5 深探法（标号法）深探法（标号法）（不要求掌握）（不要求掌握） (1)在点集在点集v中任取一点中任取一点 v,给给v以标号以标号0; (2)若某点若某点u已得标号已得标号i,检查一端点为检查一端点为u的各边的各边,另一端另一端 点是否均已标号点是否均已标号. 若有若有(u,w)边之边之w未标号未标号,则给则给w以标号以标号i+1,记下边记下边 (u,w).令令w代代u,重

17、复重复(2). 若这样的边的另一端点均已有标号若这样的边的另一端点均已有标号,就退到标号就退到标号 为为i-1的的r点点,以以r代代u,重复重复(2).直到全部点得到标号直到全部点得到标号 为止为止. 广探法广探法（不要求掌握）（不要求掌握） (1)在点集在点集v中任取一点中任取一点v,给给v以标号以标号0; (2)令所有标号为令所有标号为i的点集为的点集为vi,检查检查vi,vvi 中的端点中的端点 是否均已标号是否均已标号.对所有未标号之点均标以对所有未标号之点均标以i+1,记下记下 这些边这些边; (3)对标号对标号i+1的点重复步骤的点重复步骤(2),直到全部点得到标号直到全部点得到标

18、号 为止为止. 3 3、最小生成树问题、最小生成树问题 如果图如果图 是图是图g g的一个生成树，那么称的一个生成树，那么称e1上所有边的权的和上所有边的权的和 为生成树为生成树t 的权，记作的权，记作s(t)。如果图如果图g g的生成树的生成树t* 的权的权s(t*)，在在g 的所有生成树的所有生成树t 中的权最小，即中的权最小，即 那么称那么称t*是是g 的最小生成树。的最小生成树。 ),( 1 evt )(min)( * tsts t 某六个城市之间的道路网如图所示，要求沿着已知长度的道路联结某六个城市之间的道路网如图所示，要求沿着已知长度的道路联结 六个城市的电话线网，使电话线的总长度

19、最短。六个城市的电话线网，使电话线的总长度最短。 v1 v2 v3 v4 v5 v6 6 5 1 5 7 2 3 4 4 5 v1 v2 v3 v4 v5 v6 1 2 3 4 4 kruskal算法算法 每步从未选的边中选取边每步从未选的边中选取边e,使使 它与已选边中的最小权边不构它与已选边中的最小权边不构 成圈成圈,直到选够直到选够n-1条边为止条边为止. v1 v2 v3 v4 v5 1 4 2 3 1 3 5 2 破圈法破圈法 (1)从图从图g中任选一棵树中任选一棵树t1; (2)加上一条弦加上一条弦e1,t1+e1中立即生成一个圈中立即生成一个圈.去掉此圈中最大权边去掉此圈中最大权

20、边,得到新得到新 树树t2.以以t2代替代替t1,重复重复(2)再检查剩余的弦再检查剩余的弦,直到全部弦检查完毕为止直到全部弦检查完毕为止. 最短路的一般提法为：设最短路的一般提法为：设 为连通图，图中各边为连通图，图中各边 有权有权 （ 表示表示 之间没有边），之间没有边）， 为图中任意两点，求一条路为图中任意两点，求一条路 ，使它为从，使它为从 到到 的所的所 有路中总权最短。即：有路中总权最短。即： 最小。最小。 ),(evg ji l ji l ts vv , s v ),( ji vvji vv , t v ),( )( ji vv ji ll (一一)、 狄克斯屈拉狄克斯屈拉(di

21、jkstra)算法算法 适用于适用于wij0，给出了从，给出了从vs到任意一个点到任意一个点vj的最短路。的最短路。 三三 、最短路问题、最短路问题 算法步骤：算法步骤： 1.给始点给始点vs以以p标号标号 ，这表示从，这表示从vs到到 vs的最短距离的最短距离 为为0，其余节点均给，其余节点均给t标号，标号， 。 2.设节点设节点 vi 为刚得到为刚得到p标号的点，考虑点标号的点，考虑点vj，其中其中 ，且，且vj为为t标号。对标号。对vj的的t标号进行如下修改：标号进行如下修改： 3.比较所有具有比较所有具有t标号的节点，把最小者改为标号的节点，把最小者改为p标号，即：标号，即： 当存在两

22、个以上最小者时，可同时改为当存在两个以上最小者时，可同时改为p标号。若全部节标号。若全部节 点均为点均为p标号，则停止，否则用标号，则停止，否则用vk代替代替vi，返回步骤（返回步骤（2）。）。 0)( s vp ), 3,2()(nivt i evv ji ),( )(, )(min)( jiijj lvpvtvt )(min)( ik vtvp 例一、例一、用dijkstra算法求下图从v1到v6的最短路。 v v1 1 v v2 2 v v3 3 v v4 4 v v6 6 v v5 5 3 3 5 5 2 2 2 2 4 4 2 2 4 4 2 2 1 1 解解 （1）首先给v v1

23、1以p标号，给其余所有点t标号。 0)( 1 vp)6, 3,2()(ivt i （2） （3） 330,min)(, )(min)( 12122 lvpvtvt 550,min)(, )(min)( 13133 lvpvtvt 3)( 2 vp （4） 4 13,5min)(, )(min)( 23233 lvpvtvt 523,min)(, )(min)( 24244 lvpvtvt 523,min)(, )(min)( 25255 lvpvtvt v1 v2 v3 v4 v6 v5 3 5 2 2 4 2 4 2 1 4)( 3 vp（5） （6）844,6min)(, )(min)(

24、35355 lvpvtvt 5)( 4 vp5)( 5 vp 945,min)(, )(min)( 46466 lvpvtvt 725,min)(, )(min)( 56566 lvpvtvt 7)( 6 vp （7） （8） （9） （10） 反向追踪得反向追踪得v v1 1到到v v6 6的最短路为：的最短路为： 6521 vvvv 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 求从求从1到到8的最短路径的最短路径 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 x=1, w1=0 min c12,c14,c16=m

25、in 0+2,0+1,0+3=min 2,1,3=1 x=1,4, p4=1 p4=1 p1=0 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 x=1,4 min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2 x=1,2,4, p2=2 p1=0 p4=1 p2=2 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 x=1,2,4 min c16,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3 x=1,2,4,6, p6=

26、3 p2=2 p4=1 p1=0 p6=3 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 x=1,2,4,6 min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3 x=1,2,4,6,7, p7=3 p2=2 p4=1 p1=0 p6=3p7=3 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 x=1,2,4,6,7 min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6 x=1,2,4,5,6,7, p5=6 p

27、2=2 p4=1 p1=0 p6=3p7=3 p5=6 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 x=1,2,4,6,7 min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8 x=1,2,3,4,5,6,7, p3=8 p2=2 p4=1 p1=0 p6=3p7=3 p5=6 p3=8 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 x=1,2,3,4,6,7 min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10 x

28、=1,2,3,4,5,6,7,8, p8=10 p2=2 p4=1 p1=0 p6=3p7=3 p5=6 p3=8 p8=10 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 x=1,2,3,4,6,7,8 1到8的最短路径为1，4，7，5，8，长度为10。 p2=2 p4=1 p1=0 p6=3p7=3 p5=6 p3=8 p8=10 求从求从v1 到到 v8 的最短路线。的最短路线。 3 3 v v 1 1 v v 2 2 v v v v 4 4 v v 5 5 v v v v 6 6 7 7 v v 8 8 3 3 7 7 2 2 1 1 2 2 3

29、3 3 3 4 4 1 1 2 2 2 2 6 6 3 3 v v 1 1 v v 2 2 v v v v 4 4 v v 5 5 v v v v 6 6 7 7 v v 8 8 3 3 7 7 2 2 1 1 2 2 3 3 3 3 4 4 1 1 2 2 2 2 6 6 p p1 1=0=0 p p2 2=3=3 p p4 4=7=7 p p5 5=5=5 利用利用dijkstradijkstra算法算法 p p4 4=6=6 p p3 3=6=6 p p6 6=8=8 p p7 7=10=10 p p7 7=9=9 p p8 8=10=10 最短路：最短路：v1 v2 v5 v6 v8，

30、路长为，路长为10 3 3 v v 1 1 v v 2 2 v v v v 4 4 v v 5 5 v v v v 6 6 7 7 v v 8 8 3 3 7 7 2 2 1 1 2 2 3 3 3 3 4 4 1 1 2 2 2 2 6 6 利用标号法求解利用标号法求解 由此看到，此方法不仅求出了从由此看到，此方法不仅求出了从v v1 1 到到 v v8 8 的最短路长，的最短路长， 同时也求出了从同时也求出了从v v1 1 到到 任意一点任意一点 的最短路长。将从的最短路长。将从v v1 1 到到 任一点的最短路权标在图上，即可求出从任一点的最短路权标在图上，即可求出从v v1 1 到到

31、任一任一 点的最短路线。本例中点的最短路线。本例中v v1 1 到到 v v8 8 的最短路线是：的最短路线是： v v1 1 v v2 2 v v5 5 v v6 6 v v8 8 , ,路长路长1010 标号法标号法 1 v 2 v 3 v 4 v 5 v 9 v 8 v 7 v 6 v 6 2 3 1 2 1 6 4 10 3 6 2 3 4 2 10 1 v 3 v 2 v 5 v 8 v （二）、逐次逼近法（二）、逐次逼近法（带有负权的边时）（带有负权的边时）（不要求掌握）（不要求掌握） 算法的基本思路与步骤：算法的基本思路与步骤： 首先设任一点首先设任一点vi到任一点到任一点vj都

32、有一条弧。都有一条弧。 显然，从显然，从v1到到vj的最短路是从的最短路是从v1出发，沿着这条路到某个点出发，沿着这条路到某个点vi再沿弧再沿弧 (vi,vj)到到vj。则则v1到到vi的这条路必然也是的这条路必然也是v1到到vi的所有路中的最短路。设的所有路中的最短路。设p1j 表示从表示从v1到到vj的最短路长，的最短路长，p1i表示从表示从v1到到vi的最短路长，则有下列方程：的最短路长，则有下列方程： 开始时，令开始时，令 即用即用v1到到vj的直接距离做初始解。的直接距离做初始解。 从第二步起，使用递推公式：从第二步起，使用递推公式： 求求 ，当进行到第，当进行到第 t 步，若出现步

33、，若出现 则停止计算，则停止计算， 即为即为v1到各点的最短路长。到各点的最短路长。 min 11jii i j lpp ),2, 1( 1 )1( 1 njlp jj ）（nklpp ji k i i k j ,3,2min )1( 1 )( 1 )( 1 k j p ）（njpp t j t j ,2,1 )1( 1 )( 1 ）（njp t j ,2,1 )( 1 例二、例二、 1 8 v1 v2 v3 v4 v5 2 6 3 5 1 3 5 2 1 1 2 1 1 v6 v7 v8 3 7 v1v2v3v4v5v6v7v8 v10-1-23 v260 2 v3 -30-5 1 v48

34、0 2 v5 -1 0 v6 1017 v7 -1 0 v8 -3 -50 求图中求图中v v1 1到到 各点的最短路各点的最短路 p(1) 0 -1 -2 3 p(2) 0 -5 -2 -7 1 -1 5 p(3) 0 -5 -2 -7 -3 -1 -5 6 p(4) 0 -5 -2 -7 -3 -1 -5 6 ）（nklpp ji k i i k j ,3,2min )1( 1 )( 1 1 8 v1 v2 v3 v4 v5 2 6 3 5 1 3 5 2 1 1 2 1 1 v6 v7 v8 3 7 （v1，0） （ v3 ，-5） （ v1 ，-2） （ v3 ，-7） （ v2 ，-

35、3） （ v4 ，-5） （ v3 ，-1） （ v6 ，6） （ v1 ，-1） （ v1 ，3） 对于带有负权的边时，同样可以采用标号法进行求解对于带有负权的边时，同样可以采用标号法进行求解 例三、例三、已知某设备已知某设备5 5年内的购置费及各年的维修费如下表：年内的购置费及各年的维修费如下表： 求：求：5年内，哪些年初购置新设备，使年内，哪些年初购置新设备，使5年内的总费用最小。年内的总费用最小。 解：（解：（1 1）分析：可行的购置方案（更新计划）是很多的，）分析：可行的购置方案（更新计划）是很多的， 如：如： 1 1） 每年购置一台新的，则对应的费用为：每年购置一台新的，则对应的费

36、用为： 11+11+12+12+13 +5+5+5+5+5 = 84 2 ) 2 )第一年购置新的，一直用到第五年年底，则总费第一年购置新的，一直用到第五年年底，则总费 用为：用为： 11+5+6+8+11+18 = 59 显然不同的方案对应不同的费用。显然不同的方案对应不同的费用。 第第i i年度年度 1 2 3 4 5 购置费购置费 11 11 12 12 13 设备役龄设备役龄0-1 1-2 2-3 3-4 4-5 维修费用维修费用 5 6 8 11 18 （2）方法：将此问题用一个赋权有向图来描述，然后求）方法：将此问题用一个赋权有向图来描述，然后求 这个赋权有向图的最短路。这个赋权有

37、向图的最短路。 求解步骤：求解步骤： 1）画赋权有向图：）画赋权有向图： 设设 vi 表示第表示第i年初，年初，(vi ,vj )表示第表示第i 年初购买新设备用年初购买新设备用 到第到第j年初（年初（j-1年底），而年底），而wi j 表示相应费用，则表示相应费用，则5年的年的 一个更新计划相当于从一个更新计划相当于从v1 到到v6的一条路。的一条路。 2）求解）求解 （标号法）（标号法） w12 =11+5=16 w13 =11+5+6=22 w14 =11+5+6+8=30 w15 =11+5+6+8+11=41 w16 =11+5+6+8+11+18=59 w23 =11+5=16 w

38、24 =11+5+6=22 w25 =11+5+6+8=30 w26 =11+5+6+8+11=41 w45 =12+5=17 w46 =12+5+6=23 w56 =13+5=18 w34 =12+5=17 w35 =12+5+6=23 w36 =12+5+6+8=31 第第i i年度年度 1 2 3 4 5 购置费购置费 11 11 12 12 13 设备役龄设备役龄0-1 1-2 2-3 3-4 4-5 维修费用维修费用 5 6 8 11 18 例四、例四、 某工厂使用一种设备，这种设备在一定的年限内某工厂使用一种设备，这种设备在一定的年限内 随着时间的推移逐渐损坏。所以工厂在每年年初都

39、要决定设随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设 备是否更新。若购置设备，每年需支付购置费用；若继续使备是否更新。若购置设备，每年需支付购置费用；若继续使 用旧设备，需要支付维修与运行费用，而且随着设备的老化用旧设备，需要支付维修与运行费用，而且随着设备的老化 会逐年增加。计划期（五年）内中每年的购置费、维修费与会逐年增加。计划期（五年）内中每年的购置费、维修费与 运行费如表所示，工厂要制定今后五年设备更新计划，问采运行费如表所示，工厂要制定今后五年设备更新计划，问采 用何种方案才能使包括购置费、维修费与运行费在内的总费用何种方案才能使包括购置费、维修费与运行费在内的总费 用最小。

40、用最小。 年份年份1 12 23 34 45 5 购置费购置费18182020212123232424 使用年数使用年数0 01 11 12 22 23 33 34 44 45 5 维修费维修费5 57 7121218182525 年份年份1 12 23 34 45 5 购置费购置费18182020212123232424 使用年数使用年数0 01 11 12 22 23 33 34 44 45 5 维修费维修费5 57 7121218182525 28 v1 v2v3v4v5 v6 23 25 26 29 30 42 60 85 32 44 62 33 45 30 四、四、 最大流问题最大流

41、问题 （一）、（一）、 基本概念基本概念 1、设一个赋权有向图、设一个赋权有向图d=（v, e）,在在v中指定一个发点中指定一个发点vs和一和一 个收点个收点vt ,其它的点叫做中间点。对于其它的点叫做中间点。对于d中的每一个弧（中的每一个弧（vi , vj） e ,都有一个非负数都有一个非负数cij,叫做弧的容量。我们把这样的图叫做弧的容量。我们把这样的图d叫做一叫做一 个容量网络，简称网络，记做个容量网络，简称网络，记做d=（v，e，c）。）。 网络网络d上的流，是指定义在弧集合上的流，是指定义在弧集合e上的一个函数上的一个函数 其中其中f(vi ,vj) =fij 叫做弧叫做弧(vi，v

42、j)上的流量。上的流量。 ),( jiji fvvff 2、称满足下列条件的流为可行流：、称满足下列条件的流为可行流： （1）容量条件：对于每一个弧（）容量条件：对于每一个弧（vi ,vj）e 有有0 fij cij 。 （2）平衡条件：平衡条件： 对于发点对于发点vs和和对于收点对于收点vt ，有有 对于中间点，有对于中间点，有 evvevv t ji s istj wff ),(),( evvevv jkji jikj ff ),(),( 可行流中可行流中 fijcij 的弧叫做饱和弧，的弧叫做饱和弧，fijcij的弧叫做非饱和弧。的弧叫做非饱和弧。 fij0 的弧为非零流弧，的弧为非零流

43、弧，fij0 的弧叫做零流弧。的弧叫做零流弧。 2 v 1 v 3 v 4 v 5 v 6 v 7 v 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 图中图中 为零流弧，其余为非饱和弧。为零流弧，其余为非饱和弧。 ) , ( 63 vv 3、容量网络、容量网络g，若若 为网络中从为网络中从vs到到vt的一条链，给的一条链，给 定定 向为从向为从vs到到vt， 上的弧凡与上的弧凡与 方向相同的称为前向弧，凡与方向相同的称为前向弧，凡与 方向相反的称为后向弧，其集合分别用方向相反的称为后向弧，其集合

44、分别用 和和 表示。表示。 f 是一个可行流，如果满足：是一个可行流，如果满足： 则称则称 为从为从vs到到vt 的关于的关于f 的一条增广链。的一条增广链。 ),(0 ),(0 jijiji jijiji vvcf vvcf 推论推论 可行流可行流 f 是最大流的充分必要条件是不存在从是最大流的充分必要条件是不存在从vs到到vt 的关于的关于f 的一条可增广链。的一条可增广链。 即即 中的每一条弧都是非饱和弧中的每一条弧都是非饱和弧 即即 中的每一条弧都是非零流弧中的每一条弧都是非零流弧 2 v 1 v 3 v 4 v 5 v 6 v 7 v 13 (5) 9 (3) 4 (1) 5 (3)

45、 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 7766633232211 ),( ,),( ,),( ,),( ,vvvvvvvvvvvvv ),(),(),( 766321 vvvvvv ),( 23 vv 是一个增广链是一个增广链显然图中增广链不止一条显然图中增广链不止一条 4、容量网络、容量网络g =（v，e，c），），vs为始点，为始点，vt为终点。如为终点。如 果把果把v分成两个非空集合分成两个非空集合 ,使使 ，则所有，则所有 始点属于始点属于s，而终点属于而终点属于 的弧的集合，称为由的弧的集合，称为由s决定的截决定的截 集集,

46、记作记作 。截集。截集 中所有弧的容量之和，称为这中所有弧的容量之和，称为这 个截集的容量，记为个截集的容量，记为 。 ss ,svsv ts , s ),(ss ),(ss ),(ssc vs v1 v2v4 v3 vt 3 7 4 5 5 6 3 7 8 s 、),( 2 vvs s ),( 431t vvvvs ),(, ),( , ),(),( 32421 vvvvvvss s 18567),( 23241 lllssc s 2 v 1 v 3 v 4 v 5 v 6 v 7 v 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2)

47、 4 (1) 9 (5) 10 (1) ),(),(),(),( 75423121 vvvvvvvv 5211 ,vvvv 则截集为则截集为 76432 ,vvvvv 不不是是该该集集中中的的弧弧和和而而 ),( ),( 5423 vvvv 容量为容量为24 2 v 1 v 3 v 4 v 5 v 6 v 7 v 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 设设 ， 211 ,vvv 则截集为则截集为 765432 ,vvvvvv ),(),(),(),( 52423121 vvvvvvvv

48、容量为容量为20 不难证明，任何一个可行流的流量不难证明，任何一个可行流的流量 v(f) 都不会超过任一截都不会超过任一截 集的容量。即集的容量。即 v(f)=c 若对于一个可行流若对于一个可行流 f*,网络中有一个截集网络中有一个截集 ，使，使 则则 f* 必是最大流，而必是最大流，而 必定是必定是 g 的所有截集中容量的所有截集中容量 最小的一个，即最小截集。最小的一个，即最小截集。 最大流量最小截量定理：任一网络最大流量最小截量定理：任一网络g中，从中，从 vs 到到 vt 的最大的最大 流的流量等于分离流的流量等于分离 vs、vt 的最小截集的容量。的最小截集的容量。 ( ,)s s * (,)ss * ( *)(,)v