nbhkdz.com冰点文库

高中奥数专题——图论

时间:2017-04-13


例1 最短路问题

(SPP-shortest path problem)
一名货柜车司机奉命在最短的时间内将一车货物从 甲地运往乙地。从甲地到乙地的公路网纵横交错,因 此有多种行车路线,这名司机应选择哪条线路呢?假 设货柜车的运行速度是恒定的,那么这一问题相当于 需要找到一条从甲地到乙地的最短路。

例2 公路连接问题 某一地区有若干个主要城市,现准备修建高速公 路把这些城市连接起来,使得从其中任何一个城市 都可以经高速公路直接或间接到达另一个城市。假 定已经知道了任意两个城市之间修建高速公路的成 本,那么应如何决定在哪些城市间修建高速公路, 使得总成本最小?

例3 运输问题(transportation problem) 某种原材料有N个产地,现在需要将原材料从产地 运往M个使用这些原材料的工厂。假定N个产地的产 量和 M 家工厂的需要量已知,单位产品从任一产地 到任一工厂的运费已知,那么如何安排运输方案可 以使总运输成本最低?

例4 中国邮递员问题 (CPP-Chinese postman problem) 一名邮递员负责投递某个街区的邮件。如何为他 (她)设计一条最短的投递路线(从邮局出发,经过 投递区内每条街道至少一次,最后返回邮局)?由于 这一问题是我国管梅谷教授 1960年首先提出的,所以 国际上称之为中国邮递员问题。

例5 旅行商问题 (TSP-traveling salesman problem) 一名推销员准备前往若干城市推销产品。如何为他 (她)设计一条最短的旅行路线(从驻地出发,经过 每个城市恰好一次,最后返回驻地)?这一问题的研 究历史十分悠久,通常称之为旅行商问题。

上述问题有两个共同的特点: 一、 它们的目的都是从若干可能的安排或方案 中寻求某种意义下的最优安排或方案,数学上把这种 问题称为最优化或优化(optimization)问题; 二、 它们都易于用图形的形式直观地描述和表 达,数学上把这种与图相关的结构称为网络 (network)。
与图和网络相关的最优化问题就是网络最优化或称 网络优化 (network optimization)问题。 上面例子中介绍的问题都是网络优化问题。多数网 络优化问题是以网络上的流(flow)为研究对象,因此 网络优化又常常被称为网络流(network flows)或网络 流规划等。

98年全国大学生数学建模竞赛B题“最佳灾 情巡视路线”中的前两个问题是这样的: 今年(1998年)夏天某县遭受水灾. 为考察灾情、

组织自救,县领导决定,带领有关部门负责人到
全县各乡(镇)、村巡视. 巡视路线指从县政府

所在地出发,走遍各乡(镇)、村,又回到县政
府所在地的路线.

1)若分三组(路)巡视,试设计总路程最 短且各组尽可能均衡的巡视路线. 2)假定巡视人员在各乡(镇)停留时间T=2 小时,在各村停留时间t =1小时,汽车行驶速度V =35公里/小时. 要在24小时内完成巡视,至少应分 几组;给出这种分组下最佳的巡视路线.

公路边的数字为该路段的公里数.

2004年A题 奥运会临时超市网点设计
2008年北京奥运会的建设工作已经进入全面设计 和实施阶段。奥运会期间,在比赛主场馆的周边地区 需要建设由小型商亭构建的临时商业网点,称为迷你 超市(Mini Supermarket, 以下记做MS)网,以满足 观众、游客、工作人员等在奥运会期间的购物需求, 主要经营食品、奥运纪念品、旅游用品、文体用品和 小日用品等。 在比赛主场馆周边地区设置的这种MS, 在地点、大小类型和总量方面有三个基本要求:满足 奥运会期间的购物需求、分布基本均衡和商业上赢利。

2004A:奥运会临时超市网点的设计问题 ? 题型:属于社会事业问题,主要包括观众的出行、用餐 和购物的规律,各商区人流分布规律,以及各商区的大小 超市的设计数量等问题。 ? 特点:海量数据、数据冗余、结构复杂,即时性、综 合性、实用性和开放性强。 ? 方法:主题方法数据的处理、统计分析、数据挖掘、 数学规划等。 ? 结果:不唯一,对结果没有明确要求。

图论模型
1. 问题引入与分析 2. 图论的基本概念 3. 最短路问题及算法

4. 最小生成树及算法
5. 旅行售货员问题

6. 模型建立与求解

18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块, 它们通过七座桥相互连接,如下图.当时该城的市民 热衷于这样一个游戏:“一个散步者怎样才能从某块 陆地出发,经每座桥一次且仅一次回到出发点?”
C

A

B

D 哥尼斯堡七桥示意图

七桥问题看起来不难,很多人都想试一试,但没有人 找到答案。后来有人写信告诉了当时的著名数学家欧拉。 千百人的失败使欧拉猜想,也许那样的走法根本不可能。 1876年,他证明了自己的猜想。 Euler把南北两岸和两个岛抽象成四个点,将连接这些 陆地的桥用连接相应两点的一条线来表示,就得到如下一 个简图:
C

七桥问题的分析

A

B D

欧拉的结论
欧拉指出:一个线图中存在通过每边一次仅一次回到 出发点的路线的充要条件是: 1)图是连通的,即任意两点可由图中的一些边连接起来; 2)与图中每一顶点相连的边必须是偶数. 由此得出结论:七桥问题无解. 欧拉由七桥问题所引发的研究论文是图论的开篇之作, 因此称欧拉为图论之父.
C A D

B

七桥问题
答案是
C A B D



否定的

因 为 图 中 没 有 偶 度 顶 点

欧拉指出:如果每块陆地所连接的桥都是偶数座, 则从任一陆地出发,必能通过每座桥恰好一次而回到 出发地。

欧拉图
定义 在无向连通简单图中,通过图中每边一次且仅 一次并行遍每个结点的一条通路(回路), 称为该图的 一条欧拉通路(回路)。存在欧拉回路的图称为欧拉图。 ? 一笔画问题:欧拉通路或欧拉回路。

无欧拉通路或欧拉回路

欧拉通路

欧拉回路

例 下列图是否可以一笔画出来.
A

×





B

问题2:哈密顿圈(环球旅行游戏)

1

8
20 19

9
10

16

18

11 12

十二面体的20个顶 点代表世界上20个城 市,能否从某个城市 出发在十二面体上依 次经过每个城市恰好 一次最后回到出发点?

17 15

2 14

13

6

7

5
4

3

问题2:哈密顿圈(环球旅行游戏)

十二面体的20个顶 点代表世界上20个城 市,能否从某个城市 出发在十二面体上依 次经过每个城市恰好 一次最后回到出发点?

哈密顿圈(环球旅行游戏)

哈密顿图
定义 经过图中每个结点一次且仅一次的通路(回路), 称为哈密顿通路(回路)。存在哈密顿回路的图称为 哈密顿图。

哈密顿图

哈密顿图

无哈密顿 通路

存在哈密 顿通路

问题3(关键路径问题): 一项工程任务,大到建造一座大坝,一座体育中心, 小至组装一台机床,一架电视机, 都要包括许多工序.这些 工序相互约束,只有在某些工序完成之后, 一个工序才能 开始. 即它们之间存在完成的先后次序关系,一般认为这 些关系是预知的, 而且也能够预计完成每个工序所需要的 时间. 这时工程领导人员迫切希望了解最少需要多少时间才 能够完成整个工程项目, 影响工程进度的要害工序是哪几 个?

图的作用
图是一种表示工具,改变问题的描述方式,往往是创造性的 启发式解决问题的手段.一种描述方式就好比我们站在一个位 置和角度观察目标,有的东西被遮挡住了,但如果换一个位置和 角度,原来隐藏着的东西就可能被发现.采用一种新的描述方式, 可能会产生新思想.图论中的图提供了一种直观,清晰表达已知 信息的方式.它有时就像小学数学应用题中的线段图一样,能使 我们用语言描述时未显示的或不易观察到的特征、关系,直观 地呈现在我们面前,帮助我们分析和思考问题,激发我们的灵感.

图的广泛应用
图的应用是非常广泛的,在工农业生产、交通运输、 通讯和电力领域经常都能看到许多网络,如河道网、灌 溉网、管道网、公路网、铁路网、电话线网、计算机 通讯网、输电线网等等。还有许多看不见的网络,如各 种关系网,像状态转移关系、事物的相互冲突关系、工 序的时间先后次序关系等等,这些网络都可以归结为图 论的研究对象----图.其中存在大量的网络优化问题需要 我们解决.还有象生产计划、投资计划、设备更新等问 题也可以转化为网络优化的问题.

基本的网络优化问题
基本的网络优化问题有:最短路径问题、最小生成树问题、 最大流问题和最小费用问题.图论作为数学的一个分支,已经有有 效的算法来解决这些问题.当然这当中的有些问题也可以建立线性 规划的模型,但有时若变量特别多,约束也特别多,用线性规划的 方法求解效率不高甚至不能在可忍受的时间内解决.而根据这些 问题的特点,采用网络分析的方法去求解可能会非常有效. 例如,在1978年,美国财政部的税务分析部门在对卡特尔税制 改革做评估的过程中,就有一个100,000个约束以上,25,000,000个 变量的问题,若用普通的线性规划求解,预计要花7个月的时间.他 们利用网络分析的方法,将其分解成6个子问题,利用特殊的网络计 算机程序,花了大约7个小时问题就得到了解决.

2.图论的基本概念
1) 图的概念 2) 赋权图与子图 3) 图的矩阵表示 4) 图的顶点度 5) 路和连通

1) 图的概念

定义 一个图G是指一个二元组(V(G),E(G)),其中: ?1)V (G) ? {v1, v2 ,?, v? }是非空有限集,称为顶点集, 其中元素称为图G的顶点. ?2) E(G)是顶点集V(G)中的无序或有序的元素偶对 (vi , v j ) 组成的集合,即称为边集,其中元素称为边. 定义 图G的阶是指图的顶点数|V(G)|, 用 图的边的数目|E(G)|用 ? 来表示.

v 来表示;

用 G ? (V (G ), E (G )) 表示图,简记 G ? (V , E ). 也用 vi v j 来表示边 (vi , v j ).

例设 G ? (V (G ), E (G )) , 其中:V (G) ? {v1, v2 , v3 , v4},
E (G ) ? {e1, e2 , e3 , e4 , e5 , e6} , e1 ? v1v1,e2 ? v2v3,e3 ? v1v3,

e4 ? v1v4 , e5 ? v3v4 , e6 ? v3v4 .

(见图 2)

图. 称边 e ? (vi , v j ) 为有向边或弧,称 e ? (vi , v j )是从vi 连接 v j 的弧 ,称 vi 为e的尾,称 v j 为e的头. 若图G中的边均为无序偶对 vi v j ,称G为无向图.称 边 e ? viv j 为无向边,称e连接 vi 和 v j ,顶点 vi 和 v j 称 为e的端点. 既有无向边又有有向边的图称为混合图.

定义 若图G中的边均为有序偶对 (vi , v j ) ,称G为有向

无向图

有向图

有向图实例─ 道路图

对于一个图G = (V, E ), 人们常用图形来表示它, 称其 为图解. 凡是有向边, 在图解上都用箭头标明其方向. 例如, 设V = {v1 , v2 , v3 , v4}, E = { v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4}, 则G = (V, E ) 是一个有4个顶点和6条边的图, G的图解如下图所示.

