运筹学图与网络1qh.ppt

《运筹学图与网络1qh.ppt》由会员分享，可在线阅读，更多相关《运筹学图与网络1qh.ppt（201页珍藏版）》请在三一办公上搜索。

1、第十章 图与网络分析,引言 图论是专门研究图的理论的一门数学分支，属于离散数学范畴，与运筹学有交叉，它有200多年历史，大体可划分为三个阶段：第一阶段是从十八世纪中叶到十九世纪中叶，处于萌芽阶段，多数问题为游戏而产生，最有代表性的工作是所谓的Euler七桥问题(1736年)，即一笔画问题。,第二阶段是从十九世纪中叶到二十世纪中叶，这时，图论问题大量出现，如Hamilton问题，地图染色的四色问题以及可平面性问题等，这时，也出现用图解决实际问题，如Cayley把树应用于化学领域，Kirchhoff用树去研究电网络等.,第三阶段是二十世纪中叶以后，由生产管理、军事、交通、运输、计算机网络等方面提出

2、实际问题，以及大型计算机使大规模问题的求解成为可能，特别是以Ford和Fulkerson建立的网络流理论，与线性规划、动态规划等优化理论和方法相互渗透，促进了图论对实际问题的应用。,例10-1：哥尼斯堡七桥问题 哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？,A,B,C,D,最后，数学家Euler在1736年巧妙地给出了这个问题的答案，并因此奠定了图论的基础，Euler把A、B、C、D四块陆地分别收缩成四个顶点，把桥表示成

3、连接对应顶点之间的边，问题转化为从任意一点出发，能不能经过各边一次且仅一次，最后返回该点。这就是著名的Euler问题。,A,C,B,D,例10-2：有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？用顶点表示人，用边表示两者相邻，因为最初任何两个人都允许相邻，所以任何两点都可以有边相连。,1,2,3,7,6,4,5,假定第一次就座方案是（1，2，3，4，5，6，7，1），那么第二次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2

4、,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,假定第二次就座方案是（1，3，5，7，2，4，6，1），那么第三次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,假定第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边，只留下7点孤立点

5、，所以该问题只有三个就座方案。,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,例10-3：哈密顿（Hamilton）回路是十九世纪英国数学家哈密顿提出，给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处的周游世界线路（并不要求经过每条边）。,一.有甲、乙、丙、丁、戊、己6名运动员报名参加A，B，C，D，E，F,6项比赛。下表给出6个运动员报名

6、参加的比赛项目。问6个项目比赛顺序如何安排，做到每名运动员不连续参加两项比赛。,甲 乙 丙 丁 戊 己,A B C D E F,解:比赛项目作为点,两个比赛项目由同一个人参加连一边.如图:,A,B,D,F,C,E,比赛顺序可安排A-C-B-F-E-D 或A-F-B-C-D-E,甲 乙 丙 丁 戊 己,A B C D E F,10.1 图的基本概念 图论是专门研究图的理论的一门数学分支，主要研究点和线之间的 几何关系。,定义：（图）设G=（V，E，）其中：V=（v1，v2，.vm）是m个顶点集合；E=（e1，e2，.en）是n条边集合。是描述边与顶点之间关系的函数,称G=（V，E，）为 一个图，

7、如果它满足：（1）V非空；（2）E是一个不与V 中顶点相交的边集合；（3）是关联函数。V，E，称为图的三要素。,说明：（1）V非空，即没有顶点的图不讨论；（2）E无非空条件，即允许没有边；（3）条件（2）是指点只在边的端点 处相交；（4）任一条边必须与一对顶点关联，反之不然。,v1,v3,v2,v4,v5,v1,v3,v2,v4,v5,有向图,v1,v3,v2,v4,v6,v5,e1,e3,e5,e6,e4,e8,e7,e2,例10-5,V=（v1，v2，.v6）E=（e1，e2，.e8）（e1）=（v1，v2）（e2）=（v1，v2）（e7）=（v3，v5）（e8）=（v4，v4）,次（度）

