运筹学图与网络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

4、,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，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条边集合。 是描述边与顶点之间

7、关系的函数,称G=（V，E，）为 一个图，如果它满足： （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

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

9、 定理8-2：在任意一个图中，奇顶点的个数必为偶数。 注意：一个图的形状并不唯一。但它的三要素是不能变的。,注意：一个图的形状并不唯一。但它的三要素是不能变的。 例如：这两个图均为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

10、为G的生成（支撑）子图。,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,v1,v5,v4,v2,e1,e5,e3,（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,e

12、5,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,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,v

13、8,二、图的矩阵表示 一个图非常直观，但是不容易计算，特别不容易在计算机上进行计算，一个有效的解决办法是将图表示成矩阵形式，通常采用的矩阵是邻接矩阵、边长邻接矩阵、弧长矩阵和关联矩阵。,1 邻接矩阵 邻接矩阵A表示图G的顶点之间的邻接关系，它是一个nn的矩阵，如果两个顶点之间有边相联时，记为1，否则为0。,v1,v2,v3,v4,v1 v2 v3 v4 v1 0 1 1 1 v2 1 1 1 0 v3 1 1 0 1 v4 1 0 1 0,无向图的邻接矩阵是对称矩阵。,v1,v2,v3,v4,v1,v5,v4,v3,v2,也可以对有向图,v1 v2 v3 v4 v5 v1 0 0 0 1 1

14、v2 1 0 0 1 0 v3 0 1 1 0 0 v4 0 1 1 0 1 v5 1 0 0 1 0,二、边长邻接矩阵 在图的各边上一个数量指标，具体表示这条边的权（距离，单价，通过能力等）赋权图或网络。 无向网络；有向网络；混合网络；边权网络；点权网络； 以边长代替邻接矩阵中的元素得到边长邻接矩阵。,v1,v2,v3,v4,2,5,6,4,3,4,v1 v2 v3 v4 v1 0 2 5 6 v2 2 4 3 v3 5 3 0 4 v4 6 4 0,其中表示两点之间不能连接 。,3 弧长矩阵 对有向图的弧可以用弧长矩阵来表示。其中表示两点之间没有弧连接 。,v1,v5,v4,v3,v2,1

15、,4,2,3,2,2,6,1,2,v1 v2 v3 v4 v5 v1 0 1 2 v2 0 2 4 v3 2 0 1 v4 3 2 0 6 v5 0,4 关联矩阵 关联矩阵B揭示了图G的顶点和边之间的关联关系，它是一个nxm矩阵。 1 （ vi，vk）=ej Bij= -1 （ vk，vi）=ej 0 其他,v1,v2,v4,v3,e1,e2,e4,e3,e7,e5,e6,e1 e2 e3 e4 e5 e6 e7 v1 1 -1 1 0 0 0 0 v2 0 0 -1 -1 -1 0 0 v3 0 1 0 1 0 1 -1 v4 -1 0 0 0 1 -1 1,对无向图不存在-1 元素 。,1

16、0-2 最优树问题（或最小树） 树是一类极其简单而很有用的图。 定义（链）如果图中的某些点、边可以排列成点和边的交错序列，则称此为一条链。,定义（链）如果图中的某些点、边可以排列成点和边的交错序列，则称此为一条链。 定义（圈）如一条链中起点和终点重合，则称此为一条圈。,定义（连通图）如果图中的任意两点之间至少存在一条通路，则称图为连通图，否则为不连通图。,定义（连通图）如果图中的任意两点之间至少存在一条通路，则称图为连通图，否则为不连通图。 定义（树）一个无圈的连通图称为树。如果一个无圈的图中每一个分支都是树，则称图为森林。,定理3：设图G=(V,E)是一个树，顶点个数 ,则G中至少有两个悬挂

17、点。 证明：设 是G中含边数最多的初等链。 往证 是悬挂点。若 ，则存在边 因为G为树，不含圈，故不在P上。 是比P更长的初等链。矛盾。 定理4：设图G=(V,E)是一个树的充分必要条件是G不含圈，且恰有 条边。 证明：必要性：用数学归纳法： 时，显然成立。设对 时也成立。设图G含n+1个点，由定理3，G含悬挂点 ，考虑图 ，有 充分性：往证G为连通图，若G不为连通图，则有s（s2）个连通分图 。每一个都连通不含圈，即为树。,矛盾,定理5：设图G=(V,E)是一个树的充分必要条件是G是连通图，且 证明：必要性：由定理4即得。 充分性：往证G不含圈。对点用数学归纳法： 时，显然成立。设对 时也成

18、立。设图G含n+1个点，G必含悬挂点。否则， 设 是G的悬挂点，考虑 仍为连通图， 由归纳假设知 不含圈，则G必不含圈。 定理6：设图G=(V,E)是一个树的充分必要条件是G的任意顶点之间恰有一条链。,矛盾,（1） G不含圈 （2）G是连通图 （3） （4）图G=(V,E)是一个树 上述条件有两个成立，就推出其余条件成立。,树的性质： 1 在图中任意两点之间必有一条而且只有一条通路。,树的性质： 1 在图中任意两点之间必有一条而且只有一条通路。 2 在图中划去一条边，则图不连通。 树是边最少的连通图,树的性质： 1 在图中任意两点之间必有一条而且只有一条通路。 2 在图中划去一条边，则图不连通