一个图会有许多外形不同的图解, 下面两个图表示同 一个图G = (V, E )的图解.其中 V = {v1 , v2 , v3 , v4}, E = { v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4}.

今后将不计较这种外形上的差别,而用一个容易理解 的、确定的图解去表示一个图.

常用术语
1)边和它的两端点称为互相关联. 2)与同一条边关联的两个端点称 为相邻的顶点,与同一个顶点 点关联的两条边称为相邻的边. 3) 端点重合为一点的边称为环, 4) 若一对顶点之间有两条以上的边联结,则这些边 称为重边. 5) 既没有环也没有重边的图,称为简单图.

2) 图的顶点度
定义 1) 在无向图G中,与顶点v关联的边的数目(环 算两次),称为顶点v的度或次数,记为d(v)或 dG(v). 称度为奇数的顶点为奇点,度为偶数的顶点为偶点. 2) 在有向图中,从顶点v引出的边的数目称为顶点 v的出度,记为d+(v),从顶点v引入的边的数目称为 v的入度,记为d -(v). 称d(v)= d+(v)+d -(v)为顶点v的 度或次数.
d ? (u3 ) ? 1

d (v1 ) ? 4

d ? (u3 ) ? 2

d (u3 ) ? 3

2) 图的顶点度
定义 1) 在无向图G中,与顶点v关联的边的数目(环 算两次),称为顶点v的度或次数,记为d(v)或 dG(v). 称度为奇数的顶点为奇点,度为偶数的顶点为偶点. 2) 在有向图中,从顶点v引出的边的数目称为顶点 v的出度,记为d+(v),从顶点v引入的边的数目称为 v的入度,记为d -(v). 称d(v)= d+(v)+d -(v)为顶点v的 度或次数.

d(v1)= d(v3)= d(v4)=4, d(v2)=2.

2) 图的顶点度
定义 1) 在无向图G中,与顶点v关联的边的数目(环 算两次),称为顶点v的度或次数,记为d(v)或 dG(v). 称度为奇数的顶点为奇点,度为偶数的顶点为偶点. 2) 在有向图中,从顶点v引出的边的数目称为顶点 v的出度,记为d+(v),从顶点v引入的边的数目称为 v的入度,记为d -(v). 称d(v)= d+(v)+d -(v)为顶点v的 度或次数. 定理
v?V

? d (v) ? 2? . 图中各点度数之和是边数的2倍

握手定理
推论 任何图中奇点的个数为偶数.

定理

v?V

? d (v) ? 2? . 图中各点度数之和是边数的2倍

握手定理
图中的每条边均有两个端点,所以在计算中所有顶点 度数之和时,每条边提供度数为2。

推论 任何图中奇点的个数为偶数.
2? ? ? d (vi ) ?
i ?1 p vk ?{ 所有奇点 }

? d (v ) ? ? d (v )
k v j ?{ 所有偶点 } j

由于所有偶数点的度数之和必然为偶数,所以所有奇点 度数之和为偶数,而每个奇点的度数为奇数,所以奇点 的个数必然为偶数。

我们今后只讨论有限简单图: (1) 顶点个数是有限的;

(2) 任意一条边有且只有两个不同的点与它相互关联;
(3) 若是无向图,则任意两个顶点最多只有一条边与 之相联结; (4) 若是有向图,则任意两个顶点最多只有两条边与 之相联结。当两个顶点有两条边与之相联结时,这两条 边的方向相反。 如果某个有限图不满足(2)(3)(4),可在某条边上增设 顶点使之满足。

定理2 连通有向图G含有欧拉回路的充分必要条件 是G中每个结点的入度等于出度;连通有向图G含有 欧拉通路的充分必要条件是除两个结点外,其余每个 结点的入度等于出度,这两个结点中一个结点的入度 比其出度多1,另一个结点的入度比其出度少1。

3) 赋权图与子图
定义 若图 G ? (V (G), E (G)) 的每一条边e 都赋以 一个实数w(e),称w(e)为边e的权,G 连同边上的权 称为赋权图. 定义 设 G ? (V , E ) 和 G? ? (V ?, E?) 是两个图. ① 若 V ? ? V , E ? ? E, 称 G ?是G 的一个子图,记G? ? G. E? ? E ,则称 G?是G 的生成子图. ② 若 V ? ? V, ③ 若 V? ?V ,且 V ? ? ? ,以V ? 为顶点集,以两端点 均在 V ?中的边的全体为边集的图G 的子图,称 为G 的由 V ?导出的子图,记为 G[V ?] . ④若 E? ? E,且 E ? ? ? ,以E ? 为边集,以 E ? 的端点 集为顶点集的图 G的子图,称为 G 的由 E ?导出的 边导出的子图,记为 G[ E ?] .

G[{v1, v2 , v3}]

G[{e3 , e4 , e5 , e6}]

3) 若 V ? ? V ,且 V ? ? ? ,以 V ? 为顶点集,以两端点 均在 V ?中的边的全体为边集的图 G的子图,称 为 G 的由 V ?导出的子图,记为 G[V ?]. 4) 若E? ? E ,且E ? ? ? ,以E ? 为边集,以E ? 的端点 集为顶点集的图 G 的子图,称为 G 的由 E ? 导出的 边导出的子图,记为 G[ E ?] .

4) 图的矩阵表示
邻接矩阵: (以下均假设图为简单图).
1) 对无向图 G,其邻接矩阵 A ? (aij )? ?? ,其中:

? ?1, 若vi与v j 相邻, aij ? ? ? ? 0, 若vi与v j不相邻. v1 v2 v3 v4 v5
?0 ?1 ? A ? ?1 ?0 ? ? ?0 1 0 1 0 0 1 1 0 1 1 0 0? v1 0 0? v2 ? 1 1? v3 0 0? v4 ? 0 0? ? v5

2) 对有向图 G ? (V , E ) ,其邻接矩阵 A ? (aij )? ?? ,其中:
? ?1, 若(vi , v j ) ? E , aij ? ? ? ? 0, 若(vi , v j ) ? E .

u1 u2 u3 u4 ?0 ?0 A?? ?0 ?0 ? 1 1 1? u1 0 0 0 ? u2 ? 1 0 0? u3 0 1 0? ? u4

2) 对有向图 G ? (V , E ) ,其邻接矩阵 A ? (aij )? ?? ,其中:
? ?1, 若(vi , v j ) ? E , aij ? ? ? ? 0, 若(vi , v j ) ? E .

?0 ? ?0 A?? 1 ? ?1 ?

1 0 0 0

0 1 0 1

1? ? 0? ? 1 ? ? 0?

3) 对有向赋权图 G ? (V , E ) , 其邻接矩阵 A ? (aij )? ?? , 其中:
? wij , 若(vi , v j ) ? E , 且wij为其权, ? aij ? ? 0, i ? j, ? ?, 若(vi , v j ) ? E . ?

u1 u2 u3 u4 ? 0 3 7 8 ? u1 ?? 0 ? ? ? u 2 ? ? A? ?? 6 0 ? ? u3 ?? ? 4 0 ? u ? ? 4

3) 对有向赋权图 G ? (V , E ) , 其邻接矩阵 A ? (aij )? ?? , 其中:
? wij , 若(vi , v j ) ? E , 且wij为其权, ? aij ? ? 0, i ? j, ? ?, 若(vi , v j ) ? E . ?

?0 6 ? 8? ? ? ?? 0 7 ?? A?? 3 ? 0 2? ? ? ?4 ? 5 0? ? ?
对于无向赋权图的邻接矩阵可类似定义.

关联矩阵
1) 对无向图 G ? (V , E ) ,其关联矩阵 M ? (mij )? ?? , 其中: ? ?1, 若vi与e j 相 关联 , mij ? ? ? ?0, 若vi与e j不相 关联 .
e1 e2 ? ? ? M ?? ? ? ? ? 1 1 1 0 0 1 0 0 0 0 e3 e4 0 1 1 0 0 e5 0 0? v1 0 0? v2 ? 1 1? v3 1 0? v4 ? 0 1? ? v5

1) 对无向图 G ? (V , E ) ,其关联矩阵 M ? (mij )? ?? , 其中: ? ?1, 若vi与e j 相 关联 , mij ? ? ? ?0, 若vi与e j不相 关联 .

?1 ? ?1 A?? 0 ? ?0 ?

1 0 1 0

1 0 0 1

0 1 1 0

0 1 0 1

0? ? 0? 1? ? 1? ?

无向图的关联矩阵每列的元素中有且仅有两个1.

2) 对有向图 G ? (V , E ) ,其关联矩阵 M ? (mij )? ?? , 其中: ? 1, 若vi 是e j的尾, ? mij ? ? ?1, 若vi 是e j的 头, ? ? 0, 若vi不是e j的头 与尾. e1 e2 e3 e4 e5

? 1 0 1 1 0 ? u1 ?? 1 ? 1 0 0 0 ? u ? 2 M ?? ? 0 1 ? 1 0 ? 1? u3 ? 0 0 0 ?1 1 ? u ? ? 4

2) 对有向图 G ? (V , E ) ,其关联矩阵 M ? (mij )? ?? , 其中: ? 1, 若vi 是e j的尾, ? mij ? ? ?1, 若vi 是e j的 头, ? ? 0, 若vi不是e j的头 与尾.

?1 ? ? ?1 A?? 0 ? ?0 ?

0 1 ?1 0

0 0 1 ?1

?1 0 0 1

?1 0 1 0

0 0 ?1 1

1? ? 0? 0? ? ? 1? ?

有向图的关联矩阵每列元素中有且仅有一个1,有且仅有一个 - 1.

5) 路和连通
定义1) 无向图G的一条途径(或通道或链)是指 一个有限非空序列 W ? v0e1v1e2 ?ek vk,它的项交替 地为顶点和边,使得对 1 ? i ? k,ei 的端点是vi ?1和 vi, 称W是从v0到 vk 的一条途径,或一条 (v0 , vk )途径. 整 数k称为W的长. 顶点 v0 和 vk 分别称为的起点和终点 , 而 v1, v2 ,?, vk ?1称为W的内部顶点.

2) 若途径W的边互不相同但顶点可重复,则称W 为迹或简单链.
3) 若途径W的顶点和边均互不相同,则称W为路 或路径. 一条起点为 v0 ,终点为 vk的路称为 (v0 , vk ) 路 记为P(v0 , vk ).

定义
1) 途径 W ? v0e1v1...ek vk中由相继项构成子序列 vi ei ?1vi ?1...e j v j称为途径W的节. 2) 起点与终点重合的途径称为闭途径. 3) 起点与终点重合的的路称为圈(或回路),长 为k的圈称为k阶圈,记为Ck. 4) 若在图G中存在(u,v)路,则称顶点u和v在图G 中连通. 5) 若在图G中顶点u和v是连通的,则顶点u和v之 之间的距离d(u,v)是指图G中最短(u,v)路的长;若没 没有路连接u和v,则定义为无穷大.

6) 图G中任意两点皆连通的图称为连通图.
7) 对于有向图G,若 W ? v0e1v1e2 ?ek vk ,且 ei 有 头 vi 和尾 vi ?1,则称W为有向途径. 类似地,可定义有向迹,有向路和有向圈. 例 在右图中: 途径或链: ugyexeyfxcw
vbwcxdvaug y 迹或简单链:

uavdxcw 路或路径:
圈或回路:uavbwcxfygu

