运筹学第6章图与网络分析.pptx

《运筹学第6章图与网络分析.pptx》由会员分享，可在线阅读，更多相关《运筹学第6章图与网络分析.pptx（138页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、BDACABCD哥尼斯堡七空桥哥尼斯堡七空桥一笔画问题一笔画问题第1页/共138页哈哈密密尔尔顿顿（HamiltonHamilton）回回路路是是十十九九世世纪纪英英国国数数学学家家哈哈密密顿顿提提出出，给给出出一一个个正正1212面面体体图图形形，共共有有2020个个顶顶点点表表示示2020个个城城市市，要要求求从从某某个个城城市市出出发发沿沿着着棱棱线线寻寻找找一一条条经经过过每每个个城城市市一一次次而而且且仅仅一一次次，最最后后回回到到原原处处的的周周游游世世界界线线路路（并并不不要要求求经经过过每条边）。每条边）。第2页/共138页第3页/共138页第4页/共138页第5页/共138页

2、第6页/共138页第7页/共138页第8页/共138页第9页/共138页第10页/共138页第11页/共138页第12页/共138页第13页/共138页第14页/共138页第15页/共138页第16页/共138页第17页/共138页第18页/共138页第19页/共138页有有有有7 7 7 7个个个个人人人人围围围围桌桌桌桌而而而而坐坐坐坐，如如如如果果果果要要要要求求求求每每每每次次次次相相相相邻邻邻邻的的的的人人人人都都都都与与与与以以以以前前前前完完完完全全全全不不不不同同同同，试试试试问问问问不不不不同同同同的的的的就就就就座座座座方方方方案案案案共共共共有多少种？有多少种？有多少种？

3、有多少种？用用用用顶顶顶顶点点点点表表表表示示示示人人人人，用用用用边边边边表表表表示示示示两两两两者者者者相相相相邻邻邻邻，因因因因为为为为最最最最初初初初任任任任何何何何两两两两个个个个人人人人都都都都允允允允许许许许相相相相邻邻邻邻，所所所所以以以以任任任任何何何何两两两两点点点点都都都都可以有边相连。可以有边相连。可以有边相连。可以有边相连。第20页/共138页1 12 23 37 76 64 45 5第21页/共138页1 12 23 37 76 64 45 5第22页/共138页1 12 23 37 76 64 45 5第23页/共138页1 12 23 37 76 64 45 5

4、第24页/共138页1 12 23 37 76 64 45 5第25页/共138页1 12 23 37 76 64 45 5第26页/共138页1 12 23 37 76 64 45 5第27页/共138页1 12 23 37 76 64 45 5第28页/共138页得到第一次就座方案是（得到第一次就座方案是（得到第一次就座方案是（得到第一次就座方案是（1 1 1 1，2 2 2 2，3 3 3 3，4 4 4 4，5 5 5 5，6 6 6 6，7 7 7 7，1 1 1 1），继续寻求第二次就座方案时就不允许这些顶点），继续寻求第二次就座方案时就不允许这些顶点），继续寻求第二次就座方案时就

5、不允许这些顶点），继续寻求第二次就座方案时就不允许这些顶点之间继续相邻，因此需要从图中删去这些边。之间继续相邻，因此需要从图中删去这些边。之间继续相邻，因此需要从图中删去这些边。之间继续相邻，因此需要从图中删去这些边。第29页/共138页1 12 23 37 76 64 45 5第30页/共138页1 12 23 37 76 64 45 5第31页/共138页1 12 23 37 76 64 45 5第32页/共138页1 12 23 37 76 64 45 5第33页/共138页1 12 23 37 76 64 45 5第34页/共138页1 12 23 37 76 64 45 5第35页/

6、共138页1 12 23 37 76 64 45 5第36页/共138页1 12 23 37 76 64 45 5第37页/共138页得出第二次就座方案是（得出第二次就座方案是（得出第二次就座方案是（得出第二次就座方案是（1 1 1 1，3 3 3 3，5 5 5 5，7 7 7 7，2 2 2 2，4 4 4 4，6 6 6 6，1 1 1 1），那么第三次就座方案就不允许这些顶点之间继），那么第三次就座方案就不允许这些顶点之间继），那么第三次就座方案就不允许这些顶点之间继），那么第三次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。续相邻，只能从图中删去这些边。续相邻，只能从图

