第5章 运筹学模型5.2 图论模型图论是运筹学的一个重要分支,它是建立和处理离散类数学模型的一个重要工具。
用图论的方法往往能帮助人们解决一些用其它方法难于解决的问题。
图论的发展可以追溯到1736年欧拉所发表的一篇关于解决著名的“哥尼斯堡七桥问题”的论文。
由于这种数学模型和方法直观形象,富有启发性和趣味性,深受人们的青睐。
到目前为止,已被广泛地应用于系统工程、通讯工程、计算机科学及经济领域。
传统的物理、化学、生命科学也越来越广泛地使用了图论模型方法。
本章将在介绍图的一些基本概念的基础上,着重介绍最小生成树、最短路、最大流及最小费用最大流问题。
5.2.1 图的基本概念城市之间的交通关系,家族成员之间的关系,工厂、企业、事业单位内部,部门之间的上下关系,工程中各个工序之间的先后关系等等,用图形来描述往往是很有益的。
图论是研究某种特定关系的一门学问。
1.图图 (graph) 由若干个点 (称作顶点,vertex) 和若干条连接两两顶点的线段(称edge )组成。
通常,顶点可用来表示某一事物,边用来表示这些事之间的某种关系。
如图5-1中的五个顶点可以代表五个城市。
如果两个顶点之间有一条边连接,就表示这两个城市之间有一条铁路。
同样,它也可以代表五个人。
如果两个人认识,则用一条边把这两个顶点连接起来。
图5-1由于图是用来表示某些事物之间的联系,因而在画图时,顶点位置,边的长短、曲直是无关紧要的。
只要两个图的顶点可以一一对应,并且使得对应的顶点之间是否有边相连完全相同,就可以认为是同一个图。
例如:图5-1也可以画成图5-2的形式。
图 5-2 设图的顶点集合V ={n v v v ,...,, 21}, 边的集合 E ={m e e e , ... ,,21} 把图记作) , (E V G =。
这里大括号 { } 内的元素是没有顺序的,而小括号( )内的元素是有顺序的。
如果边e 连接顶点u 和v ,则记作e = {v u ,}。
u 和v 称作e 的端点,e 称作u 和v 的关联边。
如果u 和v 之间有一条边,即{v u ,}∈E ,则称u 和v 相邻。
如果两条边有一个共同的端点,则称这两条边相邻。
没有关联边的顶点称作孤立点。
两个顶点之间可以有不止一条边,端点相同的两条边称作平行边,如果一条边的两个端点重合,则称作环。
不含环和平行边的图称作简单图。
如图5-3中), (E V G =,V={6i 1 | ≤≤i v },E ={9j 1 | ≤≤j e }, 1e ={21,v v },}, {322v v e =, 21 v v 和相邻,31 v v 和不相邻。
21 e e 和相邻。
6v 是孤立点。
7e 和8e 是平行边,9e 是环。
设P 是图) , (E V G =中以顶点u 和v 为首尾、点边交替的序列。
如果序列中每一条边的端点恰好是与它前后相邻的两个顶点,则称这 个序列p 是从u 到v 的一条链。
当链的首尾相连时,它称作圈。
如果链上所有顶点都不相同, 图5-3 则称这条链是初级链。
如果圈上除首尾两个定点之外所有顶点都不相同,则称这个圈是初级圈。
例如,在图5-3中,},,,,,,,,,,{452232211911v e v e v e v e v e v p =是一条从41 v v 到的链,但不是初级链。
},,,,,,,,,,{112658475412v e v e v e v e v e v p =是一个圈,但不是初级圈。
在简单图中,可以用顶点序列表示链和圈。
任意两个顶点间都有一条链的图称作连通图。
图5-3不是连通图。
设有两个图) , (E V G =和),(111E V G =。
如果E E V V ⊆⊆11,则称1G 是G 的子图,如果),(111E V G =是) , (E V G =的子图,并且V V =1,则称1G 是G 的生成子图。
如果V V ⊆1, 1E 是E 中所有端点属于1V 的边组成的集合,则称1G 是G 的关于1V 的导出子图,图5-4中的3个图均是图5-3的子图,其中(b )是生成子图,(c )是关于},,{5211v v v V =的导出子图。
图 5-4我们常常可以利用图比较简便的解决某些实际问题,下面是一个例子。
例 1 有5位运动员参加游泳比赛,表5-1给出每位运动员参加的比赛项目。
问如何安排比赛,才能是每位运动都不连续的参加比赛?表 5-1赛没有同一运动员参加,则可以把这两项紧排在一起,用一条边把代表这两个项目的顶点连起来。
这样得到 图5-5,不难看出,为了解决这个问题,只需找到一条包含所有顶点的初级链。
如P= {B,C,D,A,E}是一条初级链,其对应的比赛安排是:50m 蛙泳,100m 蝶泳,100m 自由泳,50m 仰泳,200m 自由泳。
图 5-52.有向图在图) , (E V G =中,边是没有方向的,即},{},{u v v u =,这种图称作无向图。
但是,有些关系不是对称的,用图表示这样的关系时,边是有方向的,用箭头表示,称作弧。
从顶点u 指向v 的弧a 记作),(v u a =。
u 称作a 的始点,v 称作a 的终点。
这样的图称作有向图。
设顶点集合V ={n v v v ,...,, 21},弧集合A ={m a a a , ... ,,21},有向图记作) , (A V D =,和无向图类似,在有向图中也有环、平行弧、子图等概念。
当然,在有向图中必须注意到弧是有方向的。
例如,平行弧不仅要求两条弧的端点相同而且要求它们的始点和始点相同,终点和终点相同。
设P 是有向图) , (A V D =中从顶点u 到v 的点弧交替的序列。
如果序列中每一条弧的始点和终点恰好分别是与它前后相邻的顶点,则P 称D 是中的一条路。
当路的首尾相连时,称作一条回路。
和无向图一样,顶点全不相同的路称作初级回路。
例如,图5-6给出一个有向图) , (A V D =,其中V ={4321,,, v v v v },}, 81|{≤≤=i a A i ),(),,(232211v v a v v a ==, 图 5-6},,,,,,{1435461v a v a v a v p =是一初级回路。
3. 树无圈的连通图称作树(tree)。
设) , (E V G =为一个连通图,如果树) , (E V T =是) , (E V G =的生成子图,则T 称作G 生成树。
图5-7给出3棵树,其中(b )和(c )都是图5-1的生成树。
图 5-7不难证明树有下列性质:性质1 树的边数等于顶点数减1。
性质2 树的任意两个顶点之间有且只有一条初级链。
性质3 在树中任意去掉一条边,就得到一个非连通图。
性质4 在树中任意两个顶点之间添加一条边,恰好产生一个初级圈。
5.2.2 最小生成树设图) , (E V G =,对每一条边E e ∈, 指定一个实数)(e ω,我们称这样的图为赋权图,记作) ,, (ωE V G =,其中ω是边集合E 到实数集的映射,实数)(e ω称作边的权。
当},{j i v v e =时,常把)(e ω记作j i ω。
类似地,对有向图) , (A V D =的每一条弧A a ∈指定一个实数)(a ω,得到赋权有向图,记作) ,, (ωA V D =,)(a ω称作弧a 的权,当),(j i v v a =时,常把)(a ω记作j i ω。
在实际应用中,权可以有各种各样的含义,如距离、时间、费用、运输量、流量等。
1.最小生成树的概念设) ,, (ωE V G =是一个连通的赋权图,),(S V T =是G 的生成树,把T 中所有边的权之和称作树T 的权,记作)(T ω,即∑∈=se e T )()(ωω,G 中权和最小的生成树*T称作最小生成树。
2.最小生成树的算法Kruskal 于1956年给出一个求最小生成树的算法:避圈法。
其基本方法如下:(1) 画出图) ,, (ωE V G =中的全部顶点。
(2) 按边权的大小从小到大选边(n 个顶点需n-1步),并且每一步都不能构成圈。
例 2 现有5个城市,打算用铁路把它们连接起来。
这5个城市之间哪两个可以修建铁路以及铁路的长度如图5-8所示(每一条边旁边有一个数字,即表示这段铁路的长度)。
试给出修建铁路的方案,使铁路总长度最短。
图 5-8解 此题提出的问题是求给定赋权图的最小生成树。
做题步骤如图5-9所示:图 5-9注意,在第四步,可以不取},{42v v ,而取},{53v v ,得到另一棵最小生成树,其权和为12。
如图5-10所示。
可见最小生成树不唯一。
计算在每一步都要判断添加的边是否构成圈。
这在图不很复杂时,直接观察并不困难。
但在使用计算机时,则必须进一步给出形式化的方法,计算的具体步骤如下:Kruskal 算法1. 按权从小到大排列边)()()(21m e e e ωωω≤≤≤令 n i i v l i ≤≤←1 ,)( 图 5-10 2. 令S ←φ,K ←1(φ表示空集)。
3. 设)()( },,{v l u l v u e k ==若,则转6;否则令}{k e s s ←,执行4。
4. 对所有i i v v l u l v l 的顶 )}(),(max{)(=令 )}(),(min{)(v l u l v l i ←。
5. 若|S|= n-1,则 是S 最小生成树的边集合,计算结束;否则执行6。
(|S|表示S 中元素的个数)6. 若k=m ,则说明图是非连通的,停止计算;否则令k ←k+1,转3。
5.2.3最短路问题1. 最短路的概念设 (,)G V E =为连通图,图中各边 (,)i j v v 有权 i j ω(其中i j ω=+∞ 表示 ,i j v v之间没有边),,s t v v 为图中任意两点,所谓最短路问题就是求一条路μ,使它为从s v 到t v 的所有路中总权最小的路。
即:(,)()i j i jv v L μμω∈=∑ 最小。
2. 图的矩阵表示对于赋权图( , )G V E =,由其边(,)i j v v 的权i j w ,构造矩阵()i j n n A a ⨯= ,其中:(,)inf() (,)0 i j i j i j i j i jw v v Ea v v E v v ⎧∈⎪=∞∉⎨⎪=⎩称矩阵A 为赋权图G 的权矩阵。
例如图5-11的权矩阵为:图5-113.最短路的算法(1)由图写出其权矩阵。
(2)由Matlab 软件求最短路。
(3)软件计算程序为:function[D,R]=floyd(a) n=size(a,1); D=afor i=1:n for j=1:n R(i,j)=j; endend Rfor k=1:n for i=1:n for j=1:nif D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j); R(i,j)=R(i,k); end end end k D REnd例 3求下图5-12从1v 到6v 的最短路。