用图论思想求解以下各题
例 、一摆渡人欲将一只狼,一头羊,一篮菜从河西 渡过河到河东,由于船小,一次只能带一物过河,并 且,狼与羊,羊与菜不能独处,给出渡河方法。

例 、一摆渡人欲将一只狼,一头羊,一篮菜从河西 渡过河到河东,由于船小,一次只能带一物过河,并 且,狼与羊,羊与菜不能独处,给出渡河方法。

解:用四维0-1向量表示(人,狼,羊,菜)的在西岸 状态,(在西岸则分量取1,否则取0)
共24 = 16种状态, 由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1) 是不允许的, 从而对应状态(1,0,0,1),(1,1,0,0),(1,0,0,0) 也是不允许的,

人在河西: (1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1) (1,0,1,0)

人在河东: (0,1,0,1) (0,1,0,0) (0,0,1,0) (0,0,0,1) (0,0,0,0) 以十个向量作为顶点,将可能互相转移的状态连线, 则得10个顶点的偶图。 将10个顶点分别记为A1, A2, …, A10 ,则渡河问题化为 问题:如何从状态(1,1,1,1)转移到(0,0,0,0)? 在该图中求一条从A1到A10的路. 方法:从( 1,1,1,1)开始,沿关联边到达没有到达 从图中易得到两条路: 的相邻顶点,到( )终止,得到有向图即是。 A10,0,0,0 A6 A3 A 7 A2 A8 A5 A10; A1 A6 A3 A9 A4 A8 A5 A10.

3.最短路问题及算法
最短路问题是图论应用的基本问题,很多实际 问题,如线路的布设、运输安排、运输网络最小费
用流等问题,都可通过建立最短路问题模型来求解。 ①最短路的定义 ②最短路问题的两种方法:Dijkstra 和Floyd算法 .

a) 求赋权图中从给定点到其余顶点的最短路.
b) 求赋权图中任意两点间的最短路.

结构程序设计之父

第七位图 灵 奖 (1972年 ) 获 得 者 。

E. W. Dijkstra 1930年5月11日出身于the Netherlands(荷兰)Rotterdam. 去世于2002年8月6日于 Nuenen, the Netherlands. 年轻时代,Dijkstra在University of Leiden, the Netherlands. Leiden大学是荷兰最古老的大学。 学习理论物理,但很快他就意识到其兴趣不 在于理论物理虽然获得了其数学和理论物理 的学位。后来,Dijkstra获得了其博士学位从 University of Amsterdam. 1952年-1962年,E. W. Dijkstra是 Materematisch Centrum, Amsterdam的一 个程序员。 1962年-1984年,作为一个数学教授任职于 Eindhoven Unviersity of Technology. 1984年至1999年,作为计算机系系主任任职与美国UT Austin分校,并于1999年退休。 2002年8月6日在荷兰Nuenen自己的家中与世长辞

Dijkstra 最短路径算法被广泛的应用 在网络协议方面,如OSPF。

Edsger Dijkstra是1950年代ALGOL 语言的一个主 要贡献者。ALGOL高级编程语言已经成为结构清晰, 数学基 础严谨的一个典范。E. W. Dijkstra是现代编 程语言的主要贡献者之一,为我们理解程序语言的 结构,表示方法与实现做出了巨大的贡献。 E. W. Dijkstra 15年的学术著作覆盖了图论的理论工作,教 育手册,解释文章和编程语言领域的哲学思考。

在现代编程语言方面,E. W. Dijkstra也以 他著名的反对(过分)使用GOTO语句的文章 而著名。1968年,E. W. Dijkstra撰写了其 “Go To Statement Considered Harmful” 一文。这篇文章被认为是现代编程语言逐渐不鼓励使 用GOTO 语句,而使用编程控制结构,如while loop 等等的一个分水岭

定义 1) 若H是赋权图G的一个子图,则称H的各
边的权和 w( H ) ?
e?E ( H )

? w(e)为H的权.

类似地,

若P(u,v)是赋权图G中从u到v的路,称 w( P) ? 称为路P的权.

e?E ( P )

? w(e)

2) 在赋权图G中,从顶点u到顶点v的具有最小权 的路P*(u,v),称为u到v的最短路. 3) 把赋权图G中一条路的权称为它的长,把(u,v)

路的最小权称为u和v之间的距离,并记作 d(u,v).

1) 赋权图中从给定点到其余顶点的最短路
如图所示的单行线交通网,每个弧旁边的数字表 示这条单行线的长度。现在一个人要从v1出发,经过 这个交通网到达v8,要寻求是总路程最短的线路。 1 v2 v5

6
v1

2 3 2 v3 2
v4

v9

6 4

10 2

3

6
4

3
v8

1

10

v7

v6

从v1到v8的路线是很多的。比如从v1出发,经过v2,v5 到达v8或者从v1出发,经过v4,v6,v7到达v8等。但不 同的路线,经过的总长度是不同的。例如,按照第一 个线路,总长度是6+1+6=13单位,按照第二个路线, 总长度是1+10+2+4=17单位。

v2 v1 6 1 3

1

v5

2 v3 2
v4

6 4
10

2 6 3 10

v6

v9 3 v8 4 2 v7

一般意义下的最短路问题:
设一个赋权有向图D =(V,A),对于每一个弧 a =(vi ,vj),相应地有一个权wij 。vs ,vt 是 D 中的两 个顶点,P是D中从vs 到vt 的任意一条路,定义路的权 是P 中所有弧的权的和,记作S(p)。 最短路问题就是要在所有从vs 到 vt的路P 中,寻找 一个权最小的路P0,亦即S(P0) = min S(p)。P0叫做从 vs 到 vt 的最短路。P0的权 S(P0)叫做从vs到vt的距离,记 作d(vs,vt)。由于D是有向图,很明显 d(vs,vt)与 d(vt,vs)一般不相等。

Dijkstra算法
下面介绍在一个赋权有向图中寻求最短路的 方法—Dijkstra算法,它是1959年提出来的。目前 公认,在所有的权wij ≥0时,这个算法是寻求最短 路问题最好的算法。并且,这个算法实际上给出 了寻求从一个始定点vs到任意一个点vj的最短路。

寻求从一固定起点 u0 到其余各点的最短路的 最有效算法之一是Dijkstra算法,1959 年由 Dijkstra 提出。这个算法是一种迭代算法 , 它依据的是一个 重要而明显的性质: 最短路是一条路,最短路上 的任一子段也是最短路。 Dijkstra 算法的基本思想是:按距 v0 从近到 远为顺序,依次求得 v0 到图 G 的各顶点的最短路 和距离,直至顶点 v0(或直至图 G 的所有顶点)。

Dijkstra算法的基本思想:
从vs出发,逐步向外寻找最短路。在运算过程中, 与每个点对应,记录一个数,叫做一个点的标号。它 或者表示从vs到该点的最短路权(叫做P 标号),或者 表示从vs到该点最短路权的上界(叫做T 标号)。算法 的每一步是去修改T 标号,把某一个具有T 标号的点改 变为具有P 标号的点,使图D 中具有P 标号的顶点多一 个。这样,至多经过P -1步,就可求出从 vs到各点vj的 最短路。

以例1为例说明这个基本思想。 在例1中,S=1。因为wij ≥0,d(v1,v1)= 0。这时,v1是 具有P标号的点。现在看从v1出发的三条弧(v1,v2),(v1,v3),

(v1,v4)。如果一个人从 v1 出发沿(v1,v2)到达 v2,路程:
d(v1,v1)+ w12= 6单位。

v2
P(v1)

1

v5

6 3

2 3 2 6
v7

2 2
v4 v3

v9

v1

6 4

10

3 4
v8

1

10

v6

如果从v1出发,沿(v1,v3)到达v3,则是d(v1,v1)+w13=3 单位。同理,沿(v1,v4)到达v4,是d(v1,v1)+ w14 = 1单位。 故他从v1出发到达v4的最短路必是(v1,v4),d(v1,v4)= 1。 这是因为从v1到达v4的任一条路,假如是(v1,v4),则必先沿 (v1,v2)到达 v2,或者沿(v1,v3)到达 v3,而这时路程已是6 或者3单位。
P(v1)

v2

1

v5

6 3

2 3 2 6
v7

2 2
v4 v3

v9

v1

6 4

10

3 4
v8

1

10

v6

看从v1出发的三条弧(v1,v2),(v1,v3),(v1,v4), min{d(v1,v1)+w12 ,d(v1,v1)+w13 , d(v1,v1)+w14 } = d(v1,v4)=1。

v2
P(v1)

1

v5

6

2

v1

2

v9

3
1
v4

2

v3

6 4

10 2

3

6
v7

3 4
v8

10

v6

由于所有的权 wij ≥0,因此,不论他如何再从v2或者 v3 到达 v4,所经过的总路程都不会比1少,于是就有 d(v1,v4)=1。这样就使v4变成具有P标号的点。

1 6
v1
P(v1)

2 2 3 2
v3

v9

6 4

10 2

3

6
v7

3 4
v8

1

v4 P(v4)

10

v6

现在看从 v1 和 v4 指向其余点的弧.如上所述,从v1 出发,分别沿(v1,v2),(v1,v3)到达v2,v3,经过的路 程是6或者3单位.从v4出发沿(v4,v6)到达v6,经过的 路程是d(v1,v4)+ w46 =1+10=11单位。 而min{ d(v1,v1)+ w12,d(v1,v1)+ w13, d(v1,v4)+ w46 } = d(v1,v1)+ w13 = 3单位。

1

6
v1
P(v1)

2 2 3 2
v3

v9

6 4

10 2

3

6
v7

3 4
v8

1

v4 P(v4)

10

v6

根据同样的理由,可以断定,从v1到达v3的最短路

是(v1,v3),d(v1,v3)= 3。
这样,又使点v3变为具有P 标号的点,不断重复以 上过程,就可以求出从vs到达任一点vj的最短路。

1 6
v1
P(v1)

2 2 3 2
v3
P(v3)

v9

6 4

10 2

3

6
v7

3 4
v8

1

v4 P(v4)

10

v6

v 6
3 1

P(V2)=5 2?(V2)=3

1 6 4

v5

P(V5)=6 ?(V5)=2

2 3 2 6 v7

2
P(V3)=3 ?(V3)=1

v9

T(V9)=+? ?(V9)=M

10

3
8 v 4 ?(V8)=5
P(V7)=9 ?(V7)=5
P(V8)=12

P(V1)=0

2 v4
P(V4)=1

?(V1)=0

10

v6

?(V4)=1

P(V6)=10 ?(V6)=5

最短路:V1-(V4-)V3-V2-V5-(V6-V7-)V8

算法步骤: 1.给始点 vs 以P标号 P(vs ) ? 0 ,这表示从vs到vs的最短 距离为0,其余节点均给T标号, T (vi ) ? ?? (i ? 2,3,?, n) 2.设节点 vi 为刚得到P标号的点,考虑点vj,其中 (vi , v j ) ? E ,且 vj 为T标号。对vj的T标号进行如下修改

T (v j ) ? min[T (v j ) , P(vi ) ? ?i j ]

3.比较所有具有T标号的节点,把最小者改为P标号, 即:

P(vk ) ? min[ T (vi )]
当存在两个以上最小者时,可同时改为P标号。若全 部节点均为P标号,则停止,否则用vk代替vi,返回步骤 (2)。

求从1到8的最短路径
1
1 2 10 4 5 6 4 2 7

2
5

6 9 5 3 8 4

3

3

7

6

