Ling Xueling
网络模型的讨论,本质上属于 图论 范畴用途极其广泛 （ 如,运输系统设计,信息系统设计,项目计划管理等 ）,实用性强,是网络模型的特征之一,其解法的特殊,也是值得关注的地方需要重点掌握：各种网络模型的 算法 。
第八章 网络模型凌晨,凌晨,
Ling Xueling
一,问题及网络图表示
1,什么是最短路问题在网络中 任意 选择某点为起点,求出从此起点到网络中其余各点的最短路径 。 如,Taxi 的调度问题
2,例子
Gorman 建筑公司承担了散布在邻近三个区域内的一些建筑项目,公司总部与这些工地之间经常有人员,设备,材料等的运输往来 。 与运输成本相关的最短路问题,就是很值得考虑的重要问题设公司总部与六个工地间的公路网络如下页所示：
( 单位,km )。
第一节 最短路问题凌晨,凌晨,
Ling Xueling
一,问题及网络图表示第一节 最短路问题凌晨,凌晨,
1
2
3
4
5
6
7
总部
15
3
10
17
6
2
4
6 5
4
n od e
a r c
Ling Xueling
二,最 短 路 算 法 － － 介 绍 Dijkstra 算法
(Dijkstra 于 1959 年提出,又称加标号法
labeling procedure )
1,结点之标号 (给出：累计路程,路径两个指标 )
第一节 最短路问题凌晨,凌晨,
2 0,4
结点表示从起始结点到本结点的距离是 2 0
表示从起始结点到本结点的最短路径上前一个结点是 4
Ling Xueling
二,最短路算法 （ Dijkstra算法 ）
2,结点标号的分类
1） 有 /无标号结点有 标号结点－－已指定从起始结点到此结点的一条路径无 标号结点－－未指定从起始结点到此结点的路径
2） 永久 /临时标号有 永久 标号结点－－已求出从起始点到此结点的最短路径有 临时 标号结点－－未求出从起始点到此结点的最短路径 。
第一节 最短路问题凌晨,凌晨,
Ling Xueling
二,最短路算法 （ Dijkstra算法 ）
3,例子的解
1 ) 定起始点,写上永久标号 [0,S]－－ 如,结点内涂黑表示已有永久标号
2 ) ( 迭代 ) 反复以下步骤：
(1) 为起始点能直达的结点写上临时标号
(2) 比较临时标号内第一个数,选择小的一个
(3) 小者写成永久标号 ( 圈内涂黑 )
(4) 有 最新永久标号 的结点视为 新的起始点 。
第一节 最短路问题凌晨,凌晨,
Ling Xueling
二,最短路算法 （ Dijkstra算法 ）
4,求出最短路
1－ 3－ 2 1－ 3 1－ 3－ 5－ 4 1－ 3－ 5
1－ 3－ 5－ 6 1－ 3－ 5－ 6－ 7
5,第二个例子在如下页的网络中,求结点 1 和结点 10 之间的最短路径解答,1－－ 3－－ 5－－ 8－－ 10
total = 19。
第一节 最短路问题凌晨,凌晨,
Ling Xueling
二,最短路算法 （ Dijkstra算法 ）
第一节 最短路问题凌晨,凌晨,
1
2
3
4 5
6
7
8
9
10
2
5
1
12
14
6
10
4
13
12
11
3
9
6
5
8
10
5
2
Ling Xueling
三,说明
1,算法中,起始结点可以任意选定,N 个结点问题,
一般需要有 N－ 1 次迭代
2,,MS”软件包只要先输入网络,可以解决此类问题
3,其它用处：最小旅行时间问题,旅行成本问题,管道铺设问题,线路安排问题,厂区布局问题,设备更新问题 等等
4,练习的第四题 ―― 设备维护问题说明
5,标号法已发展到可以解决,(时间所限不展开讨论 )
(1) 弧值为负数；
(2) 有向网络 ( 如：单行道运输问题 )。
第一节 最短路问题凌晨,凌晨,
Ling Xueling
一,概念
1,树－－不含圈的 联通 图
2,什么是 （ 网络 ） 最小支撑树
1) 贯通网络所有结点 ―― 支撑
2) 分枝 (弧 ) 总长度最小 ―― 最小
3,用处：分子结构问题,电网络分析问题,计算机网络设立问题,管道铺设问题等等的解决 。
第二节 最小支撑树问题凌晨,凌晨,
Ling Xueling
二,实例计算机中心欲使五家新用户与中心联机电话公司负责排线,由于价格昂贵,要寻求最小支撑树由于计算机网络的可联通性能,得到：
第二节 最小支撑树问题凌晨,凌晨,
中心
1
2
3
4
5
6
20
40
50
40
30
40
10
30
30
20
40
Ling Xueling
三,算法一 ( Greedy algorithm )
1,因为问题很特殊,就有：若每一步追求最优,最后也能得到问题的最优的解法－－贪心解法
2,作法
1) 对弧的长短按照升序排序
2)任意 结点开始,在保证 不构成圈 的前提下
3) 重复进行：将 最近 的不联通结点并入网络的联通段 （ 可以双线表示联通 ）
3,说明：最小支撑树 不唯一,但分枝总长度唯一
4,例子的计算－－略 。 o.f.=110。
第二节 最小支撑树问题凌晨,凌晨,
Ling Xueling
三,算法一 ( Greedy algorithm )
第二个例子 （ 总长度＝ 28）
第二节 最小支撑树问题凌晨,凌晨,
1
2
3
4
5
6
7
8
9
10
11
3
3
2
4
2
4
4
42
3
3
4
5
3
2
3
4
7
6
5
4
4
Ling Xueling
四,算法二 （ Prim’s algorithm）
1,算法一的缺点,（ 1） 需要先排序 （ 2） 每一步都需要仔细确认有没有构成圈 ―― 故,不适合于复杂,大型的网络模型
2,算法二的步骤
1） 任意选择一个起点；
2） 选择与起点 最近的 顶点,将此顶点及其与起点相连接的弧一并加入树；
3） 对已经连接成树的部分,仍然选择与树 最近的 顶点,然后连上；
4） 重复步骤三,直到所有的顶点都连接上 。
第二节 最小支撑树问题凌晨,凌晨,
Ling Xueling
一,概念
1,什么是最大流问题有一个称之为入口点 ( source node ) 结点和一个出口点 ( sink
node ) 结点的网络,在给定时期内进 / 出最大流量是？
2,用处交通网络之流量,计算机网络之信息流量,金融系统中现金流量,物流流量,防洪系统设计,排水系统设计,供水系统等,.........
3,基本假定分枝 ( arc )－－ 有流量限制且讲究方向结点 ( node )－－ 进,出相等 。
第三节 最大流问题凌晨,凌晨,
Ling Xueling
4,例子某国道自北向南方向计划进行大修,运输部门拟以如下网络的公路系统暂时替代之 （ 单位,1000）
问题：此网络能否适应 15000 辆机动车的最大流 /小时？ 每小时最大流量是多少？ 每一条分枝分别有多大流通过？
第三节 最大流问题凌晨,凌晨,
1
2
3
4
5
6
7
s ou r c e
s i n k
北南
5
0
6
0
2
2
3 0
3
0
5
0
3
0
7
0
1
1
8
0
5
0
7
0
5 - - - 7 每小时机动车流量为 5 0 0 0
Ling Xueling
二,最大流算法
1,方法说明
1） 寻找从入口到出口的路径 ( 要保证此路径可以有流量 >0 的 flow 通过 )
2) 将 1) 中 所寻得的路径尽可能多地增加流量
3) 重复第 1) 2) 步骤,其中用到虚构流手段,直至找不到可使 flow > 0 的路径为止 。
第三节 最大流问题凌晨,凌晨,
Ling Xueling
二,最大流算法
2,虚构流 ( fictitious flow ) 方法对如下路径：
若修改成为：
表明,1) 3? 6 分枝上剩余可安排流量为 1000
2) 6? 3 的 6000 单位实际上是所谓的 虚构流
3) 虚构流－－简明地表示 3? 6 方向之流量应下降或,简明地表示若还要增加 3? 6 方向之流量应转到其它分枝上去 。
第三节 最大流问题凌晨,凌晨,
3 6
7 0
单位,1 0 0 0
3 61 6
Ling Xueling
二,最大流算法
3,实例计算可能的五次流量安排如下：
1) 1－－ 3－－ 6－－ 7,pf = 6
2) 1－－ 2－－ 5－－ 7 pf = 3
3) 1－－ 2－－ 3－－ 5－－ 7 pf = 2
4) 1－－ 4－－ 6－－ 7 pf = 1
5) 1－－ 4－－ 6－－ 5－－ 7 pf = 1
此时得到如下网络流量图,（ 见下页 ）
第三节 最大流问题凌晨,凌晨,
Ling Xueling
二,最大流算法
3,实例计算
6) 1－－ 4－－ 6－－ 3－－ 5－－ 7 pf = 1
故,最大流＝ 14,其中的虚构流手段之说明见下页 。
第三节 最大流问题凌晨,凌晨,
1
2
3
4
5
6
7
北南
13
130
5
0 6
3
2
0 3
2
6
2
0
0
7
0
4
1
2
1
63
0
3
2
Ling Xueling
二,最大流算法
4,虚构流说明说明：原始网络中 6－－ 3 之流量＝ 0,此处安排 1000 辆车在 6－－ 3,实际是虚构流,此处对 6－－ 3 做 1000 的安排,
实为将原先在 1) 中允许进入 3－－ 6 分枝的 1000 单位流转入沿 3－－ 5 分枝,则 6－－ 7 可空 1000 单位流可供安排
5,最优解第三节 最大流问题凌晨,凌晨,
1
2
3
4
5
6
7
北南
6
2
3
3
1
7
5
3
7
5
3
1 4,0 0 0
1 4,0 0 0
Ling Xueling
二,最大流算法
6,第二个例子求下列网络之最大流 ( = 33 )
第三节 最大流问题凌晨,凌晨,
1
2
3
4 5
6
7
8
9
10
0
8
0
10
0
5 5
2
2
5
5
6 6
5
5
3
3
4
4
6
6
10
10
3
3
8
0
2
2
10
0
10
0
Ling Xueling
18 世纪,29 岁的欧拉解决了哥尼斯堡七桥问题：
抽象出,图,,
结论,不是欧拉 图,亦非半欧拉图,不论起点和终点在哪里都不可能找到一条经过七座桥且每座桥只走一次的路线 。
第四节 路径巡视问题凌晨,凌晨,
A B
C
D
D
C
A B
Ling Xueling
路径巡视问题,又称中国 邮递员 问题,1962 年首先由 （ 山东大学 ） 管梅谷先生提出抽象说就是：对给定的一个 连通图,在每条边 （ 弧
） 上赋予一个非负的权,要求一个 回路,过每边至少一次并使回路总权数最小－－ 商店在弧 不在结点处首先介绍一,一笔画问题
1,问题网络中,视路径没有方向,也 不 一定要求 起点＝终点,但要求任意路径 （ 弧 ） 仅经过一次 的问题,称之为一笔画问题 。
第四节 路径巡视问题凌晨,凌晨,
Ling Xueling
一,一笔画问题
2,有关的定义
1） 结点的价 （ Valency）
从某个结点可引出的,路径,（ 弧 ） 之数量称为该结点的价
2） 奇,偶结点由结点的 价 一意决定
3）,价,的意义 （ 注意：所有,弧,都必须经历 ）
奇 结点 ―― 不是 起点 就是 终点 ；
偶 结点 ―― 只可能是 经过点 ；
4） 半欧拉图定义连通图中若：只有两个相异同的 奇 结点,其余皆为偶结点 。
第四节 路径巡视问题凌晨,凌晨,
Ling Xueling
一,一笔画问题
2,有关的定义
5） 欧拉图所有 结点都是 偶 结点的连通图
3,（ 握手 ） 定理连通图中各结点价数之和 ＝ 2?（ 路径数量 ）
4,推论任意连通图中,奇结点的个数总是偶数证明：由握手定理得,奇结点价数之和＋偶结点价数之和＝
偶数,所以 奇结点价数之和＝偶数 。
第四节 路径巡视问题凌晨,凌晨,
Ling Xueling
一,一笔画问题
5,定理连通图是欧拉图,当且仅当其中无奇结点定理的意义：
1） 若连通图是 欧拉图－－无奇结点,则可以任意结点为起点,一笔画后仍然 回到起点 ；
2） 若连通图是 半 欧拉图－－两个 奇结点,则从某奇结点出发,一笔画后以 另一个奇结点为终点；
3） 若连通图有四或以上个 奇结点－－巡视回路,不可能不走重复路经－－问题,最小重复？ 。
第四节 路径巡视问题凌晨,凌晨,
Ling Xueling
二,最短巡视路径
1,问题起点＝终点,无方向,任意路径仅经过一次,要求使得赋权的连通图之 总权数最小,可用于配送问题决策
2,欧拉图 （ 所有节点皆为偶节点的连通图 ）
可以任意选择起点,完成一笔画后总能回到起点,且,总权数也最小
3,非欧拉图 （ 奇结点个数总是偶数 ） 的最小总权数先罗列出 所有奇节点 ―― 写出 所有可能的 两两配对方案
―― 重复路径－－分别计算各方案下的最短 （ 附加 ） 连接路径 ―― 小中取小例子见下页 。
第四节 路径巡视问题凌晨,凌晨,
Ling Xueling
8
6
7
4
5
5
3
8
4
7
W
V
UZ
Y
X
3,非欧拉图的最小总权数例子：从 V 开始,并在 V 结束进行巡视,至少经过每一弧一次,最短路径是？
第四节 路径巡视问题凌晨,凌晨,
Ling Xueling
二,最短巡视路径
3,非欧拉图的最小总权数例子的解配对 最短路 期望的路径之长度
W和 X Y和 Z WX YZ 5＋ 7＝ 12
W和 Y X和 Z WXY XUZ (5+4) + (5+3) = 17
W和 Z X和 Y WUZ XY (4+3) + 4 = 11
因为第三种配对的路径最短,连接后总巡视路径长度 ＝ 68
故巡视路径应是,VWUWXYZVYXUZUV（ 详见下页 ） 。
第四节 路径巡视问题凌晨,凌晨,
Ling Xueling
双线表示重复路径
7
3
Z U 6
7
Y 8 V
5 4
4 8
X W
5
第四节 路径巡视问题凌晨,凌晨,
Ling Xueling
补充练习：道路管理人员从 A 点出发,欲经过他所管辖的所有道路 。 这些道路分布在九个点之间,所有各点之间的道路长度如下图所示,请设计经过所有道路的最短路线 。
第四节 路径巡视问题凌晨,凌晨,
IH
G
F
E
D
C
B
A
120
130130
50
130
120120
130
120120
130 50
120
120120 130
120
50
Ling Xueling
练习题：道路管理人员从 A 点出发,欲经过他所管辖的所有道路 。 这些道路分布在九个点之间,所有各点之间的道路长度如图所示,请设计经过所有道路的最短路线 。
解答：
在 C,H 之间和 I,E 之间各添加一条路线,则最短路线是
ABGHBCHCDHIDEIEFIGFAG
第四节 路径巡视问题凌晨,凌晨,
Ling Xueling
The End of Chapter 8
网络模型的讨论,本质上属于 图论 范畴用途极其广泛 （ 如,运输系统设计,信息系统设计,项目计划管理等 ）,实用性强,是网络模型的特征之一,其解法的特殊,也是值得关注的地方需要重点掌握：各种网络模型的 算法 。
第八章 网络模型凌晨,凌晨,
Ling Xueling
一,问题及网络图表示
1,什么是最短路问题在网络中 任意 选择某点为起点,求出从此起点到网络中其余各点的最短路径 。 如,Taxi 的调度问题
2,例子
Gorman 建筑公司承担了散布在邻近三个区域内的一些建筑项目,公司总部与这些工地之间经常有人员,设备,材料等的运输往来 。 与运输成本相关的最短路问题,就是很值得考虑的重要问题设公司总部与六个工地间的公路网络如下页所示：
( 单位,km )。
第一节 最短路问题凌晨,凌晨,
Ling Xueling
一,问题及网络图表示第一节 最短路问题凌晨,凌晨,
1
2
3
4
5
6
7
总部
15
3
10
17
6
2
4
6 5
4
n od e
a r c
Ling Xueling
二,最 短 路 算 法 － － 介 绍 Dijkstra 算法
(Dijkstra 于 1959 年提出,又称加标号法
labeling procedure )
1,结点之标号 (给出：累计路程,路径两个指标 )
第一节 最短路问题凌晨,凌晨,
2 0,4
结点表示从起始结点到本结点的距离是 2 0
表示从起始结点到本结点的最短路径上前一个结点是 4
Ling Xueling
二,最短路算法 （ Dijkstra算法 ）
2,结点标号的分类
1） 有 /无标号结点有 标号结点－－已指定从起始结点到此结点的一条路径无 标号结点－－未指定从起始结点到此结点的路径
2） 永久 /临时标号有 永久 标号结点－－已求出从起始点到此结点的最短路径有 临时 标号结点－－未求出从起始点到此结点的最短路径 。
第一节 最短路问题凌晨,凌晨,
Ling Xueling
二,最短路算法 （ Dijkstra算法 ）
3,例子的解
1 ) 定起始点,写上永久标号 [0,S]－－ 如,结点内涂黑表示已有永久标号
2 ) ( 迭代 ) 反复以下步骤：
(1) 为起始点能直达的结点写上临时标号
(2) 比较临时标号内第一个数,选择小的一个
(3) 小者写成永久标号 ( 圈内涂黑 )
(4) 有 最新永久标号 的结点视为 新的起始点 。
第一节 最短路问题凌晨,凌晨,
Ling Xueling
二,最短路算法 （ Dijkstra算法 ）
4,求出最短路
1－ 3－ 2 1－ 3 1－ 3－ 5－ 4 1－ 3－ 5
1－ 3－ 5－ 6 1－ 3－ 5－ 6－ 7
5,第二个例子在如下页的网络中,求结点 1 和结点 10 之间的最短路径解答,1－－ 3－－ 5－－ 8－－ 10
total = 19。
第一节 最短路问题凌晨,凌晨,
Ling Xueling
二,最短路算法 （ Dijkstra算法 ）
第一节 最短路问题凌晨,凌晨,
1
2
3
4 5
6
7
8
9
10
2
5
1
12
14
6
10
4
13
12
11
3
9
6
5
8
10
5
2
Ling Xueling
三,说明
1,算法中,起始结点可以任意选定,N 个结点问题,
一般需要有 N－ 1 次迭代
2,,MS”软件包只要先输入网络,可以解决此类问题
3,其它用处：最小旅行时间问题,旅行成本问题,管道铺设问题,线路安排问题,厂区布局问题,设备更新问题 等等
4,练习的第四题 ―― 设备维护问题说明
5,标号法已发展到可以解决,(时间所限不展开讨论 )
(1) 弧值为负数；
(2) 有向网络 ( 如：单行道运输问题 )。
第一节 最短路问题凌晨,凌晨,
Ling Xueling
一,概念
1,树－－不含圈的 联通 图
2,什么是 （ 网络 ） 最小支撑树
1) 贯通网络所有结点 ―― 支撑
2) 分枝 (弧 ) 总长度最小 ―― 最小
3,用处：分子结构问题,电网络分析问题,计算机网络设立问题,管道铺设问题等等的解决 。
第二节 最小支撑树问题凌晨,凌晨,
Ling Xueling
二,实例计算机中心欲使五家新用户与中心联机电话公司负责排线,由于价格昂贵,要寻求最小支撑树由于计算机网络的可联通性能,得到：
第二节 最小支撑树问题凌晨,凌晨,
中心
1
2
3
4
5
6
20
40
50
40
30
40
10
30
30
20
40
Ling Xueling
三,算法一 ( Greedy algorithm )
1,因为问题很特殊,就有：若每一步追求最优,最后也能得到问题的最优的解法－－贪心解法
2,作法
1) 对弧的长短按照升序排序
2)任意 结点开始,在保证 不构成圈 的前提下
3) 重复进行：将 最近 的不联通结点并入网络的联通段 （ 可以双线表示联通 ）
3,说明：最小支撑树 不唯一,但分枝总长度唯一
4,例子的计算－－略 。 o.f.=110。
第二节 最小支撑树问题凌晨,凌晨,
Ling Xueling
三,算法一 ( Greedy algorithm )
第二个例子 （ 总长度＝ 28）
第二节 最小支撑树问题凌晨,凌晨,
1
2
3
4
5
6
7
8
9
10
11
3
3
2
4
2
4
4
42
3
3
4
5
3
2
3
4
7
6
5
4
4
Ling Xueling
四,算法二 （ Prim’s algorithm）
1,算法一的缺点,（ 1） 需要先排序 （ 2） 每一步都需要仔细确认有没有构成圈 ―― 故,不适合于复杂,大型的网络模型
2,算法二的步骤
1） 任意选择一个起点；
2） 选择与起点 最近的 顶点,将此顶点及其与起点相连接的弧一并加入树；
3） 对已经连接成树的部分,仍然选择与树 最近的 顶点,然后连上；
4） 重复步骤三,直到所有的顶点都连接上 。
第二节 最小支撑树问题凌晨,凌晨,
Ling Xueling
一,概念
1,什么是最大流问题有一个称之为入口点 ( source node ) 结点和一个出口点 ( sink
node ) 结点的网络,在给定时期内进 / 出最大流量是？
2,用处交通网络之流量,计算机网络之信息流量,金融系统中现金流量,物流流量,防洪系统设计,排水系统设计,供水系统等,.........
3,基本假定分枝 ( arc )－－ 有流量限制且讲究方向结点 ( node )－－ 进,出相等 。
第三节 最大流问题凌晨,凌晨,
Ling Xueling
4,例子某国道自北向南方向计划进行大修,运输部门拟以如下网络的公路系统暂时替代之 （ 单位,1000）
问题：此网络能否适应 15000 辆机动车的最大流 /小时？ 每小时最大流量是多少？ 每一条分枝分别有多大流通过？
第三节 最大流问题凌晨,凌晨,
1
2
3
4
5
6
7
s ou r c e
s i n k
北南
5
0
6
0
2
2
3 0
3
0
5
0
3
0
7
0
1
1
8
0
5
0
7
0
5 - - - 7 每小时机动车流量为 5 0 0 0
Ling Xueling
二,最大流算法
1,方法说明
1） 寻找从入口到出口的路径 ( 要保证此路径可以有流量 >0 的 flow 通过 )
2) 将 1) 中 所寻得的路径尽可能多地增加流量
3) 重复第 1) 2) 步骤,其中用到虚构流手段,直至找不到可使 flow > 0 的路径为止 。
第三节 最大流问题凌晨,凌晨,
Ling Xueling
二,最大流算法
2,虚构流 ( fictitious flow ) 方法对如下路径：
若修改成为：
表明,1) 3? 6 分枝上剩余可安排流量为 1000
2) 6? 3 的 6000 单位实际上是所谓的 虚构流
3) 虚构流－－简明地表示 3? 6 方向之流量应下降或,简明地表示若还要增加 3? 6 方向之流量应转到其它分枝上去 。
第三节 最大流问题凌晨,凌晨,
3 6
7 0
单位,1 0 0 0
3 61 6
Ling Xueling
二,最大流算法
3,实例计算可能的五次流量安排如下：
1) 1－－ 3－－ 6－－ 7,pf = 6
2) 1－－ 2－－ 5－－ 7 pf = 3
3) 1－－ 2－－ 3－－ 5－－ 7 pf = 2
4) 1－－ 4－－ 6－－ 7 pf = 1
5) 1－－ 4－－ 6－－ 5－－ 7 pf = 1
此时得到如下网络流量图,（ 见下页 ）
第三节 最大流问题凌晨,凌晨,
Ling Xueling
二,最大流算法
3,实例计算
6) 1－－ 4－－ 6－－ 3－－ 5－－ 7 pf = 1
故,最大流＝ 14,其中的虚构流手段之说明见下页 。
第三节 最大流问题凌晨,凌晨,
1
2
3
4
5
6
7
北南
13
130
5
0 6
3
2
0 3
2
6
2
0
0
7
0
4
1
2
1
63
0
3
2
Ling Xueling
二,最大流算法
4,虚构流说明说明：原始网络中 6－－ 3 之流量＝ 0,此处安排 1000 辆车在 6－－ 3,实际是虚构流,此处对 6－－ 3 做 1000 的安排,
实为将原先在 1) 中允许进入 3－－ 6 分枝的 1000 单位流转入沿 3－－ 5 分枝,则 6－－ 7 可空 1000 单位流可供安排
5,最优解第三节 最大流问题凌晨,凌晨,
1
2
3
4
5
6
7
北南
6
2
3
3
1
7
5
3
7
5
3
1 4,0 0 0
1 4,0 0 0
Ling Xueling
二,最大流算法
6,第二个例子求下列网络之最大流 ( = 33 )
第三节 最大流问题凌晨,凌晨,
1
2
3
4 5
6
7
8
9
10
0
8
0
10
0
5 5
2
2
5
5
6 6
5
5
3
3
4
4
6
6
10
10
3
3
8
0
2
2
10
0
10
0
Ling Xueling
18 世纪,29 岁的欧拉解决了哥尼斯堡七桥问题：
抽象出,图,,
结论,不是欧拉 图,亦非半欧拉图,不论起点和终点在哪里都不可能找到一条经过七座桥且每座桥只走一次的路线 。
第四节 路径巡视问题凌晨,凌晨,
A B
C
D
D
C
A B
Ling Xueling
路径巡视问题,又称中国 邮递员 问题,1962 年首先由 （ 山东大学 ） 管梅谷先生提出抽象说就是：对给定的一个 连通图,在每条边 （ 弧
） 上赋予一个非负的权,要求一个 回路,过每边至少一次并使回路总权数最小－－ 商店在弧 不在结点处首先介绍一,一笔画问题
1,问题网络中,视路径没有方向,也 不 一定要求 起点＝终点,但要求任意路径 （ 弧 ） 仅经过一次 的问题,称之为一笔画问题 。
第四节 路径巡视问题凌晨,凌晨,
Ling Xueling
一,一笔画问题
2,有关的定义
1） 结点的价 （ Valency）
从某个结点可引出的,路径,（ 弧 ） 之数量称为该结点的价
2） 奇,偶结点由结点的 价 一意决定
3）,价,的意义 （ 注意：所有,弧,都必须经历 ）
奇 结点 ―― 不是 起点 就是 终点 ；
偶 结点 ―― 只可能是 经过点 ；
4） 半欧拉图定义连通图中若：只有两个相异同的 奇 结点,其余皆为偶结点 。
第四节 路径巡视问题凌晨,凌晨,
Ling Xueling
一,一笔画问题
2,有关的定义
5） 欧拉图所有 结点都是 偶 结点的连通图
3,（ 握手 ） 定理连通图中各结点价数之和 ＝ 2?（ 路径数量 ）
4,推论任意连通图中,奇结点的个数总是偶数证明：由握手定理得,奇结点价数之和＋偶结点价数之和＝
偶数,所以 奇结点价数之和＝偶数 。
第四节 路径巡视问题凌晨,凌晨,
Ling Xueling
一,一笔画问题
5,定理连通图是欧拉图,当且仅当其中无奇结点定理的意义：
1） 若连通图是 欧拉图－－无奇结点,则可以任意结点为起点,一笔画后仍然 回到起点 ；
2） 若连通图是 半 欧拉图－－两个 奇结点,则从某奇结点出发,一笔画后以 另一个奇结点为终点；
3） 若连通图有四或以上个 奇结点－－巡视回路,不可能不走重复路经－－问题,最小重复？ 。
第四节 路径巡视问题凌晨,凌晨,
Ling Xueling
二,最短巡视路径
1,问题起点＝终点,无方向,任意路径仅经过一次,要求使得赋权的连通图之 总权数最小,可用于配送问题决策
2,欧拉图 （ 所有节点皆为偶节点的连通图 ）
可以任意选择起点,完成一笔画后总能回到起点,且,总权数也最小
3,非欧拉图 （ 奇结点个数总是偶数 ） 的最小总权数先罗列出 所有奇节点 ―― 写出 所有可能的 两两配对方案
―― 重复路径－－分别计算各方案下的最短 （ 附加 ） 连接路径 ―― 小中取小例子见下页 。
第四节 路径巡视问题凌晨,凌晨,
Ling Xueling
8
6
7
4
5
5
3
8
4
7
W
V
UZ
Y
X
3,非欧拉图的最小总权数例子：从 V 开始,并在 V 结束进行巡视,至少经过每一弧一次,最短路径是？
第四节 路径巡视问题凌晨,凌晨,
Ling Xueling
二,最短巡视路径
3,非欧拉图的最小总权数例子的解配对 最短路 期望的路径之长度
W和 X Y和 Z WX YZ 5＋ 7＝ 12
W和 Y X和 Z WXY XUZ (5+4) + (5+3) = 17
W和 Z X和 Y WUZ XY (4+3) + 4 = 11
因为第三种配对的路径最短,连接后总巡视路径长度 ＝ 68
故巡视路径应是,VWUWXYZVYXUZUV（ 详见下页 ） 。
第四节 路径巡视问题凌晨,凌晨,
Ling Xueling
双线表示重复路径
7
3
Z U 6
7
Y 8 V
5 4
4 8
X W
5
第四节 路径巡视问题凌晨,凌晨,
Ling Xueling
补充练习：道路管理人员从 A 点出发,欲经过他所管辖的所有道路 。 这些道路分布在九个点之间,所有各点之间的道路长度如下图所示,请设计经过所有道路的最短路线 。
第四节 路径巡视问题凌晨,凌晨,
IH
G
F
E
D
C
B
A
120
130130
50
130
120120
130
120120
130 50
120
120120 130
120
50
Ling Xueling
练习题：道路管理人员从 A 点出发,欲经过他所管辖的所有道路 。 这些道路分布在九个点之间,所有各点之间的道路长度如图所示,请设计经过所有道路的最短路线 。
解答：
在 C,H 之间和 I,E 之间各添加一条路线,则最短路线是
ABGHBCHCDHIDEIEFIGFAG
第四节 路径巡视问题凌晨,凌晨,
Ling Xueling
The End of Chapter 8