8、：与顶点关联的边数。简单图：没有环和重边的图。悬挂点：次为1的点。悬挂边：次为1的边。孤立点：次为0的点。(e8)=(v4，v4),称为自回路(环)；v6是孤立点，v5为悬挂点，e7为悬挂边，顶点v3的次为4，顶点v2的次为3。,定理1：在一个图中，所有顶点次的和等于边的两倍。,定理8-1：在一个图中，所有顶点次的和等于边的两倍。定理2：在任意一个图中，奇顶点的个数必为偶数。证明:设V1和V2分别为G中奇点和偶点的集合,定理8-1：在一个图中，所有顶点次的和等于边的两倍。定理8-2：在任意一个图中，奇顶点的个数必为偶数。注意：一个图的形状并不唯一。但它的三要素是不能变的。,注意：一个图的形状并

9、不唯一。但它的三要素是不能变的。例如：这两个图均为K4,v1,v2,v3,v4,v1,v2,v3,v4,定义：设G=（V，E，）和G1=（V1，E1，1）。如果V1 V，E1 E则称G1为G的子图；如果G1=（V1，E1，1）是G=（V，E，）子图，并且V1=V，则称G1为G的生成子图；,如果V1 V，E1 是E中所有端点属于V1的边组成的集合，则称G1是G的关于V1的导出子图；如果G1=（V1，E1，1）是G=（V，E，）子图，并且V1=V，则称G1为G的生成（支撑）子图。,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,v1,v5,v4,v2,e1,e5,e3

10、,（a）的子图,v1,v5,v4,v2,v3,e8,e6,e5,e2,（a）的生成子图,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,v1,v5,v4,v2,e1,e8,e7,e6,e5,e4,e3,（a）的导出子图,定义（简单图）如果图中任意两个顶点之间至多有一条边，则称为简单图，否则称为多重图。即:无环、无重边的图。,定义（简单图）如果图中任意两个顶点之间至多有一条边，则称为简单图，否则称为多重图。定义（有向图）如果图中每一条边都规定了方向，则称为有向图。有向图去掉箭头得到的图称为基础图。,定义（链）如果图中的某些点、边可以排列成点和边的交错序列，则称此为一

11、条链。,定义（链）如果图中的某些点、边可以排列成点和边的交错序列，则称此为一条链。定义（圈）如一条链中起点和终点重合，则称此为一条圈。,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向图,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向图,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向图,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向图,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向图,v1,v5,v4,v2,v3,e1

12、,e8,e7,e6,e5,e4,e3,e2,有向图,链（路）,初等链（点不同）,简单链（边不同）,v1,v5,v4,v2,e1,e7,e6,e3,v1,v5,v4,v2,e1,e7,e6,e3,v1,v5,v4,v2,e1,e7,e6,e3,v1,v5,v4,v2,e1,e7,e6,e3,圈（回路）,连通图：图中任何两个点之间必有一条链。否则，称为不连通图。,v1,v5,v4,v2,v3,e1,e7,e6,e5,e4,e3,e2,v6,v7,v8,二、图的矩阵表示 一个图非常直观，但是不容易计算，特别不容易在计算机上进行计算，一个有效的解决办法是将图表示成矩阵形式，通常采用的矩阵是邻接矩阵、边

13、长邻接矩阵、弧长矩阵和关联矩阵。,1 邻接矩阵 邻接矩阵A表示图G的顶点之间的邻接关系，它是一个nn的矩阵，如果两个顶点之间有边相联时，记为1，否则为0。,v1,v2,v3,v4,v1 v2 v3 v4 v1 0 1 1 1v2 1 1 1 0v3 1 1 0 1v4 1 0 1 0,无向图的邻接矩阵是对称矩阵。,v1,v2,v3,v4,v1,v5,v4,v3,v2,也可以对有向图,v1 v2 v3 v4 v5v1 0 0 0 1 1v2 1 0 0 1 0v3 0 1 1 0 0v4 0 1 1 0 1v5 1 0 0 1 0,二、边长邻接矩阵 在图的各边上一个数量指标，具体表示这条边的权（