7、中删去这些边。续相邻，只能从图中删去这些边。第38页/共138页1 12 23 37 76 64 45 5第39页/共138页1 12 23 37 76 64 45 5第40页/共138页1 12 23 37 76 64 45 5第41页/共138页1 12 23 37 76 64 45 5第42页/共138页1 12 23 37 76 64 45 5第43页/共138页1 12 23 37 76 64 45 5第44页/共138页1 12 23 37 76 64 45 5第45页/共138页1 12 23 37 76 64 45 5第46页/共138页得得到到第第三三次次就就座座方方案案是是

8、（1 1，4 4，7 7，3 3，6 6，2 2，5 5，1 1），那那么么第第四四次次就就座座方方案案就就不不允允许许这这些些顶顶点点之之间间继继续续相相邻邻，只只能能从从图图中中删删去去这这些些边边，只只留留下下7 7点点孤孤立立点点，所以该问题只有三个就座方案。所以该问题只有三个就座方案。第47页/共138页1 12 23 37 76 64 45 5第48页/共138页引论 图的用处 某公司的某公司的 组织机构设置图组织机构设置图总公司分公司工厂或办事处第49页/共138页一、一、图与网络的基本知识图与网络的基本知识（一）、（一）、图与网络的基本概念图与网络的基本概念 EADCB1、一个