19、。 3 在图中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。,树的性质： 1 在图中任意两点之间必有一条而且只有一条通路。 2 在图中划去一条边，则图不连通。 3 在图中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。 4 图中边数有n=p-1（p为顶点数）,a,b,c,f,e,d,h,g,例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为一棵生成树。对于分离（不连通图）图，则称为生成森林。 一个子图与生成树的区别是：子图与原图相比少弧又少点，生成树与原图相比少弧不少点。,

20、定理 图 G有生成树的充分必要条件为图是连通图。 定义（最优树）在赋权图G中，一棵生成树所有树枝上权的和，称为生成树的权。具有最小权的生成树，称为最优树（或最小树）。 求最小树的方法有破圈法和避圈法。,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,例10-7,破圈法：在给定连通图G中，任取一圈，去掉一条最大权边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条边），在余图中（是图G的支撑子图）任取一圈，去掉一条最大权边，重复下去，直到余图中无圈为止，即可得到图G的最小树。,v1,v7,v4,v3,v2,v5,v6,20,15

21、,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,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,

22、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,20,15,9,16,25,3,28,17,4,1,23,36,避圈法（kruskal算法）：在连通图G中，任取权值最小的一条边（若有两条或两条以权数相同且最小，则任取一条），在未选边中选一条权值权值最小的边，要求所选边与已选边不构成圈，重复下去，直到不存在与已选边不构成圈的边为止。已选

23、边与顶点构成的图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,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

24、,v6,20,15,9,16,25,3,28,17,4,1,23,36,总造价=1+4+9+3+17+23=57,3 最短路问题(1959年Dijkstra给出最短路算法) 最短路问题是网络分析中的一个基本问题，它不仅可以直接应用于于解决生产实际的许多问题，若管道铺设、线路安排、厂区布局等，而且经常被作为一个基本工具，用于解决其它的优化问题. 定义 给定一个赋权有向图D = (V,A)，记D中每一条弧 上的权为为 。给定D中一个起点 和 终点，设P是D中从 到 的一条路.则定义路P的权是P中所有弧的权之和.记为 ，即 又若P*是D图中 到 的一条路，且满足 则称P*为从 到 的最短路。,下面介

25、绍在一个赋权有向图中寻求最短路的方法，这种方法实际上求出了从给定 到 任一个顶点的最短路. 如下事实是经常要利用的，即如果P是D中从 到 的最短路， 是P中的一点，那么从 沿P 到 路也是从 到 的最短路.事实上，如果这个结论不成立，设Q是从 到 的最短路，令P是从 沿Q到达 ，再从 沿P到达的路 ，那么P的权就比P的权小，这与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,

26、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,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,

27、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,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的最短路

28、径是：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,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),例设备更新问题 某工厂使用一台设备，每年年初工

29、厂要作出决定：继续使用，购买新的？如果继续使用旧的，要负维修费；若要购买一套新的，要负购买费。试确定一个5年计划，使总支出最小。 若已知设备在各年的购买费，及不同机器役龄时的残值与维修费，如表1所示 表1,解：把这个问题化为最短路问题。,设bi 表示设备在第i 年年初的购买费,ci 表示设备使用i 年后的维修费, V=v1, v2, , v6,点vi表示第i 年年初购进一台新设备,虚设一个点v6表示第5年年底. E =vivj | 1ij6.,若每年购置一台新设备，则购置费为：11+11+12+12+13=59，每年的维修费为5元， 共59+5*5=84. 若在1，2，3年购置一台新设备，则购

30、置费为：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的连线；又设备使用一年后就更新则不划算,因此再删除该图中v1v2 ,v2v3 ,v3v4 ,v4v5 ,v5v6 五条连线后得到,从上图中容易得到v1到v6只有两条路：,v1v3v6（费用22+31）和v1v4v6 （费用22+

31、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表示，即弧上的第一个数字； 流量：弧上实际通过的流量，用xij表示，弧上的第二个数字；显然0= xij=cij，如果xij=cij则称为饱和弧；,最大流问题的相关概念 网络：给定了弧的容量C（vi,vj）的有向图D=（V，A，C）叫做一个

32、网络。 fij记为流量， cij记为容量。 可行流：（1） （2）各点流入量=流出量，且vs的流出量=vt的流入量，这样的流称之为可行流 截集：分离始点vs和终点vt的弧的集合，叫做截集 截量：截集的容量叫做截量,的弧称为饱和弧； 的弧称为非饱和弧。 的弧称为零流弧； 的弧称为非零流弧。 若是网络中从发点到收点的链，链上的弧分为两类： 一类与链的方向一致，叫做前向弧，记为 ；另一类与链的方向相反，叫做后向弧，记为 。 增广链： 是可行流， 是一条从发点到收点的链， 若在前向弧上， ，即在 中每一弧是非饱和弧； 在后向弧上， ，即在 中每一弧是非零流，则称此链为增广链。,vs,vt,v2,v1,

33、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）：对前向弧，饱和否？不饱和（使其增加），给vj点标号（vi，l(vj); 对后向弧，是否非零流弧（使其减少）？是，给vj标号（-vi, l(vj)

34、 ）, 直到给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); 对后向弧，是否非零流弧（使其减少）？是，给vj标号（-vi, l(vj) ）, 直到给vt标上号，就得到了增广链。,vs,

35、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),(5,3),(2,2),(0,+),(vs,3),重新标号，直至标不下去为止。最小截集为

36、 （ 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可以分解为若干个回路的并 证明 (1) （2） 已知G为欧拉图，则必存在一个欧拉回路回

37、路中的节点都是偶度数 （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的任意节点出发，沿着所在的回路走，每走到一个共同的节点处，就转向另一个回路，这样一直

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