8

X={1}, w1= 0
p1=0 2 1 1 p4=1 0 4 5 6 4 2 7 6 5 9 5 3 8 4 8

1

2

3

3

7

6

min {d12,d14,d16} = min {0+2,0+1,0+3}

= min {2,1,3} = 1

X={1,4}, p4=1

X={1,4}
p1=0 p2=2 2 1 1 p4=1 0 4 5 6 4 2 7 6 5 9 5 3 8 4 8

1

2

3

3

7

6

min {d12,d16,d42,d47} = min {0+2,0+3,1+10,1+2} = min {2,3,11,3} = 2 X={1,2,4}, p2=2

X={1,2,4}
p1=0 p2=2 2 1 1 p4=1 0 4 5 6 p6=3 4 2 7 6 5 9 5 3 8 4 8

1

2

3

3

7

6

min {d13,d23,d25,d47}= min {0+3,2+6,2+5,1+2}

= min {3,8,7,3}=3

X={1,2,4,6}, p6=3

X={1,2,4,6}
p1=0 p2=2 2 1 1 p4=1 0 4 5 6 p6=3 4 2 7 6 5 9 5 3 8 4 8

1

2

3

3

7

6

p7=3

min {d23,d25,d47,d67}= min {2+6,2+5,1+2,3+4}

= min {8,7,3,7}=3

X={1,2,4,6,7}, p7=3

X={1,2,4,6,7}
p1=0 p2=2 2 1 1 p4=1 0 4 5 6 p6=3 4 2 7 6 5 p5=6 5 3 8 4 8 9

1

2

3

3

7

6

p7=3

min {d23,dc25,d75,d78}= min {2+6,2+5,3+3,3+8}

= min {8,7,6,11}= 6

X={1,2,4,5,6,7}, p5=6

X={1,2,4,6,7}
p1=0 p2=2 2 1 1 p4=1 0 4 5 6 p6=3 4 2 7 p3=8 6 5 p5=6 5 3 8 4 8 9

1

2

3

3

7

6

p7=3

min {d23,d53,d58,d78}= min {2+6,6+9,6+4,3+8}
= min {8,15,10,11}= 8 X={1,2,3,4,5,6,7}, p3=8

X={1,2,3,4,6,7}
p1=0 p2=2 2 1 1 p4=1 0 4 5 6 p6=3 4 2 7 p3=8 6 5 p5=6 5 3 8 4 8 9

1

2

3

3

7

6

p7=3

p8=10

min {d38,d58,d78}= min {8+6,6+4,3+7}
= min {14,10,11} = 10 X={1,2,3,4,5,6,7,8}, p8=10

X={1,2,3,4,6,7,8}
p1=0 p2=2 2 1 p4=1 4 5 6 p6=3 4 2 7 10 6 5 p5=6 5 3 8 4 8 9 p3=8

1

2

3

3

7

6

p7=3

p8=10

1到8的最短路径为{1,4,7,5,8},长度为10。

求从V1 到 V8 的最短路线。

V2
3 2 2 7 1

3

V3
3

V5
4

V6
1

6 2 2

V1

V8

V4

V7

V1 ① P=0 ②

V2 T=+∞ P=T=3 ③ ④

V3 T=+∞ T=+∞ T=6 P=T=6 ⑤

V4 T=+∞ T=7 T=7 T=6 P=T= 6

V5 T=+∞ T=+∞ P=T=5

V6 T=+∞ T=+∞ T=+∞ T=8 T=8

V7 T=+∞ T=+∞ T=+∞ T=+∞ T=9

V8 T=+∞ T=+∞ T=+∞ T=+∞ T=12



P=T=8 ⑦

T=10 P=T=9

T=10 T=11

再无其它T 标号,所以 T(V8)=P(V8)=10;

min L(μ)=10



P=T=1 0

由此看到,此方法不仅求出了从V1 到 V8 的最短路长, 同时也求出了从V1 到 任意一点 的最短路长。将从V1 到 任 一点的最短路权标在图上,即可求出从V1 到 任一点的最短 路线。本例中V1 到 V8 的最短路线是: v1 → v2 → v5→ v6 → v8



2 3 1 5 3 1

2

4 4 2 2 2 4 5 6

用Dijkstra算法求下图从v1到v6的最短路。
v2 2 2 4 v4 4 2 2 v6

3
v1 5

1 v3

v5

解 (1)首先给v1以P标号,给其余所有点T标号。
P(v1 ) ? 0

T (vi ) ? ?? (i ? 2 , 3 ,?, 6)

(2) T (v2 ) ? min[T (v2 ), P(v1 ) ? ?12 ] ? min[?? , 0 ? 3] ? 3 T (v3 ) ? min[T (v3 ), P(v1 ) ? ?13 ] ? min[?? , 0 ? 5] ? 5 (3) P(v2 ) ? 3
(4) T (v3 ) ? min[T (v3 ), P(v2 ) ? ?23 ] ? min[5 , 3 ? 1] ? 4 T (v4 ) ? min[T (v4 ), P(v2 ) ? ?24 ] ? min[?? , 3 ? 2] ? 5 T (v5 ) ? min[T (v5 ), P(v2 ) ? ?25 ] ? min[?? , 3 ? 2] ? 5

v2 3 v1 1

2 2 4

v4 4 2 2 v5

v6

5
v3
( 5) ( 6) ( 7) ( 8) ( 9) (10)

P (v 3 ) ? 4

T (v5 ) ? min[T (v5 ), P(v3 ) ? ?35 ] ? min[6 , 4 ? 4] ? 8
P (v4 ) ? 5

P (v 5 ) ? 5

T (v6 ) ? min[T (v6 ), P(v4 ) ? ?46 ] ? min[?? , 5 ? 4] ? 9 T (v6 ) ? min[T (v6 ), P(v5 ) ? ?56 ] ? min[?? , 5 ? 2] ? 7
P (v 6 ) ? 7

反向追踪得v1到v6的最短路为: v1 ? v2 ? v5 ? v6

求下面赋权图中顶点u0到其余顶点的最短路.

Dijkstra 算法:求 G 中从顶点 u0 到其余顶点的最短路。

设 G 为赋权有向图或无向图,G 边上的权均非负. 对每个顶点,定义两个标记( l (v) , z(v ) ) ,其中: l (v) :表从顶点 u0 到 v 的一条路的权.
z(v ) :v 的父亲点,用以确定最短路的路线 算法的过程就是在每一步改进这两个标记,使最终 l (v) 为从顶点 u0 到 v 的最短路的权.

S:具有永久标号的顶点集;输入: G 的带权邻接矩阵 w(u, v)

算法步骤:
(1)赋初值:令 S={ u0 }, l (u0 ) =0 ?v ? S ? V \ S ,令 l (v) = W (u0 , v ) , z(v ) = u0 u ? u0 (2)更新 l (v) 、 z(v ) : ?v ? S ? V \ S ,若 l (v) > l (u) ? W (u, v) 则令 l (v) = l (u) ? W (u, v) , z(v ) = u (3) 设 v * 是使 l (v) 取最小值的 S 中的顶点, 则令 S=S∪{ v * }, u ? v*

(4) 若 S ? φ,转 2,否则,停止.
用上述算法求出的 l (v) 就是 u0 到 v 的最短路的权, 从v的 父亲标记 z (v) 追溯到 u0 , 就得到 u0 到 v 的最短路的路线.

求所示的图 G 中 v1 到其余各顶点的最短路 及其距离。

解:(1) 初始标号。i = 0。 S0 = {v1},v1 = u0,参见图 (a)。

(a)

(2) 用 u0 = v1 对各顶点的标号进行更新。i = 1。 S0 = {v2, v3, v4, v5, v6},?v? S0,由算法有: l(v2) = min{?, 0+7} = 7, l(v3) = min{?, 0+4} = 4, l(v4) = min{?, 0+?} = ?, l(v5) = min{?, 0+?} = ?, l(v6) = min{?, 0+2} = 2。 由于 v2,v3,v6 的标号被 v1 更新,故这三个顶点的父 节点为 v1,即 z(v2) = z(v3) = z(v6) = v1,参见图 (b),数字 边方框中的符号表示父节点。 {l (v)} = l(v6) = 2,故u1 = v6,S1 = {v1, v6}。 又由于 min v?S 参见图 (c)。
0

(b)

(c)

(3) 用 u1 = v6 对各顶点的标号进行更新。i = 2。 S1 = {v2, v3, v4, v5},?v? S1 ,由算法有: l(v2) = min{7, 2+?} = 7, l(v3) = min{4, 2+1} = 3, l(v4) = min{?, 2+5} = 7, l(v5) = min{?, 2+5} = 7。

在此次迭代中,v2 的标号不变,v3,v4,v5 的标号被 v6 更新,故 v2 的父节点不变,v3,v4,v5 的父节点为 v6, 即 z(v2) = v1,z(v3) = z(v4) = z(v5) = v6。参见图(d)。 {l (v)} 又由于 min = l(v3) = 3,故 u2 = v3,S2 = {v1, v6, v3}。 v?S 参见图 (e)。
1

(d)

(e)

(4) 用 u2 = v3 对各顶点的标号进行更新。i = 3。 S2 = {v2, v4, v5},?v? S2 ,由算法有: l(v2) = min{7, 3+3} = 6, l(v4) = min{7, 3+1} = 4, l(v5)= min{7, 3+?} = 7。

在此次迭代中,v5 的标号不变,v2 和 v4 的标号 被 v3 更新,故 v5 的父节点不变,v2 和 v4 的父节点 为 v3,即 z(v5) = v6,z(v2) = z(v4) = v3。参见图(f)。 {l (v)} = l(v ) = 4,故 u = v ,S = {v , 又由于 min v?S 4 3 4 3 1 v6, v3, v4}。参见图 (g)。
2

(f)

(g)

(5) 用u3 = v4 对各顶点的标号进行更新。i = 4。 S3 = {v2, v5},?v? S3 ,由算法有:

l(v2) = min{6, 4+?} = 6, l(v5) = min{7, 4+2} = 6。 在此次迭代中,v2 的标号不变,v5 标号被v4 更 新,故 v2 的父节点不变,v5 的父节点为v4,即 z(v2) = v3,z(v5) = v4。参见图 (h)。 {l (v)} = l(v5) = 6,故 u4 = v5,S4 = {v1, 又由于 min v?S v6, v3, v4, v5}。参见图 (i)。
3

(h)

(i)

5。

(6) 用 u4 = v5 对各顶点的标号进行更新。i =
S4 = {v2},?v? S4 = {v2},由算法有:

l(v2) = min{6, 6+?} = 6。 在此次迭代中,v2 的标号不变,故 v2 的父 节点不变,即 z(v2) = v3。参见图 (i)。 {l (v)} = l(v2) = 6,故 u5 = v2,S5 = 又由于 min v?S {v1, v6, v3, v4, v5, v2}。
4

(h)

(i)

(7) 由于 i = 5 = n ? 1,停止。

注:① 迭代的终止条件也可使用 Sn?1 = {v1, …, vn},或者 S n?1 = ?。 ② 若寻找 v1 到某点 v 的最短路的路由,则由 v 开始 追溯父节点直至 v1。 例如,寻找 v1 到 v5 的最短路的路由,根据图 (i),从 v5 开始追溯父节点:v5 的父节点为 v4,v4的父节点为 v3, v3 的父节点为 v6,v6 的父节点为 v1。于是 v1 到 v5 的最短 路为:v1?v6?v3?v4?v5。 再如,v1 到 v2 的最短路为:v1?v6?v3?v2。 ③ 若求 v1 到某点 v 的距离,则直接由 l(v) 的终值确定。 例如,根据图 (i),由于 l(v5) = 6,故 v1 到 v5的距离为 6。再如,由于 l(v2) = 6,故 v1 到 v2 的距离也为 6。



