《运筹学模型》由会员分享，可在线阅读，更多相关《运筹学模型（32页珍藏版）》请在金锄头文库上搜索。
1、第 5 章 运筹学模型5.2 图论模型图论是运筹学的一个重要分支，它是建立和处理离散类数学模型的一个重要工具。用图 论的方法往往能帮助人们解决一些用其它方法难于解决的问题。图论的发展可以追溯到 1736 年欧拉所发表的一篇关于解决著名的“哥尼斯堡七桥问题”的论文。由于这种数学模 型和方法直观形象，富有启发性和趣味性，深受人们的青睐。到目前为止，已被广泛地应用 于系统工程、通讯工程、计算机科学及经济领域。传统的物理、化学、生命科学也越来越广 泛地使用了图论模型方法。本章将在介绍图的一些基本概念的基础上，着重介绍最小生成树、 最短路、最大流及最小费用最大流问题。5.2.1 图的基本概念城市之间的交
2、通关系，家族成员之间的关系，工厂、企业、事业单位内部，部门之间的 上下关系，工程中各个工序之间的先后关系等等，用图形来描述往往是很有益的。图论是研 究某种特定关系的一门学问。1. 图图（graph）由若干个点（称作顶点，vertex）和若干条连 接两两顶点的线段（称edge）组成。通常，顶点可用来表示 某一事物，边用来表示这些事之间的某种关系。如图 5-1 中的 五个顶点可以代表五个城市。如果两个顶点之间有一条边连 接，就表示这两个城市之间有一条铁路。同样，它也可以代 表五个人。如果两个人认识，则用一条边把这两个顶点连接起来。图 5-1由于图是用来表示某些事物之间的联系，因 而在画图时，顶点位
3、置，边的长短、曲直是无关 紧要的。只要两个图的顶点可以一一对应，并且使得对应的顶点之间是否有边相连完全相同，就可以认为是同一个图。例如：图5-1 也可以图 5-2画成图5-2 的形式。设图的顶点集合 V =v1,v2,.,vn, 边的集合 E=e1,e2,.,em 把图记作G二（V,E）。这里大括号 内的元素是没有顺序的，而小括号（）内的元素是有顺序 的。如果边e连接顶点u和v，则记作e = u, v 。u和v称作e的端点，e称作u和v的关 联边。如果u和v之间有一条边，即 u, v e E,则称u和v相邻。如果两条边有一个共同 的端点，则称这两条边相邻。没有关联边的顶点称作孤立点。两个顶点之
4、间可以有不止一条边，端点相同的两条边称作平行边，如果一条边 的两个端点重合，则称作环。不含环和平行边的 图 称 作 简 单 图。如图5-3中G 二(V, E), V=v11 i 6,iE = ej|1 j9 ,e1=v1,v2,j 1 1 2霜=V2, j V1和V2相邻，和V3不相邻。气和e2相邻。乙是孤立点。e7和e8是平行边，e9是环。设P是图G = (V, E)中以顶点u和v为首尾、点边交替的序列。如果序列中每一条边的 端点恰好是与它前后相邻的两个顶点，则称这 个序列p是从u到v的一条链。当链的首尾相 连时，它称作圈。如果链上所有顶点都不相同，图 5-3则称这条链是初级链。如果圈上除首
5、尾两个定点之外所有顶点都不相同，则称这个圈是初级IW圈。例如，在图 5-3 中，p = v ,e ,v ,e ,v ,e ,v ,e ,v ,e , v 是一条从v 到 v 的链，11911223225414但不是初级链。P = v ,e ,v ,e ,v ,e ,v ,e ,v ,e ,v 是一个圈，但不是初级圈。214574856211在简单图中，可以用顶点序列表示链和圈。任意两个顶点间都有一条链的图称作连通图。图 5-3 不是连通图。设有两个图G = (V, E )和G = (V ,E )。如果V匸V,E匸E则称G是G的子图，1 1 1 1 1 1如果G1 = (V,E1)是G = (V
6、,E)的子图，并且V1 = V，则称G1是G的生成子图。如果匕匸V，是E中所有端点属于的边组成的集合，则称q是G的关于匕的导出子图,图5-4中的3个图均是图5-3的子图，其中(b)是生成子图，(c)是关于匕=化,v2,叮的图 5-4我们常常可以利用图比较简便的解决某些实际问题，下面是一个例子。例 1有5位运动员参加游泳比赛，表5-1给出每位运动员参加的比赛项目。问如何安 排比赛，才能是每位运动都不连续的参加比赛？表 5-1运动员50m仰泳50m蛙泳100m蝶泳100m自由泳200m自由泳甲*乙*丙*丁*戊*图 5-5解用顶点表示比赛项目，分别记作A,B,D,C,E。如果两项比 赛没有同一运动员
7、参加，则可以把这两项紧排在一起，用一条边 把代表这两个项目的顶点连起来。这样得到 图 5-5，不难看出， 为了解决这个问题，只需找到一条包含所有顶点的初级链。如 P= B,C,D,A,E是一条初级链，其对应的比赛安排是：50m蛙泳， 100m 蝶泳， 100m 自由泳， 50m 仰泳， 200m 自由泳。2. 有向图在图G二(V,E)中，边是没有方向的，即u,v二v,u，这种图称作无向图。但是， 有些关系不是对称的，用图表示这样的关系时，边是有方向的，用箭头表示，称作弧。从顶 点u指向v的弧a记作a二(u,v)。u称作a的始点，v称作a的终点。这样的图称作有向图。设顶点集合V = v ,v，,
8、v ，弧集合A = a ,a，,a ，有向图记作D二(V, A)，1 2 n 1 2 m和无向图类似，在有向图中也有环、平行弧、子图等概念。当然，在有向图中必须注意到弧。例如，图5-6给出一个有向是有方向的。例如，平行弧不仅要求两条弧的端 点相同而且要求它们的始点和始点相同，终点和 终点相同。设P是有向图D二(V, A)中从顶点u到v 的点弧交替的序列。如果序列中每一条弧的始 点和终点恰好分别是与它前后相邻的顶点，则 P称D是中的一条路。当路的首尾相连时，称 作一条回路。和无向图一样，顶点全不相同的路a = (v , v ), a = (v , v )1 1 2 2 3 2图D 二(V, A)
9、，其中 V = v ,v ,v ,v ，A 二a 11 i 8,1234i图 5-6p=化,a6,v 4, a v3,a 4, vi是一初级回路。3. 树无圈的连通图称作树(tree)。设G二(V, E)为一个连通图，如果树T二(V,E)是G = (V,E)的生成子图，则T称作G生成树。图5-7给出3棵树，其中(b)和(c)都是图 5-1 的生成树。图 5-7不难证明树有下列性质：性质 1 树的边数等于顶点数减1。性质 2 树的任意两个顶点之间有且只有一条初级链。性质3 在树中任意去掉一条边，就得到一个非连通图。性质4 在树中任意两个顶点之间添加一条边，恰好产生一个初级圈。5.2.2 最小生成
10、树设图G = (V, E)，对每一条边e g E，指定一个实数(e)，我们称这样的图为赋权 图，记作G = (V,E,)，其中o是边集合E到实数集的映射，实数(e)称作边的权。当 e二v , v 时，常把(e)记作。类似地，对有向图D二(V, A)的每一条弧a g A指定 i ji j一个实数 (a)，得到赋权有向图，记作D二(V, A, )， (a)称作弧a的权，当a二(v , v )ij 时，常把 (a)记作。ij在实际应用中，权可以有各种各样的含义，如距离、时间、费用、运输量、流量等。1最小生成树的概念设G = (V,E, )是一个连通的赋权图，T = (V,S)是G的生成树，把T中所有
11、边的权 之和称作树T的权，记作 (T)，即(T) = 丫 (e)，G中权和最小的生成树T *称作最小egs生成树。2最小生成树的算法Kruskal 于 1956 年给出一个求最小生成树的算法：避圈法。其基本方法如下：(1) 画出图G二(V,E,w )中的全部顶点。(2) 按边权的大小从小到大选边(n个顶点需n-1步)，并且每一步都不能构成 圈。例 2 现有5个城市，打算用铁路把它们连接起来。这5个城市之间哪两个可以修建 铁路以及铁路的长度如图 5-8 所示(每一条边旁边有一个数字，即表示这段铁路的长度)。 试给出修建铁路的方案，使铁路总长度最短。图 5-8注意在第四步,可以不取, V4而取化，
12、叮，得到另一棵最小生成树其权和为12。如图 5-10 所示。可见最小生成树不唯一。计算在每一步都要判断添加的边是否构成圈。这在图不很复杂时，直接观察并不困难。但在使用计算机时，则必须进一步给出形式化的方法，计算的具体步骤如下：Kruskal 算法1. 按权从小到大排列边e(e )(e ) (e )1 2 m令 l (v ) J i, 1 i n图 510i2. 令S,K-1表示空集)。3. 设e 二u,v,若l(u)二 l(v)，则转 6；否则令s J s U e ，执行 4。kk4. 对所有l(v )二 maxl(u),l(v)的顶vii令l(v ) J minl(u),l(v) 。i5.
13、若|S|= n-1,则是S最小生成树的边集合，计算结束；否则执行6(|S|表示S中元素的个数)6. 若k=m，则说明图是非连通的，停止计算；否则令k-k+1,转3。5.2.3 最短路问题1. 最短路的概念设G = (V 5 E)为连通图，图中各边(v , v )有权(其中= +8表示v , vi ji ji ji j之间没有边)，v , v为图中任意两点，所谓最短路问题就是求一条路卩，使它为从v到v的 s ts t所有路中总权最小的路。即：L(卩)= 最小。ij(v. , vj)eij2. 图的矩阵表示对于赋权图G = ( V,E )，由其边(v , v )的权w，构造矩阵A二(a )i ji
14、jij nxn，其中：aijwij二 inf(g)0(v , v ) e E(v , v )笑 Eijv 二 vij称矩阵A为赋权图G的权矩阵。例如图 511 的权矩阵为：%v?R片V.气r o4inf&斗3 _斗027infinfmf205mf3h7502mf4infinf203inf3mf30 _图 5-113最短路的算法(1)由图写出其权矩阵。(2)由 Matlab 软件求最短路。(3)软件计算程序为： functionD,R=floyd(a) n=size(a,1);D=afor i=1:nfor j=1:nR(i,j)=j;endendRfor k=1:nfor i=1:nfor j=1:nif D(i,k)+D(k,j)