9、图是由点和连线组成。（连线可带箭头，也可、一个图是由点和连线组成。（连线可带箭头，也可不带，前者叫弧，后者叫边）不带，前者叫弧，后者叫边）第50页/共138页一一个个图图是是由由点点集集 和和 中中元元素素的的无无序序对对的的一一个个集集合合 构构成成的的二二元元组组，记记为为G G=(=(V V，E E)，其其中中 V V 中中的的元元素素 叫叫做做顶顶点点，V 表表示示图图 G 的点集合；的点集合；E 中的元素中的元素 叫做边，叫做边，E表示图表示图 G 的边集合。的边集合。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例图图1第51页/共138页 2 2、如如果果一一

10、个个图图是是由由点点和和边边所所构构成成的的，则则称称其其为为无无向向图图，记记作作G G=(V V，E E)，连连接接点点的的边记作边记作 v vi i,v,vj j，或者或者 v vj j,v,vi i。3 3、如果一个图是由点和弧所构成的，那么称它为有向图，记作、如果一个图是由点和弧所构成的，那么称它为有向图，记作D D=(=(V,AV,A)，其中其中V V 表表示有向图示有向图D D 的点集合，的点集合，A A 表示有向图表示有向图D D 的弧集合。一条方向从的弧集合。一条方向从v vi i指向指向v vj j 的弧，记作的弧，记作(v vi i,v vj j)。v4v6v1v2v3v

11、5V=v1,v2,v3,v4,v5,v6，A=(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)图图2第52页/共138页 4 4、一条边的两个端点是相同的、一条边的两个端点是相同的,那么称为这条边是环。那么称为这条边是环。5 5、如果两个端点之间有两条以上的边，那么称为它们、如果两个端点之间有两条以上的边，那么称为它们为多重边。为多重边。6 6、一个无环，无多重边的图称为简单图，一个无环，、一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。有多重边的图称为多重图。7、每一对顶点间都有边相连的无向简单

12、图称为完全图。、每一对顶点间都有边相连的无向简单图称为完全图。有向完全图则是指任意两个顶点之间有且仅有一条有有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。向边的简单图。第53页/共138页v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10 度为零的点称为弧立点，度为度为零的点称为弧立点，度为1 1的点称为悬挂点。悬挂的点称为悬挂点。悬挂点的关联边称为悬挂边。度为奇数的点称为奇点，度为偶点的关联边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。数的点称为偶点。8 8、以点、以点v v为端点的边的个数称为点为端点的边的个数称为点v v 的度（次），记作的度（次

13、），记作 。图中图中 d(v1)=4，d(v6)=4（环计两度环计两度）第54页/共138页 定理定理1 1 所有顶点度数之和等于所有边数的所有顶点度数之和等于所有边数的2 2倍。倍。定理定理定理定理2 2 2 2 在任一图中，奇点的个数必为偶数。在任一图中，奇点的个数必为偶数。所有顶点的入次之和等于所有顶点的出次之和。所有顶点的入次之和等于所有顶点的出次之和。有有向向图图中中，以以 v vi i 为为始始点点的的边边数数称称为为点点v vi i的的出出次次，用用 表示表示 ；以；以 v vi i 为终点的边数称为点为终点的边数称为点v vi i 的入次，的入次，用用 表示；表示；v vi i

14、 点的出次和入次之和就是该点的次。点的出次和入次之和就是该点的次。第55页/共138页 9 9 9 9、设、设、设、设 GG1 1=（VV1 1,E,E1 1），），），），GG2 2=（VV2 2,E,E2 2）如果如果 V2 V1,E2 E1 称称 G2 是是G1 的子图；如果的子图；如果 V2=V1,E2 E1 称称 G2是是 G1的部分图或支撑子图。的部分图或支撑子图。v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图子图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图支撑子图第56

15、页/共138页 在实际应用中，给定一个图在实际应用中，给定一个图G=（V，E）或有向或有向图图D=（V，A），在在V中指定两个点，一个称为始点中指定两个点，一个称为始点（或发点），记作（或发点），记作v1，一个称为终点（或收点），记作一个称为终点（或收点），记作vn，其余的点称为中间点。对每一条弧其余的点称为中间点。对每一条弧 ，对应一个数对应一个数 ，称为弧上的，称为弧上的“权权”。通常把这种赋权。通常把这种赋权的图称为网络。的图称为网络。10 10、由两两相邻的点及其相关联的边构成的点边序列、由两两相邻的点及其相关联的边构成的点边序列称为链。称为链。如如:v v0 0 ，e e1 1，v

16、v1 1，e e2 2，v v2 2，e e3 3 ，v v3 3,v,vn-1n-1,e en n ，v vn n，记作（记作（v v0 0，v v1 1 ，v v2 2，v v3 3 ,v vn-1n-1 ，v vn n ），），第57页/共138页e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e10 11 11、图中任意两点之间均至少有一条通路，则称此图、图中任意两点之间均至少有一条通路，则称此图为连通图，否则称为不连通图。为连通图，否则称为不连通图。其链长为其链长为 n，其中其中 v0，vn 分别称为链的起点和终点分别称为链的起点和终点 。若链中所含的边均不相同，则称此链

17、为简单链；所含的。若链中所含的边均不相同，则称此链为简单链；所含的点均不相同的链称为初等链点均不相同的链称为初等链,也称通路。也称通路。第58页/共138页（二）、（二）、图的矩阵表示图的矩阵表示对于网络（赋权图）对于网络（赋权图）G=（V，E），其中边其中边有权有权 ，构造矩阵，构造矩阵 ，其中：，其中：称矩阵称矩阵A A为网络为网络G G的权矩阵。的权矩阵。设图设图G=（V，E）中顶点的个数为中顶点的个数为n，构造一个构造一个矩阵矩阵 ，其中：，其中：称矩阵称矩阵A A为网络为网络G G的邻接矩阵。的邻接矩阵。第59页/共138页例例权矩阵为：权矩阵为：邻接矩阵为：邻接矩阵为：v5v1v2

18、v3v4v64332256437第60页/共138页 二、二、树及最小树问题树及最小树问题 已已知知有有六六个个城城市市，它它们们之之间间 要要架架设设电电话话线线，要要求求任任意意两两个个城城市市均均可可以以互互相相通通话话，并并且且电电话话线线的的总总长长度最短。度最短。v1v2v3v4v5v6 1 1、一个连通的无圈的无向图叫做树。、一个连通的无圈的无向图叫做树。树中次为树中次为1 1的点称为树叶，次大于的点称为树叶，次大于1 1的点称为分支点。的点称为分支点。第61页/共138页 树的性质：树的性质：树的性质：树的性质：（1 1）树必连通，但无回路（圈）。树必连通，但无回路（圈）。（2

19、 2）n个顶点的树必有个顶点的树必有n-1条边条边。（3 3）树树中任意两个顶点之间，恰有且仅有一条链中任意两个顶点之间，恰有且仅有一条链（初等链）。（初等链）。（4 4）树）树连通，但去掉任一条边，连通，但去掉任一条边，必变为不连通。必变为不连通。（5 5）树树无回路（圈），但不相邻的两个点之间无回路（圈），但不相邻的两个点之间加一条边，恰得到一个回路（圈）。加一条边，恰得到一个回路（圈）。v1v2v3v4v5v6第62页/共138页一个图一个图G 有生成树的充要条件是有生成树的充要条件是G是连通图。是连通图。v1v2v3v4v5v1v2v3v4v5 2 2、设图设图 是图是图G=(V,E)

20、的一支撑子图，的一支撑子图，如果图如果图 是一个树是一个树,那么称那么称K 是是G 的一个生成的一个生成树（支撑树），或简称为图树（支撑树），或简称为图G 的树。图的树。图G中属于生成树的中属于生成树的边称为树枝，不在生成树中的边称为弦。边称为树枝，不在生成树中的边称为弦。第63页/共138页（一）（一）破圈法：在图中任选一个圈，从这个圈破圈法：在图中任选一个圈，从这个圈中去掉一条边。在余下的图中重复这个步骤，中去掉一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。直到得到一不含圈的图为止。第64页/共138页第65页/共138页用破圈法求出下图的一个生成树。用破圈法求出下图的一个生

21、成树。v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8第66页/共138页（二）（二）避圈法：开始选一条边，以后每一步中，避圈法：开始选一条边，以后每一步中，总从未被选取的边中选出一条与已选边不构成总从未被选取的边中选出一条与已选边不构成圈的边，重复这个过程，直到不能进行为止。圈的边，重复这个过程，直到不能进行为止。第67页/共138页v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5第68页/共138页根据破圈法和避圈法两种方式得到了图的两个不同的

22、生成树，由此可以看到连通图的生成树不是唯一的。第69页/共138页3 3、最小生成树问题、最小生成树问题 一一棵棵生生成成树树所所有有树树枝枝上上权权的的总总和和为为这这个个生生成成树树的权的权。具有最小权的生成树，称为最小生成树。具有最小权的生成树，称为最小生成树。求求赋赋权权图图G G的的最最小小支支撑撑树树的的方方法法也也有有两两种种，“破破圈法圈法”和和“避圈法避圈法”。破破圈圈法法：在在原原图图中中，任任选选一一个个圈圈，从从圈圈中中去去掉掉权权最最大大的的一一条条边边。在在余余下下的的图图中中重重复复这这个个步步骤骤，直直到到得得到到一一不不含含圈圈的的图图为止。为止。655172

23、344v1v2v3v4v5v6第70页/共138页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第71页/共138页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第72页/共138页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323第73页/共138页v1v1v7v7v4v4v3v3v2v2v5v5v6v620201

24、5159 9161625253 3282817174 41 12323第74页/共138页v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323第75页/共138页v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323第76页/共138页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323第77页/共138页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282

25、817174 41 12323第78页/共138页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323第79页/共138页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323第80页/共138页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 317174 41 12323总造价总造价=1+4+9+3+17+23=57=1+4+9+3+17+23=57第81页/共138页v1v2v3v4v514231352避避圈圈法法：开开始始选选一一条条权权最最小小的的边边，以以后后每每一

26、一步步中中，总总从从未未被被选选取取的的边边中中选选一一条条权权尽尽可可能能小小，且且与与已已选选边不构成圈的边。边不构成圈的边。第82页/共138页 某某六六个个城城市市之之间间的的道道路路网网如如图图 所所示示，要要求求沿沿着着已已知知长长度度的的道道路路联联结结六六个个城城市市的的电电话话线线网网，使使电电话话线线的的总总长长度最短。度最短。v1v2v3v4v5v66515723445v1v2v3v4v5v61234第83页/共138页 最短路的一般提法为：设为连通图，图中各边有权（表示之间没有边），为图中任意两点，求一条路，使它为从到的所有路中总权最短。即：最小。(一)、狄克斯屈拉(D

27、ijkstra)算法适用于wij0，给出了从vs到任意一个点vj的最短路。三三 、最短路问题、最短路问题第84页/共138页算法步骤：1.给始点vs以P标号，这表示从vs到 vs的最短距离为0，其余节点均给T标号，。2.设节点vi 为刚得到P标号的点，考虑点vj，其中，且vj为T标号。对vj的T标号进行如下修改：3.比较所有具有T标号的节点，把最小者改为P标号，即：当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。第85页/共138页例一、用Dijkstra算法求下图从v1到v6的最短路。v1v2v3v4v6v5352242421 解（

28、1）首先给v1以P标号，给其余所有点T标号。（2）（3)（4）第86页/共138页v1v2v3v4v6v5352242421（5）（6）（7）（8）（9）（10）反向追踪得v1到v6的最短路为：第87页/共138页237184566134105275934682练习练习 作业作业:求从求从1到到8的最短路径的最短路径第88页/共138页237184566134105275934682X=1,w1=0min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4,p4=1p4=1p1=0第89页/共138页237184566134105275934682X=1,

29、4min 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=2第90页/共138页237184566134105275934682X=1,2,4min 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=3第91页/共138页237184566134105275934682X=1,2,4,6min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3

30、X=1,2,4,6,7,p7=3p2=2p4=1p1=0p6=3p7=3第92页/共138页237184566134105275934682X=1,2,4,6,7min 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=6第93页/共138页237184566134105275934682X=1,2,4,6,7min 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

31、=2p4=1p1=0p6=3p7=3p5=6p3=8第94页/共138页237184566134105275934682X=1,2,3,4,6,7min 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=10第95页/共138页237184566134105275934682X=1,2,3,4,6,7,81到8的最短路径为1，4，7，5，8，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10第96页/共138页求从求从V V

32、1 1 到到 V V8 8 的最短路线。的最短路线。第97页/共138页V1V2V3V4V5V6V7V8P=0T=+T=+T=+T=+T=+T=+T=+P=T=3T=+T=7T=+T=+T=+T=+T=6T=7P=T=5T=+T=+T=+P=T=6T=6T=8T=+T=+P=T=6T=8T=9T=12P=T=8T=10T=10P=T=9T=11再无其它再无其它T标号，所以标号，所以T(V8)=P(V8)=10;minL()=10P=T=10第98页/共138页由此看到，此方法不仅求出了从V1到V8的最短路长，同时也求出了从V1到任意一点的最短路长。将从V1到任一点的最短路权标在图上，即可求出从

33、V1到任一点的最短路线。本例中V1到V8的最短路线是：v1v2v5v6v8第99页/共138页623121641036234210第100页/共138页（二）、逐次逼近法算法的基本思路与步骤：首先设任一点vi到任一点vj都有一条弧。显然，从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi,vj)到vj。则v1到vi的这条路必然也是v1到vi的所有路中的最短路。设P1j表示从v1到vj的最短路长，P1i表示从v1到vi的最短路长，则有下列方程：开始时，令即用v1到vj的直接距离做初始解。从第二步起，使用递推公式：求，当进行到第t步，若出现则停止计算，即为v1到各点的最短路长。第