求下图从顶点 u 1 到其余顶点的最短路.

TO MATLAB(road1)

?0 2 1 8 ? ? ? ? 0 ? 6 1 ? ? ? 0 7 ? ? 9 ? 0 5 1 2 ? 先写出带权邻接矩阵: W? 0 3 ? ? ? 0 4 ? 0 ? ? 因 G 是无向图,故 W 是对称矩阵.

?? ?? ?? ? ?? 9? 6? 3? ? 0?

迭代 次数 1 2 3 4 5 6 7 8 最后标记:

l (ui )
u1
0 0

u2 ?
2 2

u3 ?


u4 ?
8 8 8 8 7

u5 ? ? ?
3

u6 ? ? ? ?
6

u7 ? ?
10 10 10 10 9

u8

? ? ? ?
12 12 12 12 12 u5

l (v ) z (v)

0

2

1

u1

u1

u1

7 u6

3 u2

6 u5

9 u4

l (ui )
u1
最后标记:

u2
2

u3
1

u4
7 u6

u5
3 u2

u6
6 u5

u7
9 u4

u8
12 u5

l (v ) z (v)

0

u1

u1

u1

u2

u5
u6

u1

u4

u8

u3

u7

寻求赋权图中各对顶点之间最短路,显然 可以调用 Dijkstra 算法。具体方法是:每次以 不同的顶点作为起点,用 Dijkstra 算法求出从 该起点到其余顶点的最短路径,反复执行次这 样的操作,就可得到每对顶点之间的最短路。 但这样做需要大量重复计算,效率不高。R. W. Floyd(弗洛伊德)另辟蹊径,提出了比这更好 的算法,操作方式与 Dijkstra 算法截然不同。

2) 求赋权图中任意两顶点间的最短路
算法的基本思想
? (I)求距离矩阵的方法.

? (II)求路径矩阵的方法.
? (III)查找最短路路径的方法 ? Floyd算法:求任意两顶点间的最短路.

? 举例说明

算法的基本思想
直接在图的带权邻接矩阵中用插入顶点的方法依次 (1) (2) (? ) 构造出? 个矩阵 D 、 D 、 … 、D ,使最后得到的 矩阵 D(? )成为图的距离矩阵, 同时也求出插入点矩阵以 便得到两点间的最短路径.

(I)求距离矩阵的方法.
设赋权图G 的顶点集为V ? {v1, v2 ,?, v? }.
1) 写出赋权图G 的带权邻接矩阵W , 把它作为距离矩阵的
( 0) 初值,即 D(0) ? (dij )? ?? ? ( wij )? ?? ? W .

2)对 k ? 1,2,?,? ,计算
(k ) ( k ?1) ( k ?1) ( k ?1) (k ) ? min{ dij , dik ? d kj }, D( k ) ? (dij )? ?? , 其中 dij

(k ) 表示从 vi 到 v j 且中间点仅为 v1, v2 ,?, vk 的 k 个点的所有 dij

路径中的最短路的长度。

于是, D

(? )

中间可插入任何顶点的路径中最短路的长度,即 D 求距离矩阵.

(? ) (? ) ? (dij )? ?? 中元素 dij 就是从 vi 到 v j 的路径 (? )

就是所

D(0) = [dij(0)]n?n = A:是带权邻接矩阵,dij(0) 表示从 vi 到 vj 的、中间不插入任何点的路径,即边 vivj 的权值; D(1) = [dij(1)]n?n,其中dij(1) = min{dij(0),di1(0) ? d1j(0)}:dij(1) 表示从 vi 到 vj 的、中间最多只允许 v1 作为插入点的路径中 最短路的长度; D(2) = [dij(2)]n?n,其中 dij(2) = min{dij(1),di2(1) ? d2j(1)}:dij(2) 表示从 vi 到 vj 的、中间最多只允许 v1 和 v2 作为插入点的路 径中最短路的长度; …………

D(n) = [dij(n)]n?n,其中 dij(n) = min{dij(n?1), di, n?1(n?1) ? dn?1, (n?1)}:d (n) 表示从 v 到 v 的、中间最多只允许 v , v , …, v j ij i j 1 2 n?1 作为插入点的路径中最短路的长度,即 vi 和 vj 之间的距离。

(II)求路径矩阵的方法.
在建立距离矩阵的同时可建立路径矩阵R.
(k ) (k ) 设 R( k ) ? (rij 的含义是从 vi 到 v j 的最短 )? ?? ,这里 rij

(k ) 路要经过点号为 rij 的点. ( 0) ( 0) 算法开始于 R(0) ? (rij )? ?? , rij ? j,
(k ) 迭代到第 k 步, rij

( k ?1) ( k ?1) ( k ?1) ? k , 若 d ? d ? d , ? ij ik kj ? ? ( k ?1) , 否则 ? ?rij

即由 D( k ?1) 到 D ( k ) 迭代,若某个元素改变(变小) ,则由 R ( k ?1) 到
R ( k ) 迭代中,相应元素改为 k ,表示到第 k 次迭代,从 vi 到 v j 的最

短路过点 vk 比过原有中间点更短.

在求得 D (? ) 时求得 R (? ) ,可由 R (? ) 来查找任何点对之间 最短路的路径.

(III)查找最短路路径的方法.
(? ) 若 rij 则点 va1 是点 vi 到点 v j 的最短路的中间点. ? a1,

然后用同样的方法再分头查找.若:
(? ) (? ) (? ) ? a2 , ria ? a3,…, ria ? ak . (1) 向点 vi 追朔得: ria
1

2

k

(? ) (? ) (? ) ? b r ? b r (2) 向点 v j 追朔得: ra , ,…, 1 b j 2 b j ? j. j
1 1
m

则由点 vi 到 v j 的最短路的路径为:
vi , vak ,?, va2 , va1 , vb1 , vb2 ,?, vbm , v j .

vi

vak

va3

va2

va1

vb1

vb2

vbm

vj

(IV)Floyd算法:求任意两顶点 间的最短路.
d(i,j):i 到 j 的距离. r(i,j):i 到 j 之间的插入点. 输入: 带权邻接矩阵W ? ( w(i, j ))v?v .
(1) 赋初值: 对所有 i,j, d(i,j)?w(i,j), r(i,j)?j, k?1.
(2) 更新 d(i,j), r(i,j): 对所有 i,j,若 d(i,k)+d(k,j)<d(i,j), 则 d(i,j) ?d(i,k)+d(k,j), r(i,j)?k

(3) 若 k=? ,停止.否则 k ?k+1,转(2).

例 求下图中加权图的任意两点间的距离与路径.

D (0)

? 0 1 ? ? ? 2? ? 1 0 4 ? ? 4? ? ? ?? 4 0 2 ? 1 ? ?? ?, ?? ? 2 0 3 3? ?? ? ? 3 0 5 ? ? ? 2 4 1 3 5 0 ? ? ? ?

R (0)

?1 ?1 ? ?1 ?? ?1 ?1 ? ? ?1

2 3 4 5 6? 2 3 4 5 6? ? 2 3 4 5 6? ?, 2 3 4 5 6? 2 3 4 5 6? ? 2 3 4 5 6? ?

插入点 v1,得:

(k ) dij

?

?0 1 ? ? ?1 0 4 ? ? ?? 4 0 2 (0) D ?? ?? ? 2 0 ?? ? ? 3 ? ? ?2 4 1 3 ( k ?1) ( k ?1) min{ dij , dik

? 2? ? 4? ? ? 1? ?, 3 3? 0 5? ? 5 0? ? ( k ?1) ? d kj },

D (1)

?1 2 3 ? 0 1 ? ? ? 2? ?1 2 3 ? 1 0 4 ? ? 3? ? ? ? ?1 2 3 ?? 4 0 2 ? 1 ? (1) ?? ?, R ? ? ?? ? 2 0 3 3 ? ?1 2 3 ?? ? ? 3 0 5 ? ?1 2 3 ? ? ? 2 3 1 3 5 0 ? ? ? ? ? ?1 1 3

4 5 6? 4 5 1? ? 4 5 6? ?, 4 5 6? 4 5 6? ? 4 5 6? ?

矩阵中带“=”的项为经迭代比较以后有变化的元素.

插入点 v2,得:

(k ) dij

D ( 2)

? 0 1 5 ? ? 2? ? 1 0 4 ? ? 3? ? ? ? 5 4 0 2 ? 1? ?? ?, ?? ? 2 0 3 3 ? ?? ? ? 3 0 5 ? ? ? ? ? 2 3 1 3 5 0? ?

?0 1 ? ? ?1 0 4 ? ? ?? 4 0 2 (1) D ?? ?? ? 2 0 ?? ? ? 3 ? 3 1 3 ? ? 2( k ? 1) ( k ?1) ? min{ dij , dik ?1 2 2 4 ?1 2 3 4 ? ?2 2 3 4 ( 2) R ?? ?1 2 3 4 ?1 2 3 4 ? ? ?1 1 3 4

? 2? ? 3? ? ? 1? ?, 3 3? 0 5? ? 5 0? ??1) (k ? d kj }, 5 6? 5 1? ? 5 6? ?, 5 6? 5 6? ? 5 6? ?

矩阵中带“=”的项为经迭代比较以后有变化的元素.

D ( 2)

? 0 1 5 ? ? 2? ? 1 0 4 ? ? 3? ? ? ? 5 4 0 2 ? 1? ?? ?, ?? ? 2 0 3 3 ? ?? ? ? 3 0 5 ? ? ? ? ? 2 3 1 3 5 0? ?

(k ) ( k ?1) ( k ?1) ( k ?1) 插入点 v3,得:dij ? min{ dij , dik ? d kj },

D ( 3)

? 0 1 5 7 ? 2? ? 1 0 4 6 ? 3? ? ? ? 5 4 0 2 ? 1? ?? ?, ? 7 6 2 0 3 3? ?? ? ? 3 0 5 ? ? ? ? ? 2 3 1 3 5 0? ?

R ( 3)

?1 ?1 ? ?2 ?? ?3 ?1 ? ? ?1

2 2 3 5 6? 2 3 3 5 1? ? 2 3 4 5 6? ?, 3 3 4 5 6? 2 3 4 5 6? ? 1 3 4 5 6? ?

插入点
?0 ?1 ? ?5 ?? ?7 ?10 ? ?2 ?

? 0 1 5 7 ? 2? ? 1 0 4 6 ? 3? ? ? ? 5 4 0 2 ? 1? ( 3) D ?? ?, ? 7 6 2 0 3 3? ?? ? ? 3 0 5 ? ? ? ? ? 2 3 1 3 5 0? ? (k ) ( k ?1) ( k ?1) ( k ?1) v4,得:dij ? min{ dij , dik ? d kj },
2 2 3 4 6? 2 3 3 4 1? ? 2 3 4 4 6? ?, 3 3 4 5 6? 4 4 4 5 6? ? 1 3 4 5 6? ?

D ( 4)

1 5 7 10 2? ?1 ?1 0 4 6 9 3? ? ? 4 0 2 5 1? ?2 ( 4) , ? R ?? 6 2 0 3 3? ?3 9 5 3 0 5? ?4 ? ? 3 1 3 5 0? ? 1