14、距离，单价，通过能力等）赋权图或网络。无向网络；有向网络；混合网络；边权网络；点权网络；以边长代替邻接矩阵中的元素得到边长邻接矩阵。,v1,v2,v3,v4,2,5,6,4,3,4,v1 v2 v3 v4 v1 0 2 5 6v2 2 4 3 v3 5 3 0 4v4 6 4 0,其中表示两点之间不能连接。,3 弧长矩阵 对有向图的弧可以用弧长矩阵来表示。其中表示两点之间没有弧连接。,v1,v5,v4,v3,v2,1,4,2,3,2,2,6,1,2,v1 v2 v3 v4 v5v1 0 1 2v2 0 2 4v3 2 0 1 v4 3 2 0 6v5 0,4 关联矩阵关联矩阵B揭示了图G的顶点

15、和边之间的关联关系，它是一个nxm矩阵。1（vi，vk）=ejBij=-1（vk，vi）=ej 0 其他,v1,v2,v4,v3,e1,e2,e4,e3,e7,e5,e6,e1 e2 e3 e4 e5 e6 e7v1 1-1 1 0 0 0 0v2 0 0-1-1-1 0 0v3 0 1 0 1 0 1-1v4-1 0 0 0 1-1 1,对无向图不存在-1 元素。,10-2 最优树问题（或最小树）树是一类极其简单而很有用的图。定义（链）如果图中的某些点、边可以排列成点和边的交错序列，则称此为一条链。,定义（链）如果图中的某些点、边可以排列成点和边的交错序列，则称此为一条链。定义（圈）如一条链

16、中起点和终点重合，则称此为一条圈。,定义（连通图）如果图中的任意两点之间至少存在一条通路，则称图为连通图，否则为不连通图。,定义（连通图）如果图中的任意两点之间至少存在一条通路，则称图为连通图，否则为不连通图。定义（树）一个无圈的连通图称为树。如果一个无圈的图中每一个分支都是树，则称图为森林。,定理3：设图G=(V,E)是一个树，顶点个数,则G中至少有两个悬挂点。证明：设 是G中含边数最多的初等链。往证 是悬挂点。若，则存在边 因为G为树，不含圈，故不在P上。是比P更长的初等链。矛盾。定理4：设图G=(V,E)是一个树的充分必要条件是G不含圈，且恰有 条边。证明：必要性：用数学归纳法：时，显然

17、成立。设对 时也成立。设图G含n+1个点，由定理3，G含悬挂点，考虑图，有充分性：往证G为连通图，若G不为连通图，则有s（s2）个连通分图。每一个都连通不含圈，即为树。,矛盾,定理5：设图G=(V,E)是一个树的充分必要条件是G是连通图，且证明：必要性：由定理4即得。充分性：往证G不含圈。对点用数学归纳法：时，显然成立。设对 时也成立。设图G含n+1个点，G必含悬挂点。否则，设 是G的悬挂点，考虑 仍为连通图，由归纳假设知 不含圈，则G必不含圈。定理6：设图G=(V,E)是一个树的充分必要条件是G的任意顶点之间恰有一条链。,矛盾,（1）G不含圈（2）G是连通图（3）（4）图G=(V,E)是一个

18、树上述条件有两个成立，就推出其余条件成立。,树的性质：1 在图中任意两点之间必有一条而且只有一条通路。,树的性质：1 在图中任意两点之间必有一条而且只有一条通路。2 在图中划去一条边，则图不连通。树是边最少的连通图,树的性质：1 在图中任意两点之间必有一条而且只有一条通路。2 在图中划去一条边，则图不连通。3 在图中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。,树的性质：1 在图中任意两点之间必有一条而且只有一条通路。2 在图中划去一条边，则图不连通。3 在图中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。4 图中边数有n=p-1（p为顶点数）,a,b,c,f,e,d,h,g,例