34、101页/共138页例二、18v1v2v3v4v52635135211211v6v7v837v1v2v3v4v5v6v7v8P(1)P(2)P(3)P(4)v10-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求图中求图中v v1 1到到各点的最短路各点的最短路第102页/共138页18v1v2v3v4v52635135211211v6v7v837（0，0）（v3，-5）（v1，-2）（v3，-7）（v2，-3）（v4，-5）（v3，-1）（v6，6）第103页

35、/共138页例三、求：例三、求：5 5年内，哪些年初购置新设备，使年内，哪些年初购置新设备，使5 5年内的总费用最年内的总费用最小。小。解：（解：（1 1）分析：可行的购置方案（更新计划）是很多的，）分析：可行的购置方案（更新计划）是很多的，如：如：1 1）每年购置一台新的，则对应的费用为：每年购置一台新的，则对应的费用为：11+11+12+12+13+5+5+5+5+5=84 2 2)第第一一年年购购置置新新的的，一一直直用用到到第第五五年年年年底底，则则总总费费用用为：为：11+5+6+8+11+18=59 显然不同的方案对应不同的费用。显然不同的方案对应不同的费用。第第i i年度年度 1

36、2345购置费购置费1111121213设备役龄设备役龄0-11-22-33-44-5维修费用维修费用 5681118第104页/共138页 （2 2）方方法法：将将此此问问题题用用一一个个赋赋权权有有向向图图来来描描述述，然然后后求求这个赋权有向图的最短路。这个赋权有向图的最短路。求解步骤：求解步骤：1 1）画赋权有向图：）画赋权有向图：设设 V Vi i 表表示示第第i i年年初初，(V Vi i ,V,Vj j )表表示示第第i i 年年初初购购买买新新设设备备用用到到第第j j年年初初（j-1j-1年年底底），而而W Wi i j j 表表示示相相应应费费用用，则则5 5年的一个更新计

