-68-
第五章 图与网络模型及方法
§1 概论
图论起源于 18 世纪。第一篇图论论文是瑞士数学家欧拉于 1736 年发表的“哥尼
斯堡的七座桥”。1847 年,克希霍夫为了给出电网络方程而引进了“树”的概念。1857
年,凯莱在计数烷 22 +nnHC 的同分异构物时,也发现了“树”。哈密尔顿于 1859 年提
出“周游世界”游戏,用图论的术语,就是如何找出一个连通图中的生成圈、近几十年
来,由于计算机技术和科学的飞速发展,大大地促进了图论研究和应用,图论的理论和
方法已经渗透到物理、化学、通讯科学、建筑学、运筹学,生物遗传学、心理学、经济
学、社会学等学科中。
图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示
这些具体事物,用连接两点的线段(直的或曲的)表示两个事物的特定的联系,就得到
了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了
一个数学模型,借助于图论的概念、理论和方法,可以对该模型求解。哥尼斯堡七桥问
题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结
起来,问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次,再回到起点。
图 1 哥尼斯堡七桥问题
当然可以通过试验去尝试解决这个问题,但该城居民的任何尝试均未成功。欧拉为了解
决这个问题,采用了建立数学模型的方法。他将每一块陆地用一个点来代替,将每一座
桥用连接相应两点的一条线来代替,从而得到一个有四个“点”,七条“线”的“图”。
问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特
点,给出了一笔画的一个判定法则:这个图是连通的,且每个点都与偶数线相关联,将
这个判定法则应用于七桥问题,得到了“不可能走通”的结果,不但彻底解决了这个问
题,而且开创了图论研究的先河。
图与网络是运筹学(Operations Research)中的一个经典和重要的分支,所研究的
问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等
诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都
是图与网络的基本问题。
我们首先通过一些例子来了解网络优化问题。
例 1 最短路问题(SPP-shortest path problem)
一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的
公路网纵横交错,因此有多种行车路线,这名司机应选择哪条线路呢?假设货柜车的运
行速度是恒定的,那么这一问题相当于需要找到一条从甲地到乙地的最短路。
例 2 公路连接问题
某一地区有若干个主要城市,现准备修建高速公路把这些城市连接起来,使得从其
-69-
中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两
个城市之间修建高速公路的成本,那么应如何决定在哪些城市间修建高速公路,使得总
成本最小?
例 3 指派问题(assignment problem)
一家公司经理准备安排N 名员工去完成N 项任务,每人一项。由于各员工的特点
不同,不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
可以
使总回报最大?
例 4 中国邮递员问题(CPP-chinese postman problem)
一名邮递员负责投递某个街区的邮件。如何为他(她)设计一条最短的投递路线(从
邮局出发,经过投递区内每条街道至少一次,最后返回邮局)?由于这一问题是我国管
梅谷教授 1960 年首先提出的,所以国际上称之为中国邮递员问题。
例 5 旅行商问题(TSP-traveling salesman problem)
一名推销员准备前往若干城市推销产品。如何为他(她)设计一条最短的旅行路线
(从驻地出发,经过每个城市恰好一次,最后返回驻地)?这一问题的研究历史十分悠
久,通常称之为旅行商问题。
例 6 运输问题(transportation problem)
某种原材料有M 个产地,现在需要将原材料从产地运往N 个使用这些原材料的工
厂。假定M 个产地的产量和N 家工厂的需要量已知,单位产品从任一产地到任一工厂
的运费已知,那么如何安排运输方案可以使总运输成本最低?
上述问题有两个共同的特点:一是它们的目的都是从若干可能的安排或方案中寻求
某种意义下的最优安排或方案,数学上把这种问题称为最优化或优化(optimization)
问题;二是它们都易于用图形的形式直观地描述和表达,数学上把这种与图相关的结构
称为网络(network)。与图和网络相关的最优化问题就是网络最优化或称网络优化
(netwok optimization)问题。所以上面例子中介绍的问题都是网络优化问题。由于多
数网络优化问题是以网络上的流(flow)为研究的对象,因此网络优化又常常被称为网
络流(network flows)或网络流规划等。
下面首先简要介绍图与网络的一些基本概念。
§2 图与网络的基本概念
2.1 无向图
一个无向图(undirected graph)G 是由一个非空有限集合 )(GV 和 )(GV 中某些元素
的 无 序 对 集 合 )(GE 构 成 的 二 元 组 , 记 为 ))(),(( GEGVG = 。 其 中
},,,{)( 21 nvvvGV L= 称为图G 的顶点集(vertex set)或节点集(node set), )(GV 中
的每一个元素 ),,2,1( nivi L= 称为该图的一个顶点(vertex)或节点(node);
},,,{)( 21 meeeGE L= 称为图G 的边集(edge set), )(GE 中的每一个元素 ke (即 )(GV
中某两个元素 ji vv , 的无序对) 记为 ),( jik vve = 或 ijjik vvvve == ),,2,1( mk L= ,
被称为该图的一条从 iv 到 jv 的边(edge)。
当边 jik vve = 时,称 ji vv , 为边 ke 的端点,并称 jv 与 iv 相邻(adjacent);边 ke 称
为与顶点 ji vv , 关联(incident)。如果某两条边至少有一个公共端点,则称这两条边在
图G 中相邻。
边上赋权的无向图称为赋权无向图或无向网络(undirected network)。我们对图和
网络不作严格区分,因为任何图总是可以赋权的。
-70-
一个图称为有限图,如果它的顶点集和边集都有限。图G 的顶点数用符号 ||V 或
)(Gν 表示,边数用 || E 或 )(Gε 表示。
当讨论的图只有一个时,总是用G 来表示这个图。从而在图论符号中我们常略去
字母G,例如,分别用 ν,,EV 和ε 代替 )(),(),( GGEGV ν 和 )(Gε 。
端点重合为一点的边称为环(loop)。
一个图称为简单图(simple graph),如果它既没有环也没有两条边连接同一对顶点。
2.2 有向图
定义 一个有向图(directed graph 或 digraph)G 是由一个非空有限集合V 和V 中
某些元素的有序对集合 A构成的二元组,记为 ),( AVG = 。其中 },,,{ 21 nvvvV L= 称
为图G 的顶点集或节点集, V 中的每一个元素 ),,2,1( nivi L= 称为该图的一个顶点
或节点; },,,{ 21 maaaA L= 称为图G 的弧集(arc set),A中的每一个元素 ka (即V 中
某两个元素 ji vv , 的有序对) 记为 ),( jik vva = 或 ),,2,1( nkvva jik L== ,被称为该图
的一条从 iv 到 jv 的弧(arc)。
当弧 jik vva = 时,称 iv 为 ka 的尾(tail), jv 为 ka 的头(head),并称弧 ka 为 iv 的
出弧(outgoing arc),为 jv 的入弧(incoming arc)。
对应于每个有向图D,可以在相同顶点集上作一个图G ,使得对于D的每条弧,
G有一条有相同端点的边与之相对应。这个图称为D的基础图。反之,给定任意图G,
对于它的每个边,给其端点指定一个顺序,从而确定一条弧,由此得到一个有向图,这
样的有向图称为G的一个定向图。
以下若未指明“有向图”三字,“图”字皆指无向图。
2.3 完全图、二分图
每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。n个顶点
的完全图记为 nK 。
若 YXGV U=)( , Φ=YX I , 0|||| ≠YX (这里 || X 表示集合 X 中的元素个
数), X 中无相邻顶点对,Y 中亦然,则称G 为二分图(bipartite graph);特别地,若
YyXx ∈∀∈∀ , ,则 )(GExy∈ ,则称G 为完全二分图,记成 |||,| YXK 。
2.4 子图
图 H 叫做图 G 的子图( subgraph),记作 GH ⊂ ,如果 )()( GVHV ⊂ ,
)()( GEHE ⊂ 。若H 是G 的子图,则G 称为H 的母图。
G 的支撑子图(spanning subgraph,又成生成子图)是指满足 )()( GVHV = 的子
图H 。
2.5 顶点的度
设 )(GVv∈ ,G 中与 v关联的边数(每个环算作两条边)称为 v的度(degree),记
作 )(vd 。若 )(vd 是奇数,称 v是奇顶点(odd point); )(vd 是偶数,称 v是偶顶点(even
point)。关于顶点的度,我们有如下结果:
(i) ∑
∈
=
Vv
vd ε2)(
(ii) 任意一个图的奇顶点的个数是偶数。
2.6 图与网络的数据结构
-71-
网络优化研究的是网络上的各种优化模型与算法。为了在计算机上实现网络优化的
算法,首先我们必须有一种方法(即数据结构)在计算机上来描述图与网络。一般来说,
算法的好坏与网络的具体表示方法,以及中间结果的操作方案是有关系的。这里我们介
绍计算机上用来描述图与网络的 5 种常用表示方法:邻接矩阵表示法、关联矩阵表示法、
弧表表示法、邻接表表示法和星形表示法。在下面数据结构的讨论中,我们首先假设
),( AVG = 是一个简单有向图, mAnV == ||,|| ,并假设V 中的顶点用自然数 n,,2,1 L
表示或编号, A中的弧用自然数 m,,2,1 L 表示或编号。对于有多重边或无向网络的情
况,我们只是在讨论完简单有向图的表示方法之后,给出一些说明。
(i)邻接矩阵表示法
邻接矩阵表示法是将图以邻接矩阵(adjacency matrix)的形式存储在计算机中。图
),( AVG = 的邻接矩阵是如下定义的:C是一个 nn × 的 10− 矩阵,即
nnnnijcC
×
× ∈= }1,0{)( ,
⎩⎨
⎧
∉
∈=
.),(,0
,),(,1
Aji
Aji
cij
也就是说,如果两节点之间有一条弧,则邻接矩阵中对应的元素为 1;否则为 0。
可以看出,这种表示法非常简单、直接。但是,在邻接矩阵的所有 2n 个元素中,只有m
个为非零元。如果网络比较稀疏,这种表示法浪费大量的存储空间,从而增加了在网络
中查找弧的时间。
图 2 有向图
例 7 对于图 2 所示的有向图,可以用邻接矩阵表示为
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
01100
10100
00010
01000
00110
同样,对于网络中的权,也可以用类似邻接矩阵的 nn × 矩阵表示。只是此时一条
弧所对应的元素不再是 1,而是相应的权而已。如果网络中每条弧赋有多种权,则可以
用多个矩阵表示这些权。
(ii)关联矩阵表示法
关联矩阵表示法是将图以关联矩阵(incidence matrix)的形式存储在计算机中.图
),( AVG = 的关联矩阵B是如下定义的:B是一个 mn × 的矩阵,即
mnmnikbB
×
× −∈= }1,0,1{)( ,
-72-
⎪⎩
⎪⎨
⎧
∈=∈∃−
∈=∈∃
=
.,0
,),(, ,1
,),(,,1
其它
AijkVj
AjikVj
bik
也就是说,在关联矩阵中,每行对应于图的一个节点,每列对应于图的一条弧。如
果一个节点是一条弧的起点,则关联矩阵中对应的元素为 1;如果一个节点是一条弧的
终点,则关联矩阵中对应的元素为 1− ;如果一个节点与一条弧不关联,则关联矩阵中
对应的元素为 0。对于简单图,关联矩阵每列只含有两个非零元(一个 1+ ,一个 1− )。
可以看出,这种表示法也非常简单、直接。但是,在关联矩阵的所有nm个元素中,只
有 m2 个为非零元。如果网络比较稀疏,这种表示法也会浪费大量的存储空间。但由于
关联矩阵有许多特别重要的理论性质,因此它在网络优化中是非常重要的概念。
例 8 对于例 7 所示的图,如果关联矩阵中每列对应弧的顺序为(1,2),(1,3),(2,4),
(3,2),(4,3),(4,5),(5,3)和(5,4),则关联矩阵表示为
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
−
−−
−−−
−−
11100000
10110100
01011010
00001101
00000011
同样,对于网络中的权,也可以通过对关联矩阵的扩展来表示。例如,如果网络中
每条弧有一个权,我们可以把关联矩阵增加一行,把每一条弧所对应的权存储在增加的
行中。如果网络中每条弧赋有多个权,我们可以把关联矩阵增加相应的行数,把每一条
弧所对应的权存储在增加的行中。
(iii)弧表表示法
弧表表示法将图以弧表(arc list)的形式存储在计算机中。所谓图的弧表,也就是
图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点,共需 m2 个存
储单元,因此当网络比较稀疏时比较方便。此外,对于网络图中每条弧上的权,也要对
应地用额外的存储单元表示。例如,例 7 所示的图,假设弧(1,2),(1,3),(2,4),(3,2),
(4,3),(4,5),(5,3)和(5,4)上的权分别为 8,9,6,4,0,3,6 和 7,则弧表表示如表 1
所示。
表 1
起点 1 1 2 3 4 4 5 5
终点 2 3 4 2 3 5 3 4
权 8 9 6 4 0 3 6 7
为了便于检索,一般按照起点、终点的字典序顺序存储弧表,如上面的弧表就是按
照这样的顺序存储的。
(iv)邻接表表示法
邻接表表示法将图以邻接表(adjacency lists)的形式存储在计算机中。所谓图的
邻接表,也就是图的所有节点的邻接表的集合;而对每个节点,它的邻接表就是它的所
有出弧。邻接表表示法就是对图的每个节点,用一个单向链表列出从该节点出发的所有
弧,链表中每个单元对应于一条出弧。为了记录弧上的权,链表中每个单元除列出弧的
另一个端点外,还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数
组表示。例如,例 7 所示的图,邻接表表示为
-73-
这是一个 5 维指针数组,每一维(上面表示法中的每一行)对应于一个节点的邻接
表,如第 1 行对应于第 1 个节点的邻接表(即第 1 个节点的所有出弧)。每个指针单元
的第 1 个数据域表示弧的另一个端点(弧的头),后面的数据域表示对应弧上的权。如
第 1 行中的“2”表示弧的另一个端点为 2(即弧为(1,2)),“8”表示对应弧(1,2)上的
权为 8;“3”表示弧的另一个端点为 3(即弧为(1,3)),“9”表示对应弧(1,3)上的权
为 9。又如,第 5 行说明节点 5 出发的弧有(5,3)、(5,4),他们对应的权分别为 6 和 7。
对于有向图 ),( AVG = ,一般用 )(iA 表示节点 i的邻接表,即节点 i的所有出弧构
成的集合或链表(实际上只需要列出弧的另一个端点,即弧的头)。例如上面例子,
}3,2{)1( =A , }4,3{)5( =A 等。
(v)星形表示法
星形(star)表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点,
它也是记录从该节点出发的所有弧,但它不是采用单向链表而是采用一个单一的数组表
示。也就是说,在该数组中首先存放从节点 1 出发的所有弧,然后接着存放从节点 2
出发的所有孤,依此类推,最后存放从节点n出发的所有孤。对每条弧,要依次存放其
起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号,
只是从同一节点出发的弧的顺序可以任意排列。此外,为了能够快速检索从每个节点出
发的所有弧,我们一般还用一个数组记录每个节点出发的弧的起始地址(即弧的编号)。
在这种表示法中,可以快速检索从每个节点出发的所有弧,这种星形表示法称为前向星
形(forward star)表示法。
例如,在例 7 所示的图中,仍然假设弧(1,2),(l,3),(2,4),(3,2),(4,3),(4,5),
(5,3)和(5,4)上的权分别为 8,9,6,4,0,3,6 和 7。此时该网络图可以用前向
星形表示法表示为表 2 和表 3 。
表 2 节点对应的出弧的起始地址编号数组
节点号 i 1 2 3 4 5 6
起始地址 )(ipoint 1 3 4 5 7 9
表 3 记录弧信息的数组
弧编号 1 2 3 4 5 6 7 8
起点 1 1 2 3 4 4 5 5
终点 2 3 4 2 3 5 3 4
权 8 9 6 4 0 3 6 7
在数组 point中,其元素个数比图的节点数多 1(即 1+n ),且一定有 1)1( =point ,
1)1( +=+ mnpoint 。对于节点 i,其对应的出弧存放在弧信息数组的位置区间为
]1)1(),([ −+ipointipoint ,
如果 )1()( += ipointipoint ,则节点 i没有出弧。这种表示法与弧表表示法也非常相
-74-
似,“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在前向星形表示法中,
弧被编号后有序存放,并增加一个数组( point)记录每个节点出发的弧的起始编号。
前向星形表示法有利于快速检索每个节点的所有出弧,但不能快速检索每个节点的
所有入弧。为了能够快速检索每个节点的所有入孤,可以采用反向星形(reverse star)
表示法:首先存放进入节点 1 的所有孤,然后接着存放进入节点 2 的所有弧,依此类推,
最后存放进入节点n的所有孤。对每条弧,仍然依次存放其起点、终点、权的数值等有
关信息。同样,为了能够快速检索从每个节点的所有入弧,我们一般还用一个数组记录
每个节点的入孤的起始地址(即弧的编号)。例如,例 7 所示的图,可以用反向星形表
示法表示为表 4 和表 5。
表 4 节点对应的入弧的起始地址编号数组
节点号 i 1 2 3 4 5 6
起始地址 )(irpoint 1 1 3 6 8 9
表 5 记录弧信息的数组
弧编号 1 2 3 4 5 6 7 8
终点 2 2 3 3 3 4 4 5
起点 3 1 1 4 5 5 2 4
权 4 8 9 0 6 7 6 3
如果既希望快速检索每个节点的所有出弧,也希望快速检索每个节点的所有入弧,
则可以综合采用前向和反向星形表示法。当然,将孤信息存放两次是没有必要的,可以
只用一个数组(trace)记录一条弧在两种表示法中的对应关系即可。例如,可以在采用
前向星形表示法的基础上,加上上面介绍的 rpoint数组和如下的 trace数组即可。这相
当于一种紧凑的双向星形表示法,如表 6 所示。
表 6 两种表示法中的弧的对应关系
反向法中弧编号 j 1 2 3 4 5 6 7 8
正向法中弧编号 )( jtrace 4 1 2 5 7 8 3 6
对于网络图的表示法,我们作如下说明:
① 星形表示法和邻接表表示法在实际算法实现中都是经常采用的。星形表示法的
优点是占用的存储空间较少,并且对那些不提供指针类型的语言(如 FORTRAN 语言
等)也容易实现。邻接表表示法对那些提供指针类型的语言(如 C 语言等)是方便的,
且增加或删除一条弧所需的计算工作量很少,而这一操作在星形表示法中所需的计算工
作量较大(需要花费 )(mO 的计算时间)。有关“计算时间”的观念是网络优化中需要
考虑的一个关键因素。
② 当网络不是简单图,而是具有平行弧(即多重弧)时,显然此时邻接矩阵表示
法是不能采用的。其他方法则可以很方便地推广到可以处理平行弧的情形。
③ 上述方法可以很方便地推广到可以处理无向图的情形,但由于无向图中边没有
方向,因此可能需要做一些自然的修改。例如,可以在计算机中只存储邻接矩阵的一半
信息(如上三角部分),因为此时邻接矩阵是对称矩阵。无向图的关联矩阵只含有元素
0 和 1+ ,而不含有 1− ,因为此时不区分边的起点和终点。又如,在邻接表和星形表示
法中,每条边会被存储两次,而且反向星形表示显然是没有必要的,等等。
2.7 轨与连通
kkveevevW L2110= ,其中 )(GEei ∈ , ki ≤≤1 , )(GVv j ∈ , kj ≤≤0 , ie 与
-75-
ii vv ,1− 关联,称W 是图G 的一条道路(walk),k 为路长,顶点 0v 和 kv 分别称为W 的起
点和终点,而 121 ,,, −kvvv L 称为它的内部顶点。
若道路W 的边互不相同,则W 称为迹(trail)。若道路W 的顶点互不相同,则W 称
为轨(path)。
称一条道路是闭的,如果它有正的长且起点和终点相同。起点和终点重合的轨叫做
圈(cycle)。
若图G 的两个顶点 vu, 间存在道路,则称u和 v连通(connected)。 vu, 间的最短轨
的长叫做 vu, 间的距离。记作 ),( vud 。若图G 的任二顶点均连通,则称G 是连通图。
显然有:
(i) 图P是一条轨的充要条件是P是连通的,且有两个一度的顶点,其余顶点的度
为 2;
(ii) 图C是一个圈的充要条件是C是各顶点的度均为 2 的连通图。
§3 应用—最短路问题
3.1 两个指定顶点之间的最短路径
问题如下:给出了一个连接若干个城镇的铁路网络,在这个网络的两个指定城镇间,
找一条最短铁路线。
以各城镇为图G 的顶点,两城镇间的直通铁路为图G相应两顶点间的边,得图G。
对G 的每一边 e,赋以一个实数 )(ew —直通铁路的长度,称为 e的权,得到赋权图G。
G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点 00 ,vu
间的具最小权的轨。这条轨叫做 00 ,vu 间的最短路,它的权叫做 00 ,vu 间的距离,亦记
作 ),( 00 vud 。
求最短路已有成熟的算法:迪克斯特拉(Dijkstra)算法,其基本思想是按距 0u 从
近到远为顺序,依次求得 0u 到G 的各顶点的最短路和距离,直至 0v (或直至G 的所有
顶点),算法结束。为避免重复并保留每一步的计算信息,采用了标号算法。下面是该
算法。
(i) 令 0)( 0 =ul ,对 0uv ≠ ,令 ∞=)(vl , }{ 00 uS = , 0=i 。
(ii) 对每个 iSv∈ ( ii SVS \= ),用
)}()(),({min uvwulvl
iSu
+∈
代替 )(vl 。计算 )}({min vl
iSv∈
,把达到这个最小值的一个顶点记为 1+iu ,令
}{ 11 ++ = iii uSS U 。
(iii). 若 1|| −= Vi ,停止;若 1|| −< Vi ,用 1+i 代替 i,转(ii)。
算法结束时,从 0u 到各顶点 v的距离由 v的最后一次的标号 )(vl 给出。在 v进入 iS
之前的标号 )(vl 叫 T 标号, v进入 iS 时的标号 )(vl 叫 P 标号。算法就是不断修改各顶
点的 T 标号,直至获得 P 标号。若在算法运行过程中,将每一顶点获得 P 标号所由来
的边在图上标明,则算法结束时, 0u 至各项点的最短路也在图上标示出来了。
例 9 某公司在六个城市 621 ,,, ccc L 中有分公司,从 ic 到 jc 的直接航程票价记在
下述矩阵的 ),( ji 位置上。(∞表示无直接航路),请帮助该公司设计一张城市 1c 到其它
-76-
城市间的票价最便宜的路线图。
⎥⎥
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢
⎣
⎡
∞
∞
∞∞
∞
∞
055252510
550102025
25100102040
2010015
252015050
102540500
用矩阵 nna ×(n为顶点个数)存放各边权的邻接矩阵,行向量 pb、 1index 、 2index 、
d 分别用来存放 P标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分
量
⎩⎨
⎧=
顶点未标号当第
顶点已标号当第
i
i
ipb
0
1
)( ;
)(2 iindex 存放始点到第 i点最短通路中第 i顶点前一顶点的序号;
)(id 存放由始点到第 i点最短通路的值。
求第一个城市到其它城市的最短路径的 Matlab 程序如下:
clc,clear
a=zeros(6);
a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;
a(2,3)=15;a(2,4)=20;a(2,6)=25;
a(3,4)=10;a(3,5)=20;
a(4,5)=10;a(4,6)=25;
a(5,6)=55;
a=a+a';
a(find(a==0))=inf;
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));
d(1:length(a))=inf;d(1)=0;temp=1;
while sum(pb)
计划
项目进度计划表范例计划下载计划下载计划下载课程教学计划下载
从城市 A
到城市D铺设一条天然气管道,请设计出最小价格管道铺设方案。
图 3 7 个城市间的连线图
编写 LINGO 程序如下:
model:
sets:
cities/A,B1,B2,C1,C2,C3,D/;
roads(cities,cities)/A B1,A B2,B1 C1,B1 C2,B1 C3,B2 C1,
B2 C2,B2 C3,C1 D,C2 D,C3 D/:w,x;
endsets
data:
w=2 4 3 3 1 2 3 1 1 3 4;
enddata
n=@size(cities); !城市的个数;
min=@sum(roads:w*x);
@for(cities(i)|i #ne#1 #and# i #ne#n:
@sum(roads(i,j):x(i,j))=@sum(roads(j,i):x(j,i)));
@sum(roads(i,j)|i #eq#1:x(i,j))=1;
@sum(roads(i,j)|j #eq#n:x(i,j))=1;
end
例 11(无向图的最短路问题)求图 4 中 1v 到 11v 的最短路。
分析 例 10 处理的问题属于有向图的最短路问题,本例是处理无向图的最短路问
题,在处理方式上与有向图的最短路问题有一些差别,这里选择赋权邻接矩阵的方法编
写 LINGO 程序。
-78-
图 4 无向图的最短路问题
编写 LINGO 程序如下:
model:
sets:
cities/1..11/;
roads(cities,cities):w,x;
endsets
data:
w=0;
enddata
calc:
w(1,2)=2;w(1,3)=8;w(1,4)=1;
w(2,3)=6;w(2,5)=1;
w(3,4)=7;w(3,5)=5;w(3,6)=1;w(3,7)=2;
w(4,7)=9;
w(5,6)=3;w(5,8)=2;w(5,9)=9;
w(6,7)=4;w(6,9)=6;
w(7,9)=3;w(7,10)=1;
w(8,9)=7;w(8,11)=9;
w(9,10)=1;w(9,11)=2;w(10,11)=4;
@for(roads(i,j):w(i,j)=w(i,j)+w(j,i));
@for(roads(i,j):w(i,j)=@if(w(i,j) #eq# 0, 1000,w(i,j)));
endcalc
n=@size(cities); !城市的个数;
min=@sum(roads:w*x);
@for(cities(i)|i #ne#1 #and# i #ne#
n:@sum(cities(j):x(i,j))=@sum(cities(j):x(j,i)));
@sum(cities(j):x(1,j))=1;
@sum(cities(j):x(j,1))=0; !不能回到顶点1;
@sum(cities(j):x(j,n))=1;
@for(roads:@bin(x));
end
与有向图相比较,在程序中只增加了一个语句@sum(cities(j):x(j,1))=0,即
从顶点 1离开后,再不能回到该顶点。
求得的最短路径为 1→2→5→6→3→7→10→9→11,最短路径长度为 13。
3.3 每对顶点之间的最短路径
计算赋权图中各对顶点之间最短路径,显然可以调用 Dijkstra 算法。具体方法是:
每次以不同的顶点作为起点,用 Dijkstra 算法求出从该起点到其余顶点的最短路径,反
复执行 1−n 次这样的操作,就可得到从每一个顶点到其它顶点的最短路径。这种算法
的时间复杂度为 )( 3nO 。第二种解决这一问题的方法是由 Floyd R W 提出的算法,称
之为 Floyd 算法。
-79-
假设图G 权的邻接矩阵为 0A ,
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=
nnnn
n
n
aaa
aaa
aaa
A
L
MLMM
L
L
21
22221
11211
0
来存放各边长度,其中:
0=iia ni ,,2,1 L= ;
∞=ija ji, 之间没有边,在程序中以各边都不可能达到的充分大的数代替;
ijij wa = ijw 是 ji, 之间边的长度, nji ,,2,1, L= 。
对于无向图, 0A 是对称矩阵, jiij aa = 。
Floyd 算法的基本思想是:递推产生一个矩阵序列 nk AAAA ,,,,, 10 LL ,其中
),( jiAk 表示从顶点 iv 到顶点 jv 的路径上所经过的顶点序号不大于 k 的最短路径长
度。
计算时用迭代公式:
)),(),(),,(min(),( 111 jkAkiAjiAjiA kkkk −−− +=
k 是迭代次数, nkji ,,2,1,, L= 。
最后,当 nk = 时, nA 即是各顶点之间的最短通路值。
例12 用Floyd算法求解例9。
矩阵path用来存放每对顶点之间最短路径上所经过的顶点的序号。Floyd算法的
Matlab程序如下:
clear;clc;
n=6; a=zeros(n);
a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;
a(2,3)=15;a(2,4)=20;a(2,6)=25; a(3,4)=10;a(3,5)=20;
a(4,5)=10;a(4,6)=25; a(5,6)=55;
a=a+a'; M=max(max(a))*n^2; %M为充分大的正实数
a=a+((a==0)-eye(n))*M;
path=zeros(n);
for k=1:n
for i=1:n
for j=1:n
if a(i,j)>a(i,k)+a(k,j)
a(i,j)=a(i,k)+a(k,j);
path(i,j)=k;
end
end
end
end
a, path
我们使用LINGO9.0编写的FLOYD算法如下:
model:
sets:
-80-
nodes/c1..c6/;
link(nodes,nodes):w,path; !path标志最短路径上走过的顶点;
endsets
data:
path=0;
w=0;
@text(mydata1.txt)=@writefor(nodes(i):@writefor(nodes(j):
@format(w(i,j),' 10.0f')),@newline(1));
@text(mydata1.txt)=@write(@newline(1));
@text(mydata1.txt)=@writefor(nodes(i):@writefor(nodes(j):
@format(path(i,j),' 10.0f')),@newline(1));
enddata
calc:
w(1,2)=50;w(1,4)=40;w(1,5)=25;w(1,6)=10;
w(2,3)=15;w(2,4)=20;w(2,6)=25;
w(3,4)=10;w(3,5)=20;
w(4,5)=10;w(4,6)=25;w(5,6)=55;
@for(link(i,j):w(i,j)=w(i,j)+w(j,i));
@for(link(i,j) |i#ne#j:w(i,j)=@if(w(i,j)#eq#0,10000,w(i,j)));
@for(nodes(k):@for(nodes(i):@for(nodes(j):
tm=@smin(w(i,j),w(i,k)+w(k,j));
path(i,j)=@if(w(i,j)#gt# tm,k,path(i,j));w(i,j)=tm)));
endcalc
end
§4 树
4.1 基本概念
连通的无圈图叫做树,记之为T 。若图G 满足 )()( TVGV = , )()( GETE ⊂ ,
则称T 是G的生成树。图G连通的充分必要条件为G有生成树。一个连通图的生成树
的个数很多,用 )(Gτ 表示G的生成树的个数,则有公式
公式 (Caylay) 2)( −= nn nKτ 。
公式 )()()( eGeGG ⋅+−= τττ 。
其中 eG − 表示从G上删除边 e, eG ⋅ 表示把 e的长度收缩为零得到的图。
树有下面常用的五个充要条件。
定理 1 (i)G是树当且仅当G中任二顶点之间有且仅有一条轨道。
(ii)G 是树当且仅当G 无圈,且 1−=νε 。
(iii)G是树当且仅当G连通,且 1−=νε 。
(iv)G是树当且仅当G连通,且 )(GEe∈∀ , eG − 不连通。
(v)G 是树当且仅当G 无圈, )(GEe∉∀ , eG + 恰有一个圈。
4.2 应用—连线问题
欲修筑连接 n个城市的铁路,已知 i城与 j城之间的铁路造价为 ijC ,设计一个线
路图,使总造价最低。
连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生
成树叫做最小生成树。
下面介绍构造最小生成树的两种常用算法。
4.2.1 prim 算法构造最小生成树
设置两个集合P和Q ,其中 P用于存放G 的最小生成树中的顶点,集合Q存放G
-81-
的最小生成树中的边。令集合P的初值为 }{ 1vP = (假设构造最小生成树时,从顶点 1v
出发),集合Q的初值为 Φ=Q 。prim 算法的思想是,从所有 Pp∈ , PVv −∈ 的边
中,选取具有最小权值的边 pv,将顶点 v加入集合P中,将边 pv加入集合Q中,如
此不断重复,直到 VP = 时,最小生成树构造完毕,这时集合Q中包含了最小生成树
的所有边。
prim 算法如下:
(i) }{ 1vP = , Φ=Q ;
(ii)while VP =~
找最小边 pv,其中 PVvPp −∈∈ ,
}{vPP +=
}{pvQQ +=
end
图 5 最小生成树问题
例 13 用 prim 算法求图 5 的最小生成树。
我们用 nresult ×3 的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab
程序如下:
clc;clear;
a=zeros(7);
a(1,2)=50; a(1,3)=60;
a(2,4)=65; a(2,5)=40;
a(3,4)=52;a(3,7)=45;
a(4,5)=50; a(4,6)=30;a(4,7)=42;
a(5,6)=70;
a=a+a';a(find(a==0))=inf;
result=[];p=1;tb=2:length(a);
while length(result)~=length(a)-1
temp=a(p,tb);temp=temp(:);
d=min(temp);
[jb,kb]=find(a(p,tb)==d);
j=p(jb(1));k=tb(kb(1));
result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
end
result
4.2.1 Kruskal 算法构造最小生成树
科茹斯克尔(Kruskal)算法是一个好算法。Kruskal 算法如下:
(i)选 )(1 GEe ∈ ,使得 min)( 1 =ew 。
-82-
(ii)若 ieee ,,, 21 L 已选好,则从 },,,{)( 21 ieeeGE L− 中选取 1+ie ,使得
① }],,,,[{ 121 +ii eeeeG L 中无圈,且
② min)( 1 =+iew 。
(iii)直到选得 1−νe 为止。
例 14 用 Kruskal 算法构造例 3 的最小生成树。
我们用 nindex ×2 存放各边端点的信息,当选中某一边之后,就将此边对应的顶点序
号中较大序号u改记为此边的另一序号 v,同时把后面边中所有序号为u的改记为 v。
此方法的几何意义是:将序号u的这个顶点收缩到 v顶点,u顶点不复存在。后面继续
寻查时,发现某边的两个顶点序号相同时,认为已被收缩掉,失去了被选取的资格。
Matlab 程序如下:
clc;clear;
a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;
a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;
a(4,7)=42; a(5,6)=70;
[i,j,b]=find(a);
data=[i';j';b'];index=data(1:2,:);
loop=max(size(a))-1;
result=[];
while length(result)
的对集 'M ,则M 称为最大对集;若G 中有一轨,其边交替地在对集M 内外出现,则
称此轨为M 的交错轨,交错轨的起止顶点都未被许配时,此交错轨称为可增广轨。
若把可增广轨上在M 外的边纳入对集,把M 内的边从对集中删除,则被许配的
顶点数增加 2,对集中的“对儿”增加一个。
1957 年,贝尔热(Berge)得到最大对集的充要条件:
定理 2 M 是图G 中的最大对集当且仅当G 中无M 可增广轨。
1935 年,霍尔(Hall)得到下面的许配定理:
定理 3 G 为二分图, X 与Y 是顶点集的划分,G 中存在把 X 中顶点皆许配的
-83-
对集的充要条件是, XS ⊂∀ ,则 |||)(| SSN ≥ ,其中 )(SN 是 S 中顶点的邻集。
由上述定理可以得出:
推论 1:若G 是 k 次( )0>k 正则 2 分图,则G 有完美对集。
所谓 k 次正则图,即每顶点皆 k 度的图。
由此推论得出下面的婚配定理:
定理 4 每个姑娘都结识 )1( ≥kk 位小伙子,每个小伙子都结识 k 位姑娘,则每位
姑娘都能和她认识的一个小伙子结婚,并且每位小伙子也能和他认识的一个姑娘结婚。
人员分派问题等实际问题可以化成对集来解决。
人员分派问题:工作人员 nxxx ,,, 21 L 去做n件工作 nyyy ,,, 21 L ,每人适合做其
中一件或几件,问能否每人都有一份适合的工作?如果不能,最多几人可以有适合的工
作?
这个问题的数学模型是: G 是二分图,顶点集划分为 YXGV U=)( ,
},,{ 1 nxxX L= , },,{ 1 nyyY L= ,当且仅当 ix 适合做工作 jy 时, )(GEyx ji ∈ ,求
G 中的最大对集。
解决这个问题可以利用 1965 年埃德门兹(Edmonds)提出的匈牙利算法。
匈牙利算法:
(i)从G 中任意取定一个初始对集M 。
(ii)若M 把 X 中的顶点皆许配,停止,M 即完美对集;否则取 X 中未被M 许
配的一顶点u,记 }{uS = , Φ=T 。
(iii)若 TSN =)( ,停止,无完美对集;否则取 TSNy −∈ )( 。
(iv)若 y是被M 许配的,设 Myz∈ , }{zSS U= , }{yTT U= ,转(iii);
否则,取可增广轨 ),( yuP ,令 ))(())(( MPEPEMM −−= U ,转(ii)。
把以上算法稍加修改就能够用来求二分图的最大完美对集。
最优分派问题:在人员分派问题中,工作人员适合做的各项工作当中,效益未必一
致,我们需要制定一个分派方案,使公司总效益最大。
这个问题的数学模型是:在人员分派问题的模型中,图 G 的每边加了权
0)( ≥ji yxw ,表示 ix 干 jy 工作的效益,求加权图G 上的权最大的完美对集。
解决这个问题可以用库恩—曼克莱斯(Kuhn-Munkres)算法。为此,我们要引入
可行顶点标号与相等子图的概念。
定义 若映射 RGVl →)(: ,满足 YyXx ∈∈∀ , ,
),()()( yxwylxl ≥+ ,
则称 l 是二分图G 的可行顶点标号。令
)}()()(),(|{ xywylxlGExyxyEl =+∈= ,
称以 lE 为边集的G的生成子图为相等子图,记作 lG 。
可行顶点标号是存在的。例如
;),(max)( Xxxywxl
Yy
∈=
∈
Yyyl ∈= ,0)( 。
定理 5 lG 的完美对集即为G的权最大的完美对集。
Kuhn-Munkres 算法
-84-
(i)选定初始可行顶点标号 l ,确定 lG ,在 lG 中选取一个对集M 。
(ii)若 X 中顶点皆被M 许配,停止,M 即G的权最大的完美对集;否则,取 lG
中未被M 许配的顶点u,令 }{uS = , Φ=T 。
(iii)若 TSN
lG
⊃)( ,转(iv);若 TSN
lG
=)( ,取
)}()()({min
,
xywylxl
TySxl
−+=
∉∈
α ,
⎪⎩
⎪⎨
⎧
∈+
∈−
=
其它),(
,)(
,)(
)(
vl
Tvvl
Svvl
vl l
l
α
α
,
l