第5章 图与网络优化 运筹学课件.docVIP

第五章 图与网络优化 本章主要介绍最小树问题、最短路问题、最大流问题。 第一节 图与树 图的相关概念 为了区别两类不同性质的图，把两点之间不带箭头的连线称为边，把两点之间带箭头的连线称为弧。 1、图 所谓图，就是点和边的组合,记之为G=(V,E),其中V为点的集合,E为边的集合,有时也称这样的图为无向图。 相应地,如果一个图D是由点和弧所构成的,则称之为有向图,记为D=(V,A),其中V 是点的集合,A是弧的集合。图1所示为一个无向图，其中；点集： 边集： 任一条边，则称是边的端点，点和点则为相邻的点，边称为点和点的关联边。 若某条边的两个端点相同，则称该边为环。图1中的为一个环 若两个端点之间有多于一条的边，则称为多重边。图1中的、的端点相同，故称为多重边 简单图：一个无环、无多重边的图称为多重边。 多重图：一个无环但有多重边的图称为多重图。 2、次的概念 以点为端点的边的个数称为点的次，记为。 次为奇数的点，称之为奇点； 次为偶数的点，称之为偶点； 次为1的点称之为悬挂点；次为0的点称之为孤立点。 图1 定理1图G 中所有次的和等于边数的两倍。即 这是显而易见的，一条边连接两个点，每增加一条边图的次数增加2，所以图的次之和等于边数的两倍。式中q为图的边数。 定理2 任一图中奇点的个数必为偶数。 证明:将图中点分为奇点和偶点两个点集分别记为和,由定理1有: 因是偶数, 也是偶数,故也必是偶数. 因此的个数一定是偶数. 3、连通图 对于一个给定的图G=(V,E) ，若其中一点沿边、点的交错集合到达另一点，则称其中的边集为一条连接和的链,常记为。 若在一条链中，则称之为一个圈。若在该链中各点均不相同，则称之为初等链。若除了首点和末点外，其余各点均不相同，且不同于首点，则称之为初等圈。如无特殊说明，一般所说的链都指初等链。 在一个图G=（V，E）中，若任何两点之间，至少有一条链，则称该图为连通图，否则称为不连通图。 对于一个不连通的图G，其每一个连通的部分称之为图G的连通分图，或简称分图。 给定一个图G，若另一个图满足，则称图是图G的子图。 对于有向图D=（V，A）可以定义类似的概念： 若从有向图D=（V，A）中去掉所有箭头方向，则得到一个无向图，称之为D的基础图，记为G（D）。 设是有向图D中一个点弧序列，若此点弧序列在所对应的基础图G（D）中为一条链，则称该点弧序列为有向图D（V，A）的一条链。若此链中，均有，则称该链为有向图D中从到的一条路；若有称之为回路；若除首尾点外，其余点均不相同，则称之为初等回路。 树的概念及最小部分树 树是一类特殊的图，它在实际生活中有着广泛的应用。 树的概念 树的定义：一个无圈的连通图称之为树。 树的性质 树的性质： 在树中，任意两顶点之间必有一条且仅有一条链。 在树中，去掉一边，则树成为不连通图。 在树中，不相邻两个顶点间添上一条边，恰好得到一个圈。 两个定理 定理3设T为p个顶点的一颗树，则T的边数为p-1条。 定理4若图G是连通图，则G必有部分树。 证明：因为G连通，则任意的两顶点之间必有一条或多条链。若任意两顶点之间存在两条链，则构成一个圈，任意删掉其中一条边，则该圈变成链。依次进行，直到图G中不再含有圈，则该图为树，称之为原图的部分树，又称为支撑树。 最小部分树问题 赋权图。给图G=（V，E）中的每条边一个权数，则该图G称为赋权图。称为边的权。 最小树定理。若是赋权图G的一棵树，则它是最小树时当且仅当对外的每条边，有： 其中是树中连接点和的唯一的链。 证明：边是图G中的边，其权为。在其部分树中加上这条边，则构成一个圈。在此圈所包括的各边的权值中，是最大的。因此，要在此圈中去掉一边使其成为权值之和最小的树，只有删掉边。 最小树的求法 算法1——避圈法：在连通赋权图G中，每一步从未选的边中，选一条最小权的边，使其余已经选定的边不构成圈,直至构成图G的一个连通的子图,即求得最小树. 算法2_破圈法:任取一圈,从圈中去掉一条最大权数的边,在余下的图中,重复这一步骤,直到无圈时为止,即求得最小树. 例1求图2所示连通图的最小树。 解：用破圈法或避圈法得到图2的最小树，如图3所示。 图2 图3 第二节 最短路问题 引例 例2从油田铺设管道,把原油由油田送到石油炼油厂.要求管道必须沿图4中所给的路线铺设.设图中的点为油田所在地,点为石油炼油厂,每个弧旁的数字表示这条道路的长度,求使管道总长度最短的铺设方案。 用图的术语叙述这个问题，就是在给定的有向图中，寻求一条从点到点的路，并使其是该两点之间距离最短的路。 这种在一个有向图（或无向图）