19、10-6,b,f,e,d,b,f,d,g,b,c,e,d,a,b,c,h,a,f,d,g,定义（生成树）如果图T是G的一个生成子图，而且T又是一棵树，则称图T为一棵生成树。对于分离（不连通图）图，则称为生成森林。一个子图与生成树的区别是：子图与原图相比少弧又少点，生成树与原图相比少弧不少点。,定理 图 G有生成树的充分必要条件为图是连通图。定义（最优树）在赋权图G中，一棵生成树所有树枝上权的和，称为生成树的权。具有最小权的生成树，称为最优树（或最小树）。求最小树的方法有破圈法和避圈法。,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,例

20、10-7,破圈法：在给定连通图G中，任取一圈，去掉一条最大权边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条边），在余图中（是图G的支撑子图）任取一圈，去掉一条最大权边，重复下去，直到余图中无圈为止，即可得到图G的最小树。,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,15,9,16

21、,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,17,4,1,23,总造价=1+4+9+3+17+23=57,v1,v7,v4,v3,v2,v5,v6

22、,20,15,9,16,25,3,28,17,4,1,23,36,避圈法（kruskal算法）：在连通图G中，任取权值最小的一条边（若有两条或两条以权数相同且最小，则任取一条），在未选边中选一条权值权值最小的边，要求所选边与已选边不构成圈，重复下去，直到不存在与已选边不构成圈的边为止。已选边与顶点构成的图T就是所求最小树。,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16

23、,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,总造价=1+4+9+3+17+23=57,3 最短路问题(1959年Dijkstra给出最短路算法)最短路问题是网络分析中的一个基本问题，它不仅可以直接应用于于解决生产实际的许多问题，若管道铺设、线路安排、厂区布局等，而且经常被作为一个基

24、本工具，用于解决其它的优化问题.定义 给定一个赋权有向图D=(V,A)，记D中每一条弧 上的权为为。给定D中一个起点 和 终点，设P是D中从 到 的一条路.则定义路P的权是P中所有弧的权之和.记为，即 又若P*是D图中 到 的一条路，且满足 则称P*为从 到 的最短路。,下面介绍在一个赋权有向图中寻求最短路的方法，这种方法实际上求出了从给定 到 任一个顶点的最短路.如下事实是经常要利用的，即如果P是D中从 到 的最短路，是P中的一点，那么从 沿P 到 路也是从 到 的最短路.事实上，如果这个结论不成立，设Q是从 到 的最短路，令P是从 沿Q到达，再从 沿P到达的路，那么P的权就比P的权小，这与

25、P是从 到 的最短路矛盾.,P,P,Q,P,例1：求图A到B的最短路,A,B,C,D,E,F,G,1,3,5,3,5,8,4,6,1,2,4,5,0,B,C,D,E,F,G,1,3,5,3,5,8,4,6,1,2,4,5,0,1,3,B,C,D,E,F,G,1,3,5,3,5,8,4,6,1,2,4,5,0,1,3,6,4,B,C,D,E,F,G,1,3,5,3,5,8,4,6,1,2,4,5,0,1,3,6,4,5,B,C,D,E,F,G,1,3,5,3,5,8,4,6,1,2,4,5,0,1,3,6,4,5,9,最短路为ACGFB,v7,v6,v4,v3,G,7,1,8,2,4,3,3,1