37、划相当于从年的一个更新计划相当于从V V1 1 到到V V6 6的一条路。的一条路。2 2）求解）求解 （标号法）（标号法）第105页/共138页W12=11+5=16W13=11+5+6=22W14=11+5+6+8=30W15=11+5+6+8+11=41W16=11+5+6+8+11+18=59 W23=11+5=16W24=11+5+6=22W25=11+5+6+8=30W26=11+5+6+8+11=41W45=12+5=17W46=12+5+6=23W56=13+5=18W34=12+5=17W35=12+5+6=23W36=12+5+6+8=31第106页/共138页 例四、例四

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

39、厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。维修费与运行费在内的总费用最小。年份年份1 12 23 34 45 5购置费购置费18182020212123232424使用年数使用年数0 01 11 12 22 23 33 34 44 45 5维修费维修费5 57 7121218182525第107页/共138页年份年份1 12 23 34 45 5购置费购置费18182020212123232424使用年数使用年数0 01 11 12 22 23 33 34 44 45 5维修费维修费5 57 712121818252528v1v2v3v4v5

40、v62325262930426085324462334530第108页/共138页四、最大流问题（一）、基本概念1、设一个赋权有向图D=（V,E）,在V中指定一个发点vs和一个收点vt,其它的点叫做中间点。对于D中的每一个弧（vi,vj）E,都有一个非负数cij,叫做弧的容量。我们把这样的图D叫做一个容量网络，简称网络，记做D=（V，E，C）。网络D上的流，是指定义在弧集合E上的一个函数其中f(vi,vj)=fij 叫做弧(vi，vj)上的流量。第109页/共138页2、称满足下列条件的流为可行流：（1）容量条件：对于每一个弧（vi,vj）E有 0 fij cij。（2）平衡条件：对于发点vs