插入点 v5,得: D(5) ? D( 4) , R(5) ? R( 4) ,

? ?

D ( 5)

?0 ?1 ? ?5 ?? ?7 ?10 ? ? ?2

1 5 7 10 2? 0 4 6 9 3? ? 4 0 2 5 1? ?, 6 2 0 3 3? 9 5 3 0 5? ? 3 1 3 5 0? ?

(k ) ( k ?1) ( k ?1) ( k ?1) 插入点 v6,得:dij ? min{ dij , dik ? d kj },

D (6)

?0 ?1 ? ?3 ?? ?5 ?7 ? ? ?2

1 3 5 7 2? 0 4 6 8 3? ? 4 0 2 5 1? ?, 6 2 0 3 3? 8 5 3 0 5? ? 3 1 3 5 0? ?

R (6)

?1 ?1 ? ?6 ?? ?6 ?6 ? ? ?1

2 6 6 6 6? 2 3 3 6 1? ? 2 3 4 4 6? ?. 3 3 4 5 6? 6 4 4 5 6? ? 1 3 4 5 6? ?

D (6)

R (6)

?1 ?1 ? ?6 ?? ?6 ?6 ? ?1 ?

2 6 6 6 6? 2 3 3 6 1? ? 2 3 4 4 6? ?. 3 3 4 5 6? 6 4 4 5 6? ? 1 3 4 5 6? ?

?0 ?1 ? ?3 ?? ?5 ?7 ? ? ?2

1 0 6 8

3 5 7 4 6 8 2 5 3 3 0 3 5 2 0 5

4 0

3 1

2? 3? ? 1? ?, 3? 5? ? 0? ?

( 6) d 52 ? 8 故从v5到v2的最短路为8

( 6) ( 6) r52 ? 6 由v5向v6追溯: r56 ? 6.
( 6) ( 6) 由v6向v2追溯: r62 ? 1, r12 ? 2.

所以从到的最短路径为:v5 ? v6 ? v1 ? v2 .

最 短 路 的 应 用
一、 可化为最短路问题的多阶段 决策问题 二、 选 址 问 题

可化为最短路问题的多阶段决策问题
例1 设备更新问题:企业使用一台设备,每年年初,企业领导就要确定 是购置新的,还是继续使用旧的.若购置新设备,就要支付一定的购置费用; 若继续使用,则需支付一定的维修费用.现要制定一个五年之内的设备更新 计划,使得五年内总的支付费用最少.
已知该种设备在每年年初的价格为: 第一年 第二年 第三年 第四年 第五年 11 11 12 12 13 使用不同时间设备所需维修费为: 使用年限 0- 1 1-2 2-3 3-4 4-5 5 6 8 11 18 维修费

分析:可行的购置方案(更新计划)是很多的, 如: 1) 每年购置一台新的,则对应的费用为: 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年购置新的,一直用到第五年年底,则总 费用为: 11+5+6+8+11+18 = 59 显然不同的方案对应不同的费用。
第i年度 购置费 设备役龄 维修费用 1 11 0-1 5 2 11 1-2 6 3 12 2-3 8 4 12 3-4 11 5 13 4-5 18

这样上述设备更新问题就变为:在有向赋权图
G = (V, E, F )(图解如下)中求v1到v6的最短路问题.

(2)方法:将此问题用一个赋权有向图来描述,然后求 这个赋权有向图的最短路。 求解步骤: 1)画赋权有向图: 设 Vi 表示第i年初,(Vi ,Vj )表示第i 年初购买新设备用 到第j年初(j-1年底),而Wi j 表示相应费用,则5年的 一个更新计划相当于从V1 到V6的一条路。 2)求解 (标号法)

由实际问题可知,设备使用三年后应当更新,因此删除 该图中v1到v5 ,v1到v6 ,v2到v6的连线;又设备使用一年后 就更新则不划算,因此再删除该图中v1v2 ,v2v3 ,v3v4 , v4v5 ,v5v6 五条连线后得到

从上图中容易得到v1到v6只有两条路: v1v3v6 和 v1v4v6.

而这两条路都是v1到v6的最短路.

选址问题--中心问题
例2 某城市要建立一个消防 站,为该市所属的七个 区 服务, 如图所示,问应设在哪 个区,才能使它至最远 区 的路径最短.

(1)用Floyd算法求出距离矩阵 D ? (dij )v?v
( 2)计算在各点v i 设立服务设施的 最大服务距离S (v i )
1? j ? v

S (v i ) ? m ax?d ij ? i ? 1,2,? v
1? i ? v

(3)求出顶点v k , 使S (v k ) ? min ?S (v i )?

则vk 就是要求的建立消防站 的地点,此点称为图的 中心点

? 0 ? ? 3 ? 5 ? D ? ? 10 ? 7 ? ? 5 .5 ? ? 7

3 0 2 7 4 2 .5 4

5 2 0 5 2 4.5 6

10 7 5 0 3 7 8.5

7 4 2 3 0 4 5 .5

7 ? ? 2 .5 4 ? 4 .5 6 ? ? 7 8 .5 ? 4 5.5 ? ? 0 1.5 ? ? 1. 5 0 ? 5. 5

S(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5

S(v3)=6,故应将消防站设在v3处。

选址问题--重心问题
例 3 某矿区有七个矿点,如图所示.已知各矿点每天的产矿 量 q(v j )(标在图的各顶点上) . 现要从这七个矿点选一个来建造矿 厂.问应选在哪个矿点,才能使各矿点所产的矿运到选矿厂所在地 的总运力(千吨公里)最小.

(1)求距离阵 D= (d ij )? ?? .
(2) 计算各顶点作为选矿厂的总运力 m(vi )

m(vi ) ? ? q(v j ) ? d ij
j ?1
1?i ??

?

i ? 1,2,??

(3)求 vk 使 m(v k ) ? min{m(vi )} ,则 vk 就是选矿厂应设之 矿点.此点称为图 G 的重心或中位点.

最小生成树及算法
1) 树的定义与树的特征 定义 连通且不含圈的无向图称为树.常用T表示. 树中的边称为树枝. 树中度为1的顶点称为树叶. 孤立顶点称为平凡树.

v1
v2

v3

v4

v5

平凡树

定理2 设G是具有n个顶点的图,则下述命题等价:
1) G是树( G无圈且连通); ? 2) G无圈,且有n-1条边; 3) G连通,且有n-1条边; 4) G无圈,但添加任一条新边恰好产生一个圈; 5) G连通,且删去一条边就不连通了(即G为 最小连通图); 6) G中任意两顶点间有唯一一条路.

2)图的生成树
定义 若T是包含图G的全部顶点的子图,它又是树, 则称T是G的生成树. 图G中不在生成树的边叫做弦.

定理3 图G=(V,E)有生成树的充要条件是图G是连 通的.

(II)找图中生成树的方法
可分为两种:避圈法和破圈法 A 避圈法 : 深探法和广探法 B 破圈法

A 避圈法
定理3的充分性的证明提供了一种构造图的生 成树的方法. 这种方法就是在已给的图G中,每步选出一条 边使它与已选边不构成圈,直到选够n-1条边为止. 这种方法可称为“避圈法”或“加边法”

在避圈法中,按照边的选法不同,找图中生成 树的方法可分为两种:深探法和广探法.

a) 深探法 例用深探法求出下图10的一棵生成树 步骤如下: i) 在点集V中任取一点u, 给以标号0.
ii) 若某点v已得标号,检 图10 1 2 查一端点为v的各边,另一 8 7 端是否均已标号. 10 11 0 3 若有边vw之w未标号,则给 9 13 12 6 w以标号i+1,记下边vw.令 5 4 w代v,重复ii). 若这样的边的另一端均已有标号,就退到标号为 i-1的r点,以r代v,重复ii),直到全部点得到标号为止.

a) 深探法 例用深探法求出下图10的一棵生成树 步骤如下: i) 在点集V中任取一点u, 给u以标号0. ii) 若某点v已得标号,检 图10 查一端点为v的各边,另一 1 2 8 7 端是否均已标号. 10 11 3 若有边vw之w未标号,则给 0 9 13 12 w以标号i+1,记下边vw.令 6 5 4 w代v,重复ii). 若这样的边的另一端均已有标号,就退到标号为 i-1的r点,以r代v,重复ii),直到全部点得到标号为止.

b)广探法 例用广探法求出下图10的一棵生成树 步骤如下: i) 在点集V中任取一点u, 给u以标号0. ii) 令所有标号i的点集为 Vi,检查[Vi,V\Vi]中的边端点 是否均已标号. 对所有未标 号之点均标以i+1,记下这些 边. iii) 对标号i+1的点重复步 步骤ii),直到全部点得到 标号为止.
1 1

图10
0 1 2 2 3 3 4 3 2 2 2 1

图10

b)广探法 例用广探法求出下图10的一棵生成树 步骤如下: i) 在点集V中任取一点u, 给u以标号0. ii) 令所有标号i的点集为 Vi ,检查[Vi,V\Vi]中的边端点 是否均已标号. 对所有未标 号之点均标以i+1,记下这些 边. iii) 对标号i+1的点重复步 步骤ii),直到全部点得到 标号为止.
1 1

图10
0 1 2 2 3 3 4 3 2 2 2 1

显然图10的生成树 不唯一.

B 破圈法
相对于避圈法,还有一种求生成树的方法叫做 “破圈法”. 这种方法就是在图G中任取一个圈, 任意舍弃一条边,将这个圈破掉,重复这个步骤 直到图G中没有圈为止. 例 用破圈法求出 下图的一棵生成树.
取一圈{v1e1v2e3v3e2v1},去掉 e3 ; 取一圈{v1e1v2e4v4e5v3e2v1},去掉 e5 ; 取一圈{v2e4v4e7v5e6v2},去掉 e7 ; 取一圈{v1e1v2e6v5e8v3e2v1},去掉 e6 .

B 破圈法
例 用破圈法求出下图的另一棵生成树.
取一圈{v1e1v2e3v3e2v1}, 去掉 e3 ; 取一圈{v1e1v2e4v4e5v3e2v1},去掉 e4 ; 取一圈{v1e1v2e6v5e8v3e2v1},去掉 e8 ;
取一圈{v1e1v2e6v5e7v4e5v3e2v1}去掉 e6 ; 得到另一颗生成树.

不难发现,图 的生成树不是 唯一的 .

3) 最小生成树与算法
定义 13 设T ? (V , E1) 是赋权图G ? (V , E ) 的一棵生 成树, 称T 中全部边上的权数之和为生成树的权, 记为
w(T ) ,即 w(T ) ?
e?E1 *

? w(e) .

如果生成树T 的权 w(T * ) 是 G 的所有生成树的权中最 小者,则称 T * 是 G 的最小生成树,简称为最小树,即
w(T * ) ? ? min{w(T )},式中取遍 G 的所有生成树T .
T

介绍最小树的两种算法: Kruskal算法(或避圈法)和破圈法.

A Kruskal算法(或避圈法)
步骤如下: 1) 选择边e1,使得w(e1)尽可能小; 2) 若已选定边 e1, e2 ,..., ei ,则从 E \ {e1, e2 ,..., ei } 中选取ei ?1 ,使得: i) G[{e1, e2 ,..., ei ?1}] 为无圈图,
ii) w(ei ?1 ) 是满足i)的尽可能小的权, 3) 当第2)步不能继续执行时,则停止. 定理4 由Kruskal算法构作的任何生成树 T * ? G[{e1, e2 ,..., e? ?1}] 都是最小树.