26、,4,7,2,0,2,v1,v2,v5,例2：求图 到 的最短路,v1,v7,v7,v6,v4,v3,G,7,1,8,2,4,3,3,1,4,7,2,0,2,v1,v2,v5,1,4,v7,v6,v4,v3,G,7,1,8,2,4,3,3,1,4,7,2,0,2,v1,v2,v5,5,1,4,v7,v6,v4,v3,G,7,1,8,2,4,3,3,1,4,7,2,0,2,v1,v2,v5,5,4,1,4,v7,v6,v4,v3,G,7,1,8,2,4,3,3,1,4,7,2,0,2,v1,v2,v5,5,7,4,1,4,v7,v6,v4,v3,G,7,1,8,2,4,3,3,1,4,7,2,0

27、,2,v1,v2,v5,5,7,4,9,1,4,v1到v7的最短路径是：v1v3v4v7，（5分）最短距离为1+4+2=7。,v7,v6,v4,v3,G,7,1,8,2,4,3,3,1,4,7,2,0,2,v1,v2,v5,5,7,4,9,1,4,v1到v7的最短路径是：v1v3v4v7，（5分）最短距离为1+4+2=7。,例：某交通网络如下图，求v1到v8的最短路线解：,v1,v2,v4,v5,v6,v7,v8,6,3,1,2,2,1,6,10,4,3,10,4,4,6,练习：求最短路,v1,v2,v4,v5,v6,v7,v8,6,3,1,2,2,1,6,10,4,3,10,4,4,6,v1