41、，有对于收点vt，有对于中间点，有可行流中 fijcij 的弧叫做饱和弧，fijcij的弧叫做非饱和弧。fij0 的弧为非零流弧，fij0 的弧叫做零流弧。第110页/共138页13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)图中图中为零流弧，其余为非饱和弧。为零流弧，其余为非饱和弧。第111页/共138页 3、容量网络G，若 为网络中从vs到vt的一条链，给 定向为从vs到vt，上的弧凡与 方向相同的称为前向弧，凡与 方向相反的称为后向弧，其集合分别用 和 表示。f 是一个可行流，如果满足：则称 为从vs到vt 的关于f 的一条增广链。推论

42、 可行流f 是最大流的充分必要条件是不存在从vs到vt 的关于f 的一条可增广链。即即中的每一条弧都是非饱和弧中的每一条弧都是非饱和弧即即中的每一条弧都是非零流弧中的每一条弧都是非零流弧第112页/共138页13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)是一个增广链是一个增广链显然图中增广链不止一条显然图中增广链不止一条第113页/共138页 4、容量网络G=（V，E，C），vs为始点，vt为终点。如果把V分成两个非空集合 使 ，则所有始点属于S，而终点属于 的弧的集合，称为由S决定的截集,记作 。截集 中所有弧的容量之和，称为这个截集的容

43、量，记为 。vsv1v2v4v3vt374556378S第114页/共138页13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)设设，则截集为则截集为容量为容量为24第115页/共138页13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)设设，则截集为则截集为容量为容量为20第116页/共138页（二）、求最大流的标号法 标号过程：1 给发点vs 标号（0，+）。2 取一个已标号的点vi，对于vi一切未标号的邻接点vj 按下列规则处理：（1）如果边 ，且 ，那么给vj 标号 ，其中：（2）如果边

44、 ，且 ，那么给vj 标号 ，其中：3重复步骤2，直到vt被标号或标号过程无法进行下去，则标号结束。若vt被标号，则存在一条增广链，转调整过程；若vt未被标号，而标号过程无法进行下去，这时的可行流就是最大流。第117页/共138页调整过程设1令 2去掉所有标号，回到第一步，对可行流重新标号。第118页/共138页 求下图所示网络中的最大流，弧旁数为(1,1)v2v1v4v3vsvt(3,3)(5,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)(1,1)v2v1v4v3vsvt(3,3)(5,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)（0，+）（-v1,1