例10用Kruskal算法求下图的最小树.
在左图中 {e1, e2 ,..., e8}权值 最小的边有e1, e5 , 任取一条 e1 , 在 {e2 , e3 ,..., e8} 中选取权值 最小的边 e5 , {e2 , e3 , e4 , e6 , e7 , e8} 中权值最小边有 e3 , e7 , 从中选 任取一条边 e3 ; {e2 , e4 , e6 , e7 , e8} 中选取在中选取e7 , 在{e2 , e4 , e6 , e8} 中选取 e4 , e8.但 e4与 e8 都 会与已选边构成圈,故停止,得

B破圈法

例11用破圈法求下图的最小树.

算法2 步骤如下: 1) 从图G中任选一棵树T1. 2) 加上一条弦e1,T1+e1中 立即生成一个圈. 去掉此 圈中最大权边,得到新 树T2,以T2代T1,重复2)再 检查剩余的弦,直到全 部弦检查完毕为止. 再加上弦 先求出上图的一棵生成树 e7,得到圈 v4v5v2v4, . 加以弦 e2,得到的圈 v1v3v2v1, 去掉最大的权边 e6,得到一棵 新树;如此重复进行,直到全 去掉最大的权边 e2,得到一棵新 树仍是原来的树; 全部的弦均已试过,得最小树.

e2

e7 2

行遍性问题
一、中 国 邮 递 员 问 题
(一) 欧 拉 图

(二) 中 国 邮 递 员 问 题

二、推 销 员 问 题
(一) 哈 密 尔 顿 图
(二) 推 销 员 问 题

三、建模案例:最佳灾情巡视路线

欧 拉 图
定义1 设 G=(V,E)是连通无向图 (1)经过 G 的每边至少一次的闭通路称为巡回. (2)经过 G 的每边正好一次的巡回称为欧拉巡回. (3)存在欧拉巡回的图称为欧拉图. (4)经过 G 的每边正好一次的道路称为欧拉道路. e1 v1 e1 v2 v1 v2

e4 v4 e3

e5

e2 v3

v4

e4 e e5 6 e3

e2

v3

欧拉道路:v1e1v2e2v3e5v1e4v4e3v3 欧拉巡回: 巡回:v e v e v e v e v e v e v v1e1v2e2v3e5v1e4v4e3v3e6v1
1 1 2 2 3 5 1 4 4 3 3 5 1

定理1 对于非空连通图 G,下列命题等价: (1)G 是欧拉图. (2)G 无奇次顶点. (3)G 的边集能划分为圈.

v1 e4 v4

e1

v2 e5 e2 v3

v1 e4 v4

e1 e5 e3

v2 e2 v3

e6 e3

欧拉图

非欧拉图

推论1 设 G 是非平凡连通图,则 G 有欧拉道路的充要 条件是 G 最多只有两个奇次顶点.

中国邮递员问题-定义
邮递员发送邮件时,要从邮局出发,经过他投递 范围内的每条街道至少一次,然后返回邮局,但邮递 员希望选择一条行程最短的路线.这就是中国邮递员 问题. 若将投递区的街道用边表示,街道的长度用边权 表示,邮局街道交叉口用点表示,则一个投递区构成 一个赋权连通无向图.中国邮递员问题转化为:在一 个非负加权连通图中,寻求一个权最小的巡回.这样 的巡回称为最佳巡回.

中国邮递员问题-算法
1、G 是欧拉图
此时 G 的任何一个欧拉巡回便是最佳巡回.问题 归结为在欧拉图中确定一个欧拉巡回.
Fleury 算法:求欧拉图的欧拉巡回

Fleury算法-基本思想:从任一点出发,每当访问 一条边时,先要进行检查.如果可供访问的边不只一条, 则应选一条不是未访问的边集的导出子图的割边作为访 问边,直到没有边可选择为止.

割边的定义:设G连通,e ? E(G),若从G中删除边e后, 图G-{e}不连通,则称边e为图G的割边. v1 e4 v4 e3 v3 e1 e5 v2 e2 e6 V7 e9 割边 V5

e7

e8 V6

G的边e是割边的充要条件是e不含在G的圈中.

Fleury 算法—算法步骤: (1)任选一个顶点 v0,令道路 w0=v0 (2)假定道路 wi=v0e1v1e2…eivi 已经选好,则从 E\{e1,e2, …,ei}中 选一条边 ei+1,使: a)ei+1 与 vi 相关联 b)除非不能选择,否则一定要使 ei+1 不是 Gi=G[E-{e1,e2, …,ei}] 的割边. (3)第(2)步不能进行时就停止.

v1 e4

e1 e5 e3

v2
e2

e10
e7 e6

V5
e8

v4

v3

V7 e9

V6

哈 密 尔 顿 图
定义 设 G=(V,E)是连通无向图 (1) 经过 G 的每个顶点正好一次的路径, 称为 G 的一条哈密尔 顿路径. (2) 经过 G 的每个顶点正好一次的圈, 称为 G 的哈密尔顿圈或 H 圈. (3) 含 H 圈的图称为哈密尔顿图或 H 图.

旅行售货员问题或货郎担问题.
一个旅行售货员想去访问若干城镇,然后回 到出发地.给定各城镇之间的距离后,应怎样计划 他的旅行路线,使他能对每个城镇恰好经过一次 而总距离最小? 它可归结为这样的图论问题:在一个赋权完 全图中,找出一个最小权的H圈,称这种圈为最优圈.

但这个问题是NP-hard问题,即不存在多项式 时间算法.也就是说,对于大型网络(赋权图),目前还 没有一个求解旅行售货员问题的有效算法,因此 只能找一种求出相当好(不一定最优)的解.

定义 在加权图G=(V,E)中, (1)权最小的哈密尔顿圈称为最佳H圈. (2)经过每个顶点至少一次的权最小的闭通路称 为最佳推销员回路. 一般说来,最佳哈密尔顿圈不一定是最佳推销员回路, 同样最佳推销员回路也不一定是最佳哈密尔顿圈.

H回路,长22

最佳推销员回路,长4

定 理 1 在 加 权 图 G=(V,E) 中 , 若 对 任 意 x,y,z ? V,z ? x,z ? y,都有 w(x,y) ? w(x,z)+w(z,y),则图 G 的最佳 H 圈也是最佳推销员回路.
最佳推销员回路问题可转化为最佳 H 圈问题.方法 是由给定的图 G=(V,E)构造一个以 V 为顶点集的完备图 G’=(V,E’),E’的每条边(x,y)的权等于顶点 x 与 y 在图中 最短路的权.即: ? x,y ? E’, w(x,y)=mindG(x,y)

定理2 加权图 G 的最佳推销员回路的权与 G’ 的最佳 H 圈的权相同.

推销员问题近似算法:二边逐次修正法:
(1)任取初始 H 圈: C0=v1,v2,…,vi, ,…,vj,…,vn,v1

(2)对所有的 i ,j,1< i+1 < j < n ,若 w(vi, vj) + w(vi+1,vj+1) < w(vi,vi+1) + w(vj,vj+1) 则在 C0 中删去边(vi,vi+1)和(vj,vj+1)而加入边(vi, vj)和(vi+1,vj+1), 形成 新的 H 圈 C,即 C= v1,v2,…,vi,,vj , vj-1, …,vi+1,vj+1, …,vn,v1

(3)对 C 重复步骤(2) ,直到条件不满足为止,最后得到 的 C 即为所求.

例对下图16的K6,用二边逐次修正法求较优H圈.

较优H圈: C3 ? v1v4v5v6v2v3v1 其权为ω(C3)=192

分析: 找出的这个解的好坏可用最优H圈的权 的下界与其比较而得出.即利用最小生成树可得最 优H圈的一个下界,方法如下: 设C是G的一个最优H圈,则对G的任一顶点v, C-v是G-v的路,也G-v是的生成树.如果T是G-v的 最小生成树,且e1是e2与v关联的边中权最小的两条 边,则w(T)+w(e1)+w(e2)将是w(C)的一个下界. 取v=v3,得G-v3的一 最小生成树(实线),其 权w(T)=122,与v3关联 的权最小的两条边为 v1v3和v2v3,故w(C) ? w(T)+w(v1v3)+w(v2v3) =178.故最优H圈的权 应满足178 ? w(C)? 192.

6. 最佳灾情巡视路线的模型的建立与 求解
1) 98年全国大学生数学建模竞赛B题“最佳灾
情巡视路线”中的前两个问题是这样的:

今年(1998年)夏天某县遭受水灾. 为考察灾情、
组织自救,县领导决定,带领有关部门负责人到 全县各乡(镇)、村巡视. 巡视路线指从县政府 所在地出发,走遍各乡(镇)、村,又回到县政 府所在地的路线.

1)若分三组(路)巡视,试设计总路程最 短且各组尽可能均衡的巡视路线. 2)假定巡视人员在各乡(镇)停留时间T=2 小时,在各村停留时间t=1小时,汽车行驶速度V =35公里/小时. 要在24小时内完成巡视,至少应分 几组;给出这种分组下最佳的巡视路线.

公路边的数字为该路段的公里数.

2) 问题分析:
本题给出了某县的公路网络图,要求的是在不 同的条件下,灾情巡视的最佳分组方案和路线. 将每个乡(镇)或村看作一个图的顶点,各乡 镇、村之间的公路看作此图对应顶点间的边,各条 公路的长度(或行驶时间)看作对应边上的权,所 给公路网就转化为加权网络图,问题就转化图论中 一类称之为旅行售货员问题,即在给定的加权网络 图中寻找从给定点O出发,行遍所有顶点至少一次 再回到点O,使得总权(路程或时间)最小.

本题是旅行售货员问题的延伸-多旅行售货员问题. 本题所求的分组巡视的最佳路线,也就是m条 经过同一点并覆盖所有其他顶点又使边权之和达到 最小的闭链(闭迹). 如第一问是三个旅行售货员问题,第二问是四 个旅行售货员问题. 众所周知,旅行售货员问题属于NP完全问题, 即求解没有多项式时间算法. 显然本问题更应属于NP完全问题. 有鉴于此, 一定要针对问题的实际特点寻找简便方法,想找到 解决此类问题的一般方法是不现实的,对于规模较大 的问题可使用近似算法来求得近似最优解.

问题转化为在 给定的加权网 络图中寻找从 给定点O出发, 行遍所有顶点 至少一次再回 回到点O ,使得 总权(路程或时 时间)最小,即 最佳旅行售货 员问题.

因二边逐次修正法的结果与初始圈有关,故本算法 最佳旅行售货员问题是NP—完全问题,采用一种 第2),3),4)步分别用三种方法产生初始圈,以保 近似算法求其一个近似最优解,来代替最优解 . 证能得到较优的计算结果. 算法一 求加权图的最佳旅行售货员回路近似算法 1):用图论软件包求出G中任意两个顶点间的最短路, 构造出完全图 G? ? (V , E?), ?( x, y ) ? E?, ? ( x, y )

2) 输入图 G ?的一个初始H圈; 3) 用对角线完全算法(见[3])产生一个初始圈; 4) 随机搜索出 G ?中若干个H圈,例如2000个; 5) 对第2),3),4)步所得的每个H圈,用二边逐次 修正法进行优化,得到近似最优H圈; 6) 在第5)步求出的所有H圈中,找出权最小的一个, 此即要找的最优H圈的近似解.

