关于中国邮递员问题和欧拉图应用

欧拉图
欧拉图
例：(七桥问题)18世纪东普鲁士有一个城市称为个普 尼斯堡，它位于普雷格尔河畔，河中有两个小岛， 通过七座桥彼此相联（如图）。 当时有人提出：能否从某个地点出发经过每个桥一 次且仅一次然后返回出发点？
A B D
C
欧拉图 Euler的解：
A
D B
C
欧拉图 例: 中国邮路问题
1962年中国数学家管梅谷提出：一个邮递 员从邮局出发递送邮件，要求对他所负责 的辖区的每条街至少走一次，问如何选取 路程最短 的路线？（加的重复的边的权值最少）这个问 题称为中国邮路问题。 该问题可用专门的算 “一笔画”
G 连通且 G 中度数为奇数的点的个数不超过2
定理3
• 定理: G 是非平凡（至少有两个点）的欧拉图当且 仅当G是连通的,且为若干个边不重的圈的 并.
• 证明：对于非平凡的G，则d(v)>=2，所以一定存在圈C，令G1=G-E（C）只减去边， 不减去点。则成为多个连通分支，之后每个分支存在圈，重复上述过程，则最终只剩 下孤立点，此时倒推，两两连通分支的边必然不相交，则定理1 定理3 反过来，可以将圈地交点进行分裂，成为一个大圈，重复这种变化，可以构造成一个 欧拉回路（至多n次）。则定理3 定理1
欧拉图 例
（a ）
（b）
（c）
（d）
（e）
（f）
欧拉图
定理:G是欧拉图当且仅当G是连通图且不含度为奇数 的点（定理1）；图G有欧拉通路但无欧拉回路，当且 仅当G是连通有两个度为奇的点。（定理2）（可以用 结论1证明结论2：奇次点连边成为欧拉图，然后回路 减去该边，则成为半欧拉图）
例如，对完全图 Kn，因 d(Kn) = n-1，故当n为奇数时是欧拉 图，当n为偶时不是欧拉图。

中国邮路问题中国邮递员问题⼀个邮递员送信，要⾛完他负责投递的所有街道（所有街道都是双向通⾏的且每条街道能够经过不⽌⼀次），完毕任务后回到邮局，应按如何的路线⾛，他所⾛的路程才会最短呢？解决⽅式1、图论建模因为街道是双向通⾏的，我们能够把它看成是赋权⽆向连通图，将路⼝模型为点，街道模型为边，街道的长度就是每条边的权值，问题转化为在图中求⼀条回路，使得回路的总权值最⼩。

1.1最理想的情况若图中有欧拉回路，由于欧拉回路通过全部的边，因此不论什么⼀个欧拉回路即为此问题的解。

1.2若G仅仅有两个Vi,Vj则有从Vi到Vj的欧拉迹，从Vj回到Vi则必须反复⼀些边，使反复边的总长度最⼩，转化为求从Vi到Vj的最短路径。

算法：1）找出奇点Vi,Vj之间的最短路径P；2）令G’ = G + P；3）G’为欧拉图，G’的欧拉回路即为最优邮路。

1.3普通情况，奇点数⼤于2的时，邮路必须反复很多其它的边。

Edmonds算法（匈⽛利算法）思想：步骤：1）求出G全部奇点之间的最短路径和距离；2）以G的全部奇点为结点（必为偶数），以他们之间的最短距离为节点之间边的权值，得到⼀个全然图G1；3）将M中的匹配边（Vi，Vj）写成Vi与Vj之间的最短路径经过的全部边集合Eij；4）令G’ = G U { Eij | (Vi,Vj)属于M}，则G’是欧拉图，求出最优邮路。

2、详细模块实现2.1最短路径⽤ Dijkstra算法计算Dijkstra算法是⼀种最短路径算法，⽤于计算⼀个节点到其他全部节点的最短路径。

