没有合适的资源?快使用搜索试试~ 我知道了~
第05章 图与网络.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 103 浏览量
2024-05-14
10:20:17
上传
评论
收藏 488KB PDF 举报
温馨提示
试读
50页
第05章 图与网络
资源推荐
资源详情
资源评论
-68-
第五章 图与网络模型及方法
§1 概论
图论起源于 18 世纪。第一篇图论论文是瑞士数学家欧拉于 1736 年发表的“哥尼
斯堡的七座桥”。1847 年,克希霍夫为了给出电网络方程而引进了“树”的概念。1857
年,凯莱在计数烷
22 +nn
HC
的同分异构物时,也发现了“树”。哈密尔顿于 1859 年提
出“周游世界”游戏,用图论的术语,就是如何找出一个连通图中的生成圈、近几十年
来,由于计算机技术和科学的飞速发展,大大地促进了图论研究和应用,图论的理论和
方法已经渗透到物理、化学、通讯科学、建筑学、运筹学,生物遗传学、心理学、经济
学、社会学等学科中。
图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示
这些具体事物,用连接两点的线段(直的或曲的)表示两个事物的特定的联系,就得到
了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了
一个数学模型,借助于图论的概念、理论和方法,可以对该模型求解。哥尼斯堡七桥问
题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结
起来,问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次,再回到起点。
图 1 哥尼斯堡七桥问题
当然可以通过试验去尝试解决这个问题,但该城居民的任何尝试均未成功。欧拉为了解
决这个问题,采用了建立数学模型的方法。他将每一块陆地用一个点来代替,将每一座
桥用连接相应两点的一条线来代替,从而得到一个有四个“点”,七条“线”的“图”。
问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特
点,给出了一笔画的一个判定法则:这个图是连通的,且每个点都与偶数线相关联,将
这个判定法则应用于七桥问题,得到了“不可能走通”的结果,不但彻底解决了这个问
题,而且开创了图论研究的先河。
图与网络是运筹学(Operations Research)中的一个经典和重要的分支,所研究的
问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等
诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都
是图与网络的基本问题。
我们首先通过一些例子来了解网络优化问题。
例 1 最短路问题(SPP-shortest path problem)
一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的
公路网纵横交错,因此有多种行车路线,这名司机应选择哪条线路呢?假设货柜车的运
行速度是恒定的,那么这一问题相当于需要找到一条从甲地到乙地的最短路。
例 2 公路连接问题
某一地区有若干个主要城市,现准备修建高速公路把这些城市连接起来,使得从其
-69-
中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两
个城市之间修建高速公路的成本,那么应如何决定在哪些城市间修建高速公路,使得总
成本最小?
例 3 指派问题(assignment problem)
一家公司经理准备安排
N
名员工去完成
N
项任务,每人一项。由于各员工的特点
不同,不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以
使总回报最大?
例 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 n
vvvGV L= 称为图 G 的顶点集(vertex set)或节点集(node set),
)(GV
中
的每一个元素
),,2,1( niv
i
L= 称为该图的一个顶点(vertex)或节点(node);
},,,{)(
21 m
eeeGE L= 称为图 G 的边集(edge set),
)(GE
中的每一个元素
k
e (即
)(GV
中某两个元素
ji
vv ,
的无序对) 记为
),(
jik
vve
=
或
ijjik
vvvve
=
=
),,2,1( mk L=
,
被称为该图的一条从
i
v 到
j
v 的边(edge)。
当边
jik
vve = 时,称
ji
vv , 为边
k
e 的端点,并称
j
v 与
i
v 相邻(adjacent);边
k
e 称
为与顶点
ji
vv ,
关联(incident)。如果某两条边至少有一个公共端点,则称这两条边在
图
G 中相邻。
边上赋权的无向图称为赋权无向图或无向网络(undirected network)。我们对图和
网络不作严格区分,因为任何图总是可以赋权的。
-70-
一个图称为有限图,如果它的顶点集和边集都有限。图 G 的顶点数用符号 ||V 或
)(G
ν
表示,边数用 || E 或 )(G
ε
表示。
当讨论的图只有一个时,总是用
G 来表示这个图。从而在图论符号中我们常略去
字母
G ,例如,分别用
ν
,,
E
V 和
ε
代替 )(),(),( GGEGV
ν
和 )(G
ε
。
端点重合为一点的边称为环(loop)。
一个图称为简单图(simple graph),如果它既没有环也没有两条边连接同一对顶点。
2.2 有向图
定义 一个有向图(directed graph 或 digraph)
G 是由一个非空有限集合V 和V 中
某些元素的有序对集合
A构成的二元组,记为 ),( AVG
=
。其中 },,,{
21 n
vvvV L
=
称
为图
G
的顶点集或节点集, V 中的每一个元素 ),,2,1( niv
i
L
=
称为该图的一个顶点
或节点;
},,,{
21 m
aaaA L= 称为图
G
的弧集(arc set),A 中的每一个元素
k
a (即V 中
某两个元素
ji
vv , 的有序对) 记为 ),(
jik
vva
=
或 ),,2,1( nkvva
jik
L
=
=
,被称为该图
的一条从
i
v 到
j
v 的弧(arc)。
当弧
jik
vva = 时,称
i
v 为
k
a 的尾(tail),
j
v 为
k
a 的头(head),并称弧
k
a 为
i
v 的
出弧(outgoing arc),为
j
v 的入弧(incoming arc)。
对应于每个有向图
D ,可以在相同顶点集上作一个图 G ,使得对于 D 的每条弧,
G 有一条有相同端点的边与之相对应。这个图称为 D 的基础图。反之,给定任意图 G ,
对于它的每个边,给其端点指定一个顺序,从而确定一条弧,由此得到一个有向图,这
样的有向图称为
G 的一个定向图。
以下若未指明“有向图”三字,“图”字皆指无向图。
2.3 完全图、二分图
每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。
n 个顶点
的完全图记为
n
K 。
若
YXGV U=)( ,
Φ
=YX I , 0||||
≠
YX (这里 || X 表示集合
X
中的元素个
数),
X
中无相邻顶点对,
Y
中亦然,则称 G 为二分图(bipartite graph);特别地,若
YyXx ∈∀∈∀ , ,则 )(GExy ∈ ,则称 G 为完全二分图,记成
|||,| YX
K 。
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
−
矩阵,即
nn
nnij
cC
×
×
∈= }1,0{)( ,
⎩
⎨
⎧
∉
∈
=
.),(,0
,),(,1
Aji
Aji
c
ij
也就是说,如果两节点之间有一条弧,则邻接矩阵中对应的元素为 1;否则为 0。
可以看出,这种表示法非常简单、直接。但是,在邻接矩阵的所有
2
n 个元素中,只有 m
个为非零元。如果网络比较稀疏,这种表示法浪费大量的存储空间,从而增加了在网络
中查找弧的时间。
图 2 有向图
例 7 对于图 2 所示的有向图,可以用邻接矩阵表示为
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
01100
10100
00010
01000
00110
同样,对于网络中的权,也可以用类似邻接矩阵的 nn
×
矩阵表示。只是此时一条
弧所对应的元素不再是 1,而是相应的权而已。如果网络中每条弧赋有多种权,则可以
用多个矩阵表示这些权。
(ii)关联矩阵表示法
关联矩阵表示法是将图以关联矩阵(incidence matrix)的形式存储在计算机中.图
),( AVG = 的关联矩阵
B
是如下定义的:
B
是一个 mn
×
的矩阵,即
mn
mnik
bB
×
×
−∈= }1,0,1{)( ,
-72-
⎪
⎩
⎪
⎨
⎧
∈=∈∃−
∈=∈∃
=
.,0
,),(, ,1
,),(,,1
其它
AijkVj
AjikVj
b
ik
也就是说,在关联矩阵中,每行对应于图的一个节点,每列对应于图的一条弧。如
果一个节点是一条弧的起点,则关联矩阵中对应的元素为 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 所示的图,邻接表表示为
剩余49页未读,继续阅读
资源评论
人工智能_SYBH
- 粉丝: 4w+
- 资源: 220
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功