? min dG ( x, y);

问题一 若分为三组巡视,设计总路程最短且各 组尽可能均衡的巡视路线. 此问题是多个售货员的最佳旅行售货员问题. 即在加权图G 中求顶点集V 的划分V1,V2 ,?,Vn ,将G
分成 n 个生成子图 G[V1], G[V2 ],?, G[Vn ],使得 n

i ? 1,2,3,?, n. 2) ?Vi ? V (G) . i ?1 max | ? (Ci ) ? ? (C j ) | i, j ??, 3) 其中Ci 为Vi 的导出 max ? (Ci )
1) 顶点O ?Vi ,
i

子图G[Vi ]中的最佳旅行售货员回路, ? (Ci ) 为 n C 的权,i, j ? 1,2,3,..., n . 4) ? ? (Ci ) ? min
i
i ?1

定义 称? 0 ?

max | ? (Ci ) ? ? (C j ) |
i, j

max ? (Ci )
i

为该分组的实际

均衡度. ? 为最大容许均衡度.

显然 0 ? ? 0 ? 1, 说明分组的均衡性越 ?0 越小, 好. 取定一个? 后,? 0 与? 满足条件 3)的分组是 一个均衡分组. 条件 4)表示总巡视路线最短. 此问题包含两方面:a)对顶点分组, b)在每组中 求(单个售货员)最佳旅行售货员回路. 因单个售货员的最佳旅行售货员回路问题不存 故多 也不 存在多项式时间内的精确算法.

而图中节点数较多,为53个,我们只能去寻求 一种较合理的划分准则,对图1进行粗步划分后,求 出各部分的近似最佳旅行售货员回路的权,再进一

进一步进行调整,使得各部分满足均衡性条件 3).
从O点出发去其它点,要使路程较小应尽量走 O点到该点的最短路. 故用软件包求出O点到其余顶点的最短路. 这些最短路构成一棵O为树根的树. 将从O点出发的树枝称为干枝.

由上述分组准则,我们找到两种分组形式如下: 准则 1 尽量使同一干枝上及其分枝上的点分在同一组. 在分组时应遵从准则: 从O1: 点出发到其它点共有 6条干枝,它们的名称 分组 (⑥,①),(②,③),(⑤,④) 准则2 应将相邻的干枝上的点分在同一组; 分别为①,②,③,④,⑤,⑥ 分组 (①,②),(③,④),(⑤,⑥) . 准则 3 2: 尽量将长的干枝与短的干枝分在同一组 .

分组1极不均衡,故考虑分组2.

分组2:(①,②),(③,④),(⑤,⑥) 对分组2中每组顶点的生成子图,用算法一求出近 似最优解及相应的巡视路线. 在每个子图所构造的完全图中,取一个尽量包含上 图中树上的边的H圈作为其第2)步输入的初始圈.

分组2的近似解
小组 名称 I II III 路 线 总路线 长度 路线的 总长度

O—P—28—27—26—N—24—23—22—17—16—I—15—I —18—K—21—20—25—M—O O—2—5—6—L—19—J—11—G—13—14—H—12—F—10 —F—9—E—7—E— 8—4—D—3—C—O O—R—29—Q—30—32—31—33—35—34—A—B—1—O

191.1 241.9 125.5 558.5

因为该分组的均衡度

? (C1 ) ? ? (C2 ) 241.9 ? 125.5 ?0 ? ? ? 54.2% max ? (Ci ) 241.9
.

i ?1, 2,3

所以此分法的均衡性很差. 为改善均衡性,将第Ⅱ组中的顶点C,2,3,D,4 分给第Ⅲ组(顶点2为这两组的公共点),重新分 分组后的近似最优解见表2.

表2 编号 I II III 路 线

(单位:公里) 路线 路线总 长 度 长度 191.1

O—P—28—27—26—N—24—23—22—17—16—I— 15—I—18—K—21—20—25—M—O O—2—5—6—7—E—8—E—9—F—10—F—12—H —14—13—G—11—J—19—L—6—5—2—O O—R—29—Q—30—32—31—33—35—34—A—1— B—C—3—D—4—D—3—2—O

216.4 192.3

599.8

因该分组的均衡度 ? (C3 ) ? ? (C1 ) 216.4 ? 191.1 ?0 ? ? ? 11.69%. max ? (Ci ) 216.4
i ?1, 2,3

所以这种分法的均衡性较好.

问题二 当巡视人员在各乡(镇)、村的停留
停留时间一定,汽车的行驶速度一定,要在24小时内

完成巡视,至少要分几组及最佳旅行的巡视路线.

?

由于T=2小时,t=1小时,V=35公里/小时,需访问 的乡镇共有17个,村共有35个. 计算出在乡(镇)及 村的总停留时间为17 ?2+35=69小时,要在24小时 内完成巡回,若不考虑行走时间,有: 69/i<24(i为 分的组数). 得i最小为4,故至少要分4组.

由于该网络的乡(镇)、村分布较为均匀,故有可 能找出停留时间尽量均衡的分组,当分4组时各组停 停留时间大约为69/4=17.25小时,则每组分配在路 路途上的时间大约为24-17.25=6.75小时.而前面讨 论过,分三组时有个总路程599.8公里的巡视路线, 分4组时的总路程不会比599.8公里大太多,不妨以 599.8公里来计算.路上约用599.8/35=17小时,若平 均分配给4个组,每个组约需17/4=4.25小时<6.75小 小时,故分成4组是可能办到的.

现在尝试将顶点分为4组.分组的原则:除遵从 前面准则1、2、3外,还应遵从以下准则: 准则4 尽量使各组的停留时间相等. 用上述原则在下图上将图分为4组,同时计算 各组的停留时间,然后用算法一算出各组的近似最 最佳旅行售货员巡回,得出路线长度及行走时间, 从而得出完成巡视的近似最佳时间. 用算法一计 计算时,初始圈的输入与分三组时同样处理.

这4组的近似最优解见表3.

表3 组名 I II III IV 路 线

(路程单位:公里;时间单位:小时) 路 线 总长度 195.8 199.2 159.1 166 停留 时间 17 16 18 18 行走 时间 5.59 5.69 4.54 4.74 完成巡视 的总时间 22.59 21.69 22.54 22.74

O—2—5—6—7—E—8—E—11—G—12—H—12 —F—10—F—9—E—7—6—5—2—O O— R —29—Q—30—Q—28—27—26—N—24—23 —22—17—16—17— K —22—23—N—26—P—O O—M—25—20—21—K—18—I—15—14—13—J —19—L— 6—M—O O—R—A—33—31—32—35—34—B—1—C—3 — D—4—D—3—2 —O

表3 组名 I II III IV 路 线

(路程单位:公里;时间单位:小时) 路 线 总长度 195.8 199.2 159.1 166 停留 时间 17 16 18 18 行走 时间 5.59 5.69 4.54 4.74 完成巡视 的总时间 22.59 21.69 22.54 22.74

O—2—5—6—7—E—8—E—11—G—12—H—12 —F—10—F—9—E—7—6—5—2—O O— R —29—Q—30—Q—28—27—26—N—24—23 —22—17—16—17— K —22—23—N—26—P—O O—M—25—20—21—K—18—I—15—14—13—J —19—L— 6—M—O O—R—A—33—31—32—35—34—B—1—C—3 — D—4—D—3—2 —O

表3符号说明:加有底纹的表示前面经过并停留过 , 此次只经过不停留;加框的表示此点只经过不停留. 22.74 ? 21.69 ? 4.62% 该分组实际均衡度 ? 0 ? 22.74 可看出,表3分组的均衡度很好,且完全满足24 小时完成巡视的要求.

2004年 A题

奥运会临时超市网点设计

一、关于人流量的分布:

“最短路径原则”与“观众分流原则”
简单的人流量分布应指的是各商区的人流量占 总人流量的百分比。只要遵循“最短路径原则”和选

定的某个“分流原则”便可完全计算出人流量的分布。
对于每个商区的人流量而言,还有一个人流量 的人群结构问题,因为不同结构的人群其消费水平是

有较大差异的,这将会影响与人流量对应的消费水平
的计算。解决此问题的关键是“分流原则”的更细化、

更具体化。比如每个商区都按各终点的观众结构进行
分流。

二、模型框架:
1、首先要根据问题的特征,确定模型的类型。 设计方案的内容 设计方案满足的 三个基本要求 难点: 用决策变量表示的目标函数和约束条件 整数规划模型

2、从分析三个基本要求入手,确定目标函数和约束条 件。 硬约束: 软约束: 满足购物需求 分布基本均衡 商业上赢利

可以考虑以分布基本均衡和商业上赢利这两个要求为目标, 以满足购物需求为约束来建立一个双目标规划模型。 或者以商业上赢利这一要求为目标,以满足购物需求和分 布基本均衡为约束条件来建立单目标规划模型。

三、建立模型:
1、根据人流量刻画各商区的购物需求
以 d 表示档次时, 以 M 表示该档次对应的平均消费水平。 设 M ? f (d ) 。由于 0 ? 100(元)为第一档,定义 d ? 1,2?5时,
M = f (1) =50 , f (2) ? 150, f (3) ? 250, f (4) ? 350, f (5) ? 450 。

故可用 M ? f (d ) ? 100 d ? 50 来刻画消费档次与平均消费水平 的关系。在此关系中, d ? [1 , 5]。

观众购物强度指数(平均消费档次):

r?

i ? Ni ? i ?1 Ni ? i ?1
6

6

观众的购物强度: W ? f (r ) ? 100 r ? 50
根据调查资料统计数据可计算出全体观众的平均购 物强度指数 r0 ? 2.5148;观众的平均购物强度(平均消费 水平)为W0 ? f (r0 ) ? 100r0 ? 50 ? 201.48 (元) 。再结合各 商区的人流量,可以简单地计算出各商区的购物需求。

2、确定目标函数的含义与约束条件的含义,并用数学 语言描述之,于是得到规划模型。 ⑴目标函数

? 20 ? F ? min ?? ( L ? mi ? T ? ni ? H (i ))? ? i ?1 ?
F ? min ? (mi ? ni )
i ?1 20

⑵约束条件
①各商区商亭满足各商区的需求的约束:

L ? mi ? T ? ni ? H (i) ? 0
②分布基本均衡约束 : a ? mi ? ni ? b ③各商区的大小店数目为正整数的约束:

mi ? N , ni ? N

⑶模型

? 20 ? F ? min ?? ( L ? mi ? T ? ni ? H (i ))? ? i ?1 ?

? L ? mi ? T ? ni ? H (i ) ? 0 ? s.t.?a ? mi ? ni ? b ?m ? N , n ? N ? i i
其中: i ? 1,2?20

四、参赛文章中几个有意义的思考和 处理:
1、与最短路径有关的两个准则
准则1:在到达同一地点的路程相差不多的不同路段中,以节 约时间为目的,选择不经过商业区的路段。 准则2:在到达同一地点的路程相差不多的不同路段中,以观 光旅游为目的,选择走可经过运动会场的(即经过商业区) 的路段。

2、为便于计算人流量,对6个车站的等效处理。
3、有效人流量的概念 4、与观众群体组成结构有关的购物需求
H (i )

H (i, j ) ? Dij ?W j

五、模型评价的着眼点:
1、观众分流原则 2、人流量的计算 3、各商区购物需求量化方法 4、目标函数与约束条件的理解与刻画


赞助商链接