28、,V2(v3,5),V3(v1,3),V4(v1,1),V5(v2,6),V6(v5,10),6,3,1,2,2,1,6,10,4,10,4,3,6,4,V2(v1,6）,v7(v5,9),v8(v5,12),例设备更新问题某工厂使用一台设备，每年年初工厂要作出决定：继续使用，购买新的？如果继续使用旧的，要负维修费；若要购买一套新的，要负购买费。试确定一个5年计划，使总支出最小。若已知设备在各年的购买费，及不同机器役龄时的残值与维修费，如表1所示表1,解：把这个问题化为最短路问题。,设bi 表示设备在第i 年年初的购买费,ci 表示设备使用i 年后的维修费,V=v1,v2,v6,点vi表示第i

29、 年年初购进一台新设备,虚设一个点v6表示第5年年底.E=vivj|1ij6.,若每年购置一台新设备，则购置费为：11+11+12+12+13=59，每年的维修费为5元，共59+5*5=84.若在1，2，3年购置一台新设备，则购置费为：11+12+13=36，每年的维修费为（5+6）+（5+6）+5=27，共36+27=63.设备使用一年后就更新则不划算。由表1知，设备使用三年后应当更新。,这样上述设备更新问题就变为：在有向赋权图G=(V,E,F)(图解如下)中求v1到v6的最短路问题.,由实际问题可知,设备使用三年后应当更新,因此删除该图中v1到v5,v1到v6,v2到v6的连线；又设备使用

30、一年后就更新则不划算,因此再删除该图中v1v2,v2v3,v3v4,v4v5,v5v6 五条连线后得到,从上图中容易得到v1到v6只有两条路：,v1v3v6（费用22+31）和v1v4v6（费用22+31）.,而这两条路都是v1到v6的最短路.,3 网络最大流问题,引例：如下输水网络，南水北调工程，从vs到vt送水，弧旁数字前者为管道容量，后者为现行流量，如何调整使输水最多？,vs,vt,v2,v1,v4,v3,(3,3),(5,1),(1,1),(4,3),(1,1),(2,2),(3,0),(2,1),(5,3),容量：每个弧上的最大通过能力，用cij表示，即弧上的第一个数字；流量：弧上实

31、际通过的流量，用xij表示，弧上的第二个数字；显然0=xij=cij，如果xij=cij则称为饱和弧；,最大流问题的相关概念网络：给定了弧的容量C（vi,vj）的有向图D=（V，A，C）叫做一个网络。fij记为流量，cij记为容量。可行流：（1）（2）各点流入量=流出量，且vs的流出量=vt的流入量，这样的流称之为可行流截集：分离始点vs和终点vt的弧的集合，叫做截集截量：截集的容量叫做截量,的弧称为饱和弧；的弧称为非饱和弧。的弧称为零流弧；的弧称为非零流弧。若是网络中从发点到收点的链，链上的弧分为两类：一类与链的方向一致，叫做前向弧，记为；另一类与链的方向相反，叫做后向弧，记为。增广链：是可

32、行流，是一条从发点到收点的链，若在前向弧上，即在 中每一弧是非饱和弧；在后向弧上，即在 中每一弧是非零流，则称此链为增广链。,vs,vt,v2,v1,v4,v3,(3,3),(5,1),(1,1),(4,3),(1,1),(2,2),(3,0),(2,1),(5,3),增广链：是可行流，是一条从发点到收点的链，若在前向弧上，即在 中每一弧是非饱和弧；在后向弧上，即在 中每一弧是非零流，则称此链为增广链。,1 标号方法很简单：首先找到一条增广链，沿此进行最大可能调整，再找增广链，再调整，直到没有增广链。寻找增广链的标号法：先给vs标号（0，+）,而后依次审查各条弧（vi,vj）：对前向弧，饱和否

33、？不饱和（使其增加），给vj点标号（vi，l(vj);对后向弧，是否非零流弧（使其减少）？是，给vj标号（-vi,l(vj)）,直到给vt标上号，就得到了增广链。调整对于增广链，,求最大流的方法,调整令：得到新的可行流，重新标号，直至标不下去为止。,例：解水网最大流问题,vs,V2,(0,+),V1,(3,3),(5,1),(1,1),(4,3),(1,1),(2,2),(3,0),(5,3),(2,1),V4,V3,Vt,(vs,4),(-v1,1),(-v2,1),(v2,1),(v3,1),1 标号,对前向弧，饱和否？不饱和（使其增加），给vj点标号（vi，l(vj);对后向弧，是否非零

34、流弧（使其减少）？是，给vj标号（-vi,l(vj)）,直到给vt标上号，就得到了增广链。,vs,V2,(0,+),V1,(3,3),(5,2),(1,0),(4,3),(1,0),(2,2),(3,0),(5,3),(2,2),V4,V3,Vt,(vs,3),2 沿增广链进行调整，前向弧增加1，后向弧减少l。,vs,V2,(0,+),V1,(3,3),(5,2),(1,0),(4,3),(1,0),(2,2),(3,0),(5,3),(2,2),V4,V3,Vt,(vs,3),vs,V2,V1,V3,V4,Vt,(3,3),(5,2),(4,3),(1,0),(1,0),(2,2),(3,0

35、),(5,3),(2,2),(0,+),(vs,3),重新标号，直至标不下去为止。最小截集为（vs，v2），（v1，v3),容量为5。最大流也为5。,例1：求从发点V1到收点V7的最大流。弧的流量放在括号内。如图.V=20,4(3),例2：求图的最大流和最小割,图中标号为(,vs,V2,V1,V3,V4,Vt,(2,0),(8,8),(7,5),(9,9),(9,4),(5,5),(10,8),(5,4),(6,1),6、中国邮递员问题,证明：,定理1 对连通图G（V，E），下列条件是相互等价的：（1）G是一个欧拉图；（2）G的每一个节点的度数都是偶数；（3）G的边集合E可以分解为若干个回路的

36、并证明(1)（2）已知G为欧拉图，则必存在一个欧拉回路回路中的节点都是偶度数（2）（3）设G中每一个节点的度数均为偶数若能找到一个回路C1使G=C1，则结论成立否则，令G1=GC1，由C1上每个节点的度数均为偶数，则G1中的每个节点的度数亦均为偶数于是在G1必存在另一个回路C2令G2=G1C2，由于G为有限图，上述过程经过有限步，最后必得一个回路Cr使 Gr=Gr-1Cr上各节点的度数均为零，即Cr=Gr-1这样就得到的一个分解（3）（4）设 其中（i=1,2,r）均为回路由于G为连通图，对任意回路,必存在另一个回路与之相连，即存在共同的节点现在我们从图G的任意节点出发，沿着所在的回路走，每走

37、到一个共同的节点处，就转向另一个回路，这样一直走下去就可走遍G的每条边且只走过一次,最后回到原出发节点，即G为一个欧拉图,设G（V，E）为一个图，若存在一条回路，使它经过图中每条边且只经过一次又回到起始点，就称这种回路为欧拉回路，并称图G为欧图,利用定理1去判断一个连通图是否为欧拉图比较容易，但要找出欧拉回路，当连通图比较复杂时就不太容易了下面介绍一种求欧拉回路的算法弗罗莱算法 算法步骤如下：（1）任取起始点,（2）设路,已选出，则从E,中选出边,，使,与,相连，除非没有其它选择，,仍应为连通的,（3）重复步骤（2），直至不能进行下去为止,定理2 连通的有向图存在欧拉回路的充分必要条件是对任意

38、节点，进入该节点边数（进数）与离开该点的边数（出数）相等,中国邮递员问题 一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题 用图论的述语，在一个连通的赋权图G（V，E）中，要寻找一条回路，使该回路包含G中的每条边至少一次，且该回路的权数最小也就是说要从包含G的每条边的回路中找一条权数最小的回路 如果G是欧拉图，则很容易由弗罗莱算法求出一个欧拉回路，但是若G不是欧

39、拉图，即存在奇度数的节点，则中国由递员问题的解决要困难得多本节的主要目标是给出在有奇度数节点的连通图中寻找最小权数的回路的方法,例：已知邮递员要投递的街道如图11-20所示，试求最优邮路。,解 先找出奇节点：A1，A2，A3，A4，B1，B2，B3，B4奇节点进行配对，不妨把A1与B1，A2与B2，A3与B3，A4与B4配对，求其最短路显然它不是最优解下面我们根据定理3来进行调解,1,2,第一次调整：删去多于一条的重复边，即A3与B3，A4与B4中的（A4，B3）调整后，实际上成为A1与B1，A2与B2，A3与A4，B3与B4的配对，它们的最短路如图11-21所示,图11-21,1,2,第二次

40、调整：发现在回路A1，A2，B2，A4，B3，B4，B1，A1中重复边的权数和为11，大于该回路权数20的一半因而调整时，把该回路的重复边删去，代之以重复其余部分，得图11-22可以看出，实际上是调整为A1与A2，B1与B4，A3与A4，B2与B3配对,图11-21,1,2,图11-22,图11-23,P281/2从v8出发，因d(v8)=6,故可设vi1,vi2,vi3，vi4,vi5,vi6与v8相连，而V4,v5,v6,v7中必有一点与v8相连，否则与d(v8)=6矛盾。令vi1=v4,则vi1必与 vi2,vi3.vi4,vi5,vi6中某点相连，否则,d(vi1)3，与d(v4)=5

41、矛盾。,v8,vi6,vi5,vi4,vi3,Vi1=v4,vi2,6、中国邮递员问题,在奇点间加边，构造初始可行方案。寻找改进可行方案：在两奇点间检查所有链，若某链的长度小于已加重复边的长度，则在该链的每边加上重复边，去掉原重复边。重复以上步骤，直到任意两奇点间加重复边的链是最短的为止。,求解中国邮递员问题：例子,例子的初始可行解,例子的修正解,四、奇偶点作业法的改进方法,奇偶点作业法的瓶颈是需检查太多的链可以首先求出任意一对奇点之间的最短路，从中选出总路长最小的组合方案。也可以由奇点构成偶图，求最小匹配得到最优解。,一个四奇点的例子,第九章 网络计划,9.1基本概念杜邦公司关键路线法CPM

42、 确定型美国海军武器局计划评审技术PERT网络图（有向赋权图）的构成结点，也称事项，一道工序的开始或结束工序（弧），相对独立的活动，消耗资源虚工序，只表示衔接关系，不消耗资源工序时间（权），完成工序的时间消耗,9.2.网络规则,1、避免循环、不留缺口2、一一对应：一道工序用两个事项表示3、从左向右依次展开例：,A,4,B,6,D,7,E,5,F,9,H,4,I,8,C,6,G,7,9.3 关键路线法 CPM,时间参数运算 什么是关键路线？1、作业时间t（i，j），经验数据、统计数据2、事项最早时间TE(j)maxTE(i)+t（i，j）到齐上课，最后到者决定最早开课时间3、事项最迟时间TL(i

43、)minTL(j)-t（i，j）保证12点吃饭，路最远者决定最迟下课时间4、工序最早可能开工时间 TES(i,j)TE(i)=maxTES(h,i)+t（h,i）5、工序最早可能完工时间 TEF(i,j)TES(i,j)+t（i，j）,6、工序最迟必须开工时间 TLS（i,j)TL(j)t（i,j)minTLs(j,k)-t（i，j）7、工序最迟必须完工时间 TLF（i,j)TL(j)TLS（i,j)+t（i,j)8、工序总时差：在不影响其紧后工序最迟必须开工时间的前提下，本工序可以推迟的时间 R（i,j）TLS(i,j)TES(i,j)TLF(i,j)TEF(i,j)minTLS(j,k)T