2.1.1算法思想：按路径长度递增次序产⽣最短路径算法： 把V分成两组： 1）S：已求出最短路径的顶点的集合 2）V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序增加到S中，保证：1）从源点V0到S中各顶点的最短路径长度都不⼤于从V0到T中不论什么顶点的最短路径长度 2）每⼀个顶点相应⼀个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的仅仅包含S中顶点作中间顶点的最短路径长度2.1.2求最短路径步骤 1）初始时令 S={V0},T={ 其余顶点}，T中顶点相应的距离值 若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值；若不存在<V0,Vi>，d(V0,Vi)为∝ 2）从T中选取⼀个其距离值为最⼩的顶点W且不在S中，增加S 3）对S中顶点的距离值进⾏改动：若加进W作中间顶点，从V0到Vi的距离值缩短，则改动此距离值；反复上述步骤2、3，直到S中包括全部顶点，即W=Vi为⽌2.2图的连通性測试检測⽤户输⼊的图是否是连通图，不是的话没办法求解，提醒⽤户⼜⼀次输⼊。

欧拉( 欧拉( Euler )图问题
3
1736年欧拉把这个问题抽象成图论问题：用四个点v 1736年欧拉把这个问题抽象成图论问题：用四个点v1, 把这个问题抽象成图论问题 v2, v3, v4表示两岸及两个岛(称为顶点)，用两点间的连 表示两岸及两个岛(称为顶点 顶点) 表示桥(称为边 问题转化为: 线e1, e2, e3, e4, e5, e6, e7表示桥(称为边)，问题转化为: 从任何一个顶点出发，通过每一条边一次且仅一次，最 从任何一个顶点出发，通过每一条边一次且仅一次 每一条边一次且仅一次， 后回到该顶点，是否存在满足条件的走法？ 后回到该顶点，是否存在满足条件的走法？
13
B
7
3：哈密顿周游世界问题
英国数学家哈密顿于1856年提出周游世界的问题 英国数学家哈密顿于1856年提出周游世界的问题： 年提出周游世界的问题： G=<V,E>是连通无向图 是连通无向图： 哈密顿图 设G=<V,E>是连通无向图： 且城与城之间只有一 – 若要周游世界上的二十个名城， 若要周游世界上的二十个名城， 如果G中存在一条路径，经过G ①如果G中存在一条路径，经过G中每个结点且只经过 条路，则能否把每一个城走且只走一次， 条路，则能否把每一个城走且只走一次，最后返回到 一次，则称该路径为哈密顿路径； 一次，则称该路径为哈密顿路径； 原地. 原地. 中存在一条回路，经过G 如果G ②如果G中存在一条回路，经过G中每个结点且只经过 一次，则称该路径为哈密顿回路。 20个顶点分别表示 一次，则称该路径为哈密顿回路。 用20个顶点分别表示 – 该问题可以抽象为图论问题： 该问题可以抽象为图论问题： 存在哈密顿回路的图称为哈密顿图。 存在哈密顿回路的图称为哈密顿图。 20个城市，两个顶点间的连线表示城市间的路，要求 20个城市 两个顶点间的连线表示城市间的路， 个城市， 找一条从某点出发，经过各个顶点一次且仅一次， 顶点一次且仅一次 找一条从某点出发，经过各个顶点一次且仅一次，最 后能否返回到出发点的路线? 后能否返回到出发点的路线? 哈密顿(Hamilton)圈 哈密顿(Hamilton)圈问题

邮递员问题求解算法
若此连通赋权图是Euler图，则可用Fleury算法求Euler回路，此回路即为所求；关于非Euler图，1973年，Edmonds和Johnson给出下边的解法：
设G是连通赋权图，则
（i）求V0
{v|v
V(G),
d(v)
1(mod2)}；
（ii）对每对极点
u ,v V0，求
d(u,v)（
d
(u,v)
是
u
与v的距离，
可用
Floyd
算法求得）；
iii）结构完整赋权图K|V0|，以V0为极点集，以d(u,v)为边uv的权；
iv）求K|V0|中权之和最小的完满对集M；
v）求M中边的端点之间的在G中的最短轨；
vi）在（v）中求得的每条最短轨上每条边增添一条等权的所谓“倍边”（即共端点共权的边）；
vii）在（vi）中得的图G'上求Euler回路即为中国邮递员问题的解。

多邮递员问题求解
邮局有k(k2)位送达员，同时送达信函，全城街道都要送达，达成任务返回邮局，怎样分派送达路线，使得达成送达任务的时间最早？我们把这一问题记
成kPP。

KPP的数学模型以下：
G(V,E)是连通图，v0
V(G)，求G的回路
C1,
,C k，
使得
（i ）v0
V(C i)
，i1,2,,k，
（ii）max
(
)min，
w
e
ik e
E(C)
（ii i）
k
E
(C i)E(G)
1。