行 遍 性 问 题数学建模与数学实验行 遍 性 问 题一、中 国 邮 递 员 问 题二、推 销 员 问 题三、建模案例：最佳灾情巡视路线
（一） 欧 拉 图
（二） 中 国 邮 递 员 问 题
（一） 哈 密 尔 顿 图
（二） 推 销 员 问 题定义 设图 G = （ V,E ）,M? E,若 M 的边互不相邻，则称 M 是 G 的一个 匹配,
若顶点 v 与 M 的一条边关联，则称 v 是 M 饱和的,
设 M 是 G 的一个匹配，若 G 的每个顶点都是 M 饱和的，则称
M 是 G 的 理想匹配,
7
3
1 2
3
4
1
24 5
5
6
6
7 8
9
割边
G的边 是割边的充要条件是 不含在 G的圈中．
割边的定义,设 G连通,E(G),若从 G中删除边 后，
图 G-{ }不连通，则称边 为图 G的割边．
e e
e e
e e
v
v
v
v
v
v
v
e
e
e
ee
e
e e
e
e3
v1 v2
v3v4
e1
e2e4 e5e
6
欧 拉 图定义１ 设 G =( V,E ) 是连通无向图
（１）经过 G 的每边至少一次的闭通路称为 巡回,
（２）经过 G 的每边正好一次的巡回称为 欧拉巡回,
（３）存在欧拉巡回的图称为 欧拉图,
（４）经过 G 的每边正好一次的道路称为 欧拉道路,
e3
v1 v2
v3v4
e1
e 2e4 e5
巡回,v1e1v2e2v3e5v1e4v4e3v3e5v1
欧拉道路,v1e1v2e2v3e5v1e4v4e3v3 欧拉巡回：
v1e1v2e2v3e5v1e4v4e3v3e6v1
定理１ 对于非空连通图 G,下列命题等价,
（１） G 是欧拉图,
（２） G 无奇次顶点,
（３） G 的边集能划分为圈,
推论１ 设 G 是非平凡连通图，则 G 有欧拉道路的充要条件是 G 最多只有两个奇次顶点,
e3
v1 v2
v3v4
e1
e2e4 e5
e3
v1 v2
v3v 4
e1
e2e4 e5e
6
欧拉图 非欧拉图返回中国邮递员问题 -定义邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线．这就是 中国邮递员问题,
若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图．中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回．这样的巡回称为 最佳巡回,
中国邮递员问题 -算法
1,G 是欧拉图此时 G 的任何一个欧拉巡回便是最佳巡回．问题归结为在欧拉图中确定一个欧拉巡回,
F l e u r y 算法,求欧拉图的欧拉巡回,
Fleury算法基本思想,从任一点出发，每当访问一条边时，先要进行检查．如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边 作为访问边，直到没有边可选择为止,
v7
e3
v1 v2
v3v4
e1
e2e4 e5
v5
e6e6
e 7 e8
e9
e10
Fle ury 算法 — 算法步骤,
（１）任选一个顶点 v 0,令道路 w 0 =v 0,
（２）假定道路 w i =v 0 e 1 v 1 e 2 … e i v i 已经选好，则从 E \ { e 1,e 2,…,e i } 中选一条边 e i+ 1,使,
a ） e i+ 1 与 v i 相关联
b ）除非不能选择，否则一定要使 e i+ 1 不是 G i =G [ E - { e 1,e 2,…,e i }]
的割边,
（３）第（２）步不能进行时就停止,
2,G 不是欧拉图若 G不是欧拉图，则 G的任何一个巡回经过某些边必定多于一次．
解决这类问题的一般方法是：在一些点对之间引入重复边（重复边与它平行的边具有相同的权），
使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小．
情形１ G 正好有两个奇次顶点
（１）用 Di j k s t r a 算法求出奇次顶点 u 与 v 之间的最短路径 P,
（２）令 G * = G? P,则 G * 为欧拉图,
（３）用 F l e u r y 算法求出 G * 的欧拉巡回，这就是 G 的最佳巡回,
v7
e3
v1 v2
v3v4
e1
e2e4 e5
v5
v6e6
e7 e8
e9
情形２ G 有２ n 个奇次顶点（ n? ２）
E d m o n d s 最小对集算法：
基本思想,
先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小．再沿点对之间的最短路径添加重复边得欧拉图 G *,G * 的欧拉巡回便是原图的最佳巡回,
算法步骤：
（１）用 F l o y d 算法求出所有奇次顶点之间的最短路径和距离,
（２）以 G 的所有奇次顶点为顶点集（偶数个元素），作一完备图，
边上的权为两端点在原图 G 中的最短距离，将此完备加权图记为 G 1,
（４）在 G 中沿配对顶点之间的最短路径添加重复边得欧拉图 G *,
（５）用 F l e u r y 算法求出 G * 的欧拉巡回，这就是 G 的最佳巡回,
（３）求出 G1的 最小权理想匹配 M，得到奇次顶点的最佳配对,
例 求右图所示投递区的一条最佳邮递路线．
1,图中有 v 4,v 7,v 8,v 9 四个奇次顶点用 F l o y d 算法求出它们之间的最短路径和距离：
3),(,
6),(,
9),(,
6)(,
3),(,
5),(,
9898
9797
8787
9,4984
8484
747234
98
97
87
94
84
74
vvdvvP
vvdvvP
vvdvvP
vvdvvvP
vvdvvP
vvdvvvvP
vv
vv
vv
vv
vv
vv
2,以 v 4,v 7,v 8,v 9 为顶点，他们之间的距离为边权构造完备图 G 1,
3,求出 G 1 的最小权完美匹配 M= {( v 4,,v 7 ),( v 8,v 9 )},
4,在 G 中沿 v 4 到 v 7 的最短路径添加重复边，沿 v 8 到 v 9 的最短路径 v 8 v 9 添加重复边，得欧拉图 G 2,G 2 中一条欧拉巡回就是 G 的一条最佳巡回．其权值为 64,
返回哈 密 尔 顿 图定义 设 G =( V,E ) 是连通无向图,
（１） 经过 G 的每个顶点正好一次的路径，称为 G 的一条哈密尔顿路径,
（２） 经过 G 的每个顶点正好一次的圈，称为 G 的 哈密尔顿圈 或 H 圈,
（３）含 H 圈的图称为 哈密尔顿图 或 H 图,
返回推销员问题 -定义流动推销员需要访问某地区的所有城镇，最后回到出发点．问如何安排旅行路线使总行程最小．这就是 推销员问题,
若用顶点表示城镇，边表示连接两城镇的路，
边上的权表示距离（或时间、或费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题．
定义 在加权图 G=(V,E)中,
（ １ ） 权最小的哈密尔顿圈称为 最佳 H圈,
（ ２ ） 经过每个顶点至少一次的权最小的闭通路称为 最佳推销员回路,
一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，
同样最佳推销员回路也不一定是最佳哈密尔顿圈．
H回路，长 22 最佳推销员回路，长 4
定理１ 在加权图 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) = m i nd G ( x,y )
定理２ 加权图 G 的最佳推销员回路的权与 G ’ 的最佳 H 圈的权相同,
推销员问题近似算法,二边逐次修正法,
( 1 ) 任取初始 H 圈,C 0 =v 1,v 2,…,v i,,…,v j,…,v n,v 1
( 2) 对所有的 i,j,1 <i+ 1 < j < n,若
w(v i,v j ) + w(v i+ 1,v j+ 1 )< w(v i,v i+ 1 ) + w(v j,v j+ 1 )
则在 C 0 中删去边 ( v i,v i+ 1 ) 和 ( v j,v j+ 1 ) 而加入边 ( v i,v j ) 和 ( v i+ 1,v j+ 1 ),形成新的 H 圈 C,即
C= v 1,v 2,…,v i,,v j,v j - 1,…,v i+ 1,v j+ 1,…,v n,v 1
( 3 ) 对 C 重复步骤 ( 2 ),直到条件不满足为止，最后得到的 C 即为所求,
例 对以下完备图,用二边逐次修正法求较优 H圈,
返回
（一） 欧 拉 图
（二） 中 国 邮 递 员 问 题
（一） 哈 密 尔 顿 图
（二） 推 销 员 问 题定义 设图 G = （ V,E ）,M? E,若 M 的边互不相邻，则称 M 是 G 的一个 匹配,
若顶点 v 与 M 的一条边关联，则称 v 是 M 饱和的,
设 M 是 G 的一个匹配，若 G 的每个顶点都是 M 饱和的，则称
M 是 G 的 理想匹配,
7
3
1 2
3
4
1
24 5
5
6
6
7 8
9
割边
G的边 是割边的充要条件是 不含在 G的圈中．
割边的定义,设 G连通,E(G),若从 G中删除边 后，
图 G-{ }不连通，则称边 为图 G的割边．
e e
e e
e e
v
v
v
v
v
v
v
e
e
e
ee
e
e e
e
e3
v1 v2
v3v4
e1
e2e4 e5e
6
欧 拉 图定义１ 设 G =( V,E ) 是连通无向图
（１）经过 G 的每边至少一次的闭通路称为 巡回,
（２）经过 G 的每边正好一次的巡回称为 欧拉巡回,
（３）存在欧拉巡回的图称为 欧拉图,
（４）经过 G 的每边正好一次的道路称为 欧拉道路,
e3
v1 v2
v3v4
e1
e 2e4 e5
巡回,v1e1v2e2v3e5v1e4v4e3v3e5v1
欧拉道路,v1e1v2e2v3e5v1e4v4e3v3 欧拉巡回：
v1e1v2e2v3e5v1e4v4e3v3e6v1
定理１ 对于非空连通图 G,下列命题等价,
（１） G 是欧拉图,
（２） G 无奇次顶点,
（３） G 的边集能划分为圈,
推论１ 设 G 是非平凡连通图，则 G 有欧拉道路的充要条件是 G 最多只有两个奇次顶点,
e3
v1 v2
v3v4
e1
e2e4 e5
e3
v1 v2
v3v 4
e1
e2e4 e5e
6
欧拉图 非欧拉图返回中国邮递员问题 -定义邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线．这就是 中国邮递员问题,
若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图．中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回．这样的巡回称为 最佳巡回,
中国邮递员问题 -算法
1,G 是欧拉图此时 G 的任何一个欧拉巡回便是最佳巡回．问题归结为在欧拉图中确定一个欧拉巡回,
F l e u r y 算法,求欧拉图的欧拉巡回,
Fleury算法基本思想,从任一点出发，每当访问一条边时，先要进行检查．如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边 作为访问边，直到没有边可选择为止,
v7
e3
v1 v2
v3v4
e1
e2e4 e5
v5
e6e6
e 7 e8
e9
e10
Fle ury 算法 — 算法步骤,
（１）任选一个顶点 v 0,令道路 w 0 =v 0,
（２）假定道路 w i =v 0 e 1 v 1 e 2 … e i v i 已经选好，则从 E \ { e 1,e 2,…,e i } 中选一条边 e i+ 1,使,
a ） e i+ 1 与 v i 相关联
b ）除非不能选择，否则一定要使 e i+ 1 不是 G i =G [ E - { e 1,e 2,…,e i }]
的割边,
（３）第（２）步不能进行时就停止,
2,G 不是欧拉图若 G不是欧拉图，则 G的任何一个巡回经过某些边必定多于一次．
解决这类问题的一般方法是：在一些点对之间引入重复边（重复边与它平行的边具有相同的权），
使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小．
情形１ G 正好有两个奇次顶点
（１）用 Di j k s t r a 算法求出奇次顶点 u 与 v 之间的最短路径 P,
（２）令 G * = G? P,则 G * 为欧拉图,
（３）用 F l e u r y 算法求出 G * 的欧拉巡回，这就是 G 的最佳巡回,
v7
e3
v1 v2
v3v4
e1
e2e4 e5
v5
v6e6
e7 e8
e9
情形２ G 有２ n 个奇次顶点（ n? ２）
E d m o n d s 最小对集算法：
基本思想,
先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小．再沿点对之间的最短路径添加重复边得欧拉图 G *,G * 的欧拉巡回便是原图的最佳巡回,
算法步骤：
（１）用 F l o y d 算法求出所有奇次顶点之间的最短路径和距离,
（２）以 G 的所有奇次顶点为顶点集（偶数个元素），作一完备图，
边上的权为两端点在原图 G 中的最短距离，将此完备加权图记为 G 1,
（４）在 G 中沿配对顶点之间的最短路径添加重复边得欧拉图 G *,
（５）用 F l e u r y 算法求出 G * 的欧拉巡回，这就是 G 的最佳巡回,
（３）求出 G1的 最小权理想匹配 M，得到奇次顶点的最佳配对,
例 求右图所示投递区的一条最佳邮递路线．
1,图中有 v 4,v 7,v 8,v 9 四个奇次顶点用 F l o y d 算法求出它们之间的最短路径和距离：
3),(,
6),(,
9),(,
6)(,
3),(,
5),(,
9898
9797
8787
9,4984
8484
747234
98
97
87
94
84
74
vvdvvP
vvdvvP
vvdvvP
vvdvvvP
vvdvvP
vvdvvvvP
vv
vv
vv
vv
vv
vv
2,以 v 4,v 7,v 8,v 9 为顶点，他们之间的距离为边权构造完备图 G 1,
3,求出 G 1 的最小权完美匹配 M= {( v 4,,v 7 ),( v 8,v 9 )},
4,在 G 中沿 v 4 到 v 7 的最短路径添加重复边，沿 v 8 到 v 9 的最短路径 v 8 v 9 添加重复边，得欧拉图 G 2,G 2 中一条欧拉巡回就是 G 的一条最佳巡回．其权值为 64,
返回哈 密 尔 顿 图定义 设 G =( V,E ) 是连通无向图,
（１） 经过 G 的每个顶点正好一次的路径，称为 G 的一条哈密尔顿路径,
（２） 经过 G 的每个顶点正好一次的圈，称为 G 的 哈密尔顿圈 或 H 圈,
（３）含 H 圈的图称为 哈密尔顿图 或 H 图,
返回推销员问题 -定义流动推销员需要访问某地区的所有城镇，最后回到出发点．问如何安排旅行路线使总行程最小．这就是 推销员问题,
若用顶点表示城镇，边表示连接两城镇的路，
边上的权表示距离（或时间、或费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题．
定义 在加权图 G=(V,E)中,
（ １ ） 权最小的哈密尔顿圈称为 最佳 H圈,
（ ２ ） 经过每个顶点至少一次的权最小的闭通路称为 最佳推销员回路,
一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，
同样最佳推销员回路也不一定是最佳哈密尔顿圈．
H回路，长 22 最佳推销员回路，长 4
定理１ 在加权图 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) = m i nd G ( x,y )
定理２ 加权图 G 的最佳推销员回路的权与 G ’ 的最佳 H 圈的权相同,
推销员问题近似算法,二边逐次修正法,
( 1 ) 任取初始 H 圈,C 0 =v 1,v 2,…,v i,,…,v j,…,v n,v 1
( 2) 对所有的 i,j,1 <i+ 1 < j < n,若
w(v i,v j ) + w(v i+ 1,v j+ 1 )< w(v i,v i+ 1 ) + w(v j,v j+ 1 )
则在 C 0 中删去边 ( v i,v i+ 1 ) 和 ( v j,v j+ 1 ) 而加入边 ( v i,v j ) 和 ( v i+ 1,v j+ 1 ),形成新的 H 圈 C,即
C= v 1,v 2,…,v i,,v j,v j - 1,…,v i+ 1,v j+ 1,…,v n,v 1
( 3 ) 对 C 重复步骤 ( 2 ),直到条件不满足为止，最后得到的 C 即为所求,
例 对以下完备图,用二边逐次修正法求较优 H圈,
返回