44、EF（i,j）9、工序单时差：在不影响其紧后工序最早可能开工时间的前提下，本工序可以推迟的时间 r（i,j）minTES(j,k)TEF（i,j）,时间参数图解,.解上例：计算事项 时间参数,.解上例：计算事项 时间参数,TES,TLS,TEF,TLF,TES,TLS,TEF,TLS,r(i,j),R（i,j）,A4,B6,C6,G7,D7,E5,F9,H4,I 8,0,0,4,7,6,13,22,20,28,28,20,24,13,6,关键路线：由总时差为零的工序构成 B D G I,t（i,j),t（j,k),解上例 计算工序时间参数,9.4计划评审技术PERT,PERT的产生 关键路线法

45、中，工序时间是确定值，而对研究性的工序来说，t（i，j）是随机的。1958年美国海军武器局研制北极星导弹时提出，重点在于计划的评审。PERT的时间估计 采用三种时间估计法a最乐观时间，b最悲观时间，m最可能时间，则 工序期望时间 te 方差 e2（）2,a+4m+b,6,ba,6,PERT的计算方法,网络图的绘制与关键路线法相同参数计算与关键路线法体系不同 工程期望工期 TE tek 期望工期方差 2 ek2 计划工期 TK业主要求的工期 预期完工概率：查正态分布表 一定概率的完工期 TK TE+,TK TE,PERT应用举例,P346例6 关键工序：C D F/G I J期望工期：TE10.

46、50+10.17+20.33+5.17+12.8359 121.36+0.25+4.00+0.25+14.6920.55 22 1.36+0.25+1.00+0.25+14.6917.55完工概率：1（60-59）20.550.22 查表得 P（1）58.7 2（60-59）17.550.244 查表得 P（2）59.5若要有90的把握，计划工期应定多长 TK TE+59+4.531.2964.84,9.5 网络优化,CPM与PERT主要目标是控制工期网络优化在上述基础上，寻求时间更短、资源更省、成本更低的方案时间资源优化（资源的均衡配置）原则：关键优先、利用时差 P331例题4方法：绘制资源负荷图，排定关键工序，游移非关键工序,d20天,g30天,k25天,58人,H15天 39人,42人,26人,F18天 22人,v1,v5,v4,v3,v2,求下图的邻接矩阵和关联矩阵。,e1,e2,e3,e4,e5,e6,e7,e8,