45、）（+vs,4）（-v2，1）（+v2，1）(+v3，1)第119页/共138页(1,0)v2v1v4v3vsvt(3,3)(5,2)(1,0)(4,3)(2,2)(3,0)(5,3)(2,2)(1,0)v2v1v4v3vsvt(3,3)(5,2)(1,0)(4,3)(2,2)(3,0)(5,3)(2,2)（0，+）（+vs,3）最小截集最小截集第120页/共138页13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)第121页/共138页13(11)9(9)4(0)5(5)6(6)5(5)5(4)5(4)4(4)4(3)9(9)10(7)截集截

46、集1 1截集截集2 2最小截量为：最小截量为：9+6+5=20第122页/共138页70（70）70（50）130（100）150（130）150（150）50（20）50（50）120（30）100（100）（120）（230）（150）（200）第123页/共138页第五节最小费用最大流问题定义已知网络G=（V，E，C，d），f是G上 的 一 个 可 行 流，为 一 条 从 vs到 vt的 增 广 链，称为链的费用。若 *是从vs到vt的增广链中费用最小的增广链，则称 *是最小费用增广链。结论：如果可行流 f在流量为W(f)的所有可行流中的费用最小，并且 *是关于f 的所有增广链中的费用最

47、小的增广链，那么沿增广链 *调整可行流f，得到的新可行流f*也是流量为W(f*)的所有可行流中的最小费用流。当f*是最大流时，就是最小费用最大流。第124页/共138页寻找关于f 的最小费用增广链：构造一个关于f 的赋权有向图L(f)，其顶点是原网络G的顶点，而将G中的每一条弧(vi,vj)变成两个相反方向的弧（vi，vj）和(vj,vi)，并且定义图中弧的权lij为：1.当 ，令 2.当（vj，vi）为原来网络G中（vi，vj）的反向弧，令 在网络G中寻找关于f 的最小费用增广链等价于在L(f)中寻求从vs 到vt 的最短路。第125页/共138页步骤：（1）取零流为初始可行流，f(0)=0

48、。（2）一般地，如果在第k-1步得到最小费用流 f(k-1)，则构造图 L(f(k-1)。（3）在L(f(k-1)中，寻求从vs到vt的最短路。若不存在最短路，则f(k-1)就是最小费用最大流；否则转(4)。（4）如果存在最短路，则在可行流f(k1)的图中得到与此最短路相对应的增广链，在增广链上，对f(k1)进行调整，调整量为：第126页/共138页令得到新可行流f(k)。对f(k)重复上面步骤，返回（2）。例8.11求网络的最小费用最大流，弧旁权是（bij,cij）(3,2)vsv2v1vtv3(1,4)(6,7)(4,8)(1,6)(2,5)(2,3)第127页/共138页3 vsv2v1

49、vtv31 64 12 2(1)L(f(0)(3,2)vsv2v1vtv3(1,4)(6,7)(4,8)(1,6)(2,5)(2,3)0vsv2v1vtv3300333(2)f(1)1=3W(f(1)=31(3)L(f(1)2 3vsv2v1vtv31 64 12 12第128页/共138页1vsv2v1vtv3400343(4)f(2)2=1W(f(2)=4(3,2)vsv2v1vtv3(1,4)(6,7)(4,8)(1,6)(2,5)(2,3)(5)L(f(2)3 vsv2v1vtv31 4 12 2 231661vsv2v1vtv3401453(6)f(3)3=1W(f(3)=5第129

50、页/共138页(7)L(f(3)vsv2v1vtv33 1 4 1-2 2 3161vsv2v1vtv3434450(8)f(4)4=3W(f(4)=80vsv2v1vtv34455505=1W(f(5)=9(10)f(5)1-2 31vsv2v1vtv33 4 12 6(9)L(f(4)-4-6第130页/共138页31 2 14(11)L(f(5)12 64vsv2v1vtv36第131页/共138页第六节中国邮递员问题 一、欧拉回路与道路定义 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。具有欧拉回路