运筹学课件4.8 中国邮递员问题

第六节 中国邮递员问题

哥尼斯堡七桥问题与欧拉图 中国邮递员问题 求解中国邮递员问题的奇偶点图作业法 奇偶点图作业法的改进方法
一、哥尼斯堡七桥问题与欧拉图

哥尼斯堡七桥问题 欧拉图与一笔画问题
A
A C B 哥尼斯堡七桥问题 C D
D
B
二、中国邮递员问题

1962年，管梅谷先生提出 中国邮递员问题 若图中无奇点，欧拉圈即为所求 若图中有奇点，则奇点必为偶数，在奇点间加边 （重复走），使其变为偶数而成欧拉图。 中国邮递员问题是要求所加边的权之和最小。
三、求解中国邮递员问题的奇偶点图作业法


在奇点间加边，构造初始可行方案。 寻找改进可行方案：在两奇点间检查所有链，若 某链的长度小于已加重复边的长度，则在该链的 每边加上重复边，去掉原重复边。 重复以上步骤，直到任意两奇点间加重复边的链 是最短的为止。
求解中国邮递员问题：例子
v2
1 2 3 6
v3
4 2
5 1 2 2
v1
v6
v4
3
v5
例子的初始可行解
v2
1 2 3 6
v3
v4
4 2 3
5 1 2 2
5
v1
v6
2
v5
例子的修正解
v2
1 1 2 3 6
v3
v4
4 2 3
5 1 2 2 2
v1
v6
v5Leabharlann 四、奇偶点作业法的改进方法
奇偶点作业法的瓶颈是需检查太多的链 可以首先求出任意一对奇点之间的最短路， 从中选出总路长最小的组合方案。 也可以由奇点构成偶图，求最小匹配得到 最优解。

邮递员问题简介邮递员问题（Travelling Salesman Problem，TSP）是一个著名的组合优化问题，被称为计算机科学中的经典问题之一。

该问题起源于邮递员在一天内送货的最短路径问题。

邮递员需要从一个起点出发，经过所有的目标点，最后回到起点。

问题的目标是找到一条最短的路径，使得所有目标点都被访问，同时回到起点。

TSP问题涉及到组合爆炸，通常在计算上是NP难的。

问题描述给定一个有向图和一个起点，邮递员需要从起点出发经过所有的节点，最后回到起点。

每条边的权重表示从一个节点到另一个节点的距离。

找到一条最短路径，使得所有的节点都被访问且回到起点。

解决方法1. 枚举法枚举法是最简单的解决TSP问题的方法。

它通过遍历所有可能的路径，计算每条路径的总长度，并返回最短路径的长度和路径本身。

然而，由于TSP问题是NP难的，当图的规模增加时，枚举法的计算复杂度呈指数增长，很难在合理的时间内求解。

2. 动态规划法动态规划法是解决TSP问题的常用方法之一。

该方法通过将问题划分为子问题，并使用递归的方式求解。

具体而言，我们可以定义一个状态数组dp，其中dp[S][i]表示从起点到节点i，经过节点集合S中的所有节点，最后回到起点的最短路径长度。

那么，我们可以使用如下的递推关系来计算dp数组：dp[S][i] = min(dp[S-{i}][j] + dis(j, i))，其中j∈S，j≠i通过不断更新dp数组，最终可以得到从起点出发经过所有节点并回到起点的最短路径长度。

3. 遗传算法遗传算法是一种启发式优化算法，被广泛应用于解决TSP问题。

它模拟生物进化的过程，通过基因交叉、变异等操作，生成新的个体，并通过评估函数对个体进行选择。

遗传算法的优点是能够在较短的时间内找到接近最优解的解，但不能保证找到全局最优解。

4. 改进算法针对TSP问题，还有一些改进的算法，如蚁群算法、模拟退火算法、禁忌搜索等。

这些算法在不同的问题实例上可能会有更好的表现。

§4.中国邮递员问题（Chinese Postman Problem）1．问题的提出例5. 一个邮递员从邮局出发投递信件, 然后再返回邮局, 如果他必须至少一次地走过他负责投递范围内的每条街道, 街道路线如下图所示, 问选择怎样的路线才能使所走的路为最短?5 6 78问题的图论表述：在赋权G=[V, E]上找一条经每条边至少一次的权最小的圈。

1960年山东师范学院管梅谷教授首先提出此问题，并设计了一个“奇偶点表上作业法”，后来发现此法不是多项式算法，1973年，Edmonds和Johnson给出一个多项式算法。

2．哥尼斯堡七桥问题18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如下图所示。

城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。

3．Euler圈Euler圈：经图G的每条边的简单圈Euler图：具有Euler圈的图Euler图非Euler图下面讨论的图G允许有重边，且重边被认为是有区别的边。

伪Euler 圈：经图G 的每条边至少一次的圈点v 的次：与点V 关联的边的数目奇(偶)点：该点的次为奇(偶)数命题1：G 的奇点个数为偶数命题2：G 中有伪Euler 圈 ⇔ G 无奇点中国邮递员问题可表述为：在图G 中找一条权最小的伪Euler 圈。

对于邮递员来说，有些街道可能会重复走，原问题便转化为尽可能少走重复的 街道。

我们将这些重复的边组成的集合称可行集，即找最小的可行集。

命题3：E *是最小可行集 ⇔ωωμμμ()()()()*()*()e e e E E E e E E ≤∑∑∀μ∈∩∈∩\初等圈重复的边 非重复的边4．算法思路由命题1，简单图G 的奇点个数为偶数，可设为v 1 , v 2 , …, v 2k , 对每个1≤ i ≤k, 找v 2i − 1 至v 2i 的链p i ，将p i 的边重复一次。

中国邮递员问题
管梅谷教授首先提出的方法是奇偶点图上作业 法（1962年）
Edmonds，Johnson（1973年）给出有效算法。
复杂度为 O(|V(G)|2|E(G)|)
中国邮递员问题
中国邮递员问题
解决这样的问题，可以采用奇偶 点图上作业法：如果在配送范围 内，街道中没有奇点，那么他就 可以从配送中心出发，走过每条 街道一次，且仅一次，最后回到 配送中心，这样他所走的路程也 就是最短的路程。
原来的问题可以叙述为在一个有奇点的图中， 要求增加一些重复边，使新图不含奇点，并且 重复边的总权为最小。
我们把使新图不含奇点而增加的重复边简称为 可行（重复边）方案，使总权最小的可行方案 为最优方案。
现在的问题是第一个可行方案如何确定？ 在确定一个可行方案后，怎么判断这个方案是
否为最优方案？ 若不是最优方案，如何调整这个方案？
Fleury算法的复杂度是 O(| E(G)|2)
中国邮递员问题
求欧拉回路的算法(回路算法)
算法思想: 首先得到一个回路C1, 再在剩
下的图G- C1中求一条与C1有公共顶点的
回路C2, 则C1与 C2构成一个更长的回路,
继续下去可得到含所有边恰好一次的回
路. 回路算法的复杂度是
O(|
E(G) |)
这个问题就是一笔画问题。
中国邮递员问题
管梅谷教授。
上海市人。1957年毕业于华 东师范大学数学系。历任 山东师范大学讲师、副教 授、教授、校长，中国运 筹学会第一、二届常务理 事，山东省数学学会第四 届副理事长，山东省运筹 学会第一届副理事长，山 东省世界语协会理事长。 是第六届全国政协委员。 从事运筹学及其应用的研 究，对最短投递路线问题 的研究取得成果。所提模 型在国外称为中国投递问 题。

中国邮递员问题第一篇：中国邮递员问题运筹学第六组运筹学个人心得之中国邮递员问题我们第六组做的第二次案例就是中国邮递员问题，这个问题是运筹学中的经典命题。

这个案例讲的是：在中国的六个县城，每个县城都有一个县局，县局下面设立若干个邮政所，每天邮递员的任务就是从县局出发，依次到每一个邮政所送邮件，要求每个邮政所都必须去，而且只能去一次。

这就涉及到一个路线的规划问题，怎么走才能使得邮递员走的路最少，而且能够完成任务。

在做题之前考虑了很久，真不知道从何着手，国为以前确实没有接触过这个类型的题，没有一个能够行得通的办法。

后来，我们选定了一个代表性的区域，来尝试求解，国为第六个区域的变量最多，所以就选择这个区域作为突破口。

只要第六个区域求解成功，其它五个区域便迎刃而解了。

首先，我们画了一个由第六区域的十七个点所组成的17*17矩阵，一一对应设定变量，在去除对角线的17个变量之后，我们得到272个变量。

这是一个非常庞大的变量群体，若按传统的线性规划方法求解，求解过程将会变得异常艰辛，而且以前的模板，求解工具都不能求解这么多变量。

所以我们一度陷入混乱，求解工作停滞不前。

后来老师在对这价目案例作初步的讲解的时候，提出了用运输模型来对这个问题进行求解，此话一出，真是如醍醐灌顶，酣畅极了，眼前简直豁然一亮，真想“拍案而起”。

若用运输模型求解，这个问题将会变得非常简单。

一方面由于每行的出发点只能有一个，而每列的终点也只能有一个，这样看来，邮运筹学第六组递员总是变成了一个产销平衡的运输问题，产量和销量都有是1。

这样我们就完成了求解工作，在第一次求解得出结论后，我们画了一个路线图，发现有几个两点循环，没有形成一条大通路，于是我们重新加入了两点循环约束，进行二次求解；在第二次求解完成后，我们又重新画了路线图，结果发现有四点循环于是我们又加入四点循环约束，进行第三次求解，在得到第三次求解的结果后，我们又画出了路线图，这次刚好形成了一个完整的通路，保证了邮递员每点都走到且行走的路线最合理。

完整的算法流程如下：
1如果G的基图连通且所有顶点的入、出度均不为0，转2，否则返回无解并结束；
2计算所有顶点v的d’(v)值；
3构造网络N；
4在网络N中求最小费用最大流；
5对N中每一条流量f(u,v)的边(u,v)，在图G中增加f(u,v)次得到G’；
6在G’中求欧拉回路，即为所求的最优路线。
NPC问题：
if(in[i] +1 == out[i]) ...{
spos = i;
break;
}
}
}
else ...{
for(i=0;i<30;i++) ...{
if(f[i] != -1) ...{
spos = i;
break;
}
}
}
for(i=0;i<30;i++) sort(words[i].begin(), words[i].end());
如果部分街道能够双向通行，部分街道只能单向通行。这个问题已被证明是NPC的。[5]
--------------------------------------------------------------------------------
[1]大城市邮政投递问题及其算法研讨
[2]忽略有向图所有边的方向，得到的无向图称为该有向图的基图。
step = 0;
memset(vis, 0, sizeof(vis));
find_euler(spos);
//memset(vis, 0, sizeof(vis));
for(i=step-1;i>0;i--) ...{
spos = seq[i];
string snext;

中国邮路问题及解决方案中国邮递员问题一个邮递员送信，要走完他负责投递的全部街道（所有街道都是双向通行的且每条街道可以经过不止一次），完成任务后回到邮局，应按怎样的路线走，他所走的路程才会最短呢？解决方案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中，加入S3) 对S 中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi 的距离值缩短，则修改此距离值；重复上述步骤2、3，直到S 中包含所有顶点，即W=Vi为2.2 图的连通性测试检测用户输入的图是否是连通图，不是的话没办法求解，提醒用户重新输入。

管梅谷
管梅谷教授。 上海市人。1957年毕业于华 东师范大学数学系。历任 山东师范大学讲师、副教 授、教授、校长，中国运 筹学会第一、二届常务理 事，山东省数学学会第四 届副理事长，山东省运筹 学会第一届副理事长，山 东省世界语协会理事长。 是第六届全国政协委员。 从事运筹学及其应用的研 究，对最短投递路线问题 的研究取得成果。所提模 型在国外称为中国投递问 题。
求解。
推广的中国邮递员问题： 混合图的中国邮递员问题，有各种限制 的中国邮递员问题，动态网络的中国邮 递员问题。 其他相关问题-旅行售货员（TSP）问题， 灾清巡视路线。

谢谢!
v1 2 5 v2 5 9 v3 v4 图2 3 v8
4
3
v7
6
v9 4 4 4
v6
4
v5

这样就得到初始方案.在这个图中，没有奇点， 故称它为欧拉图。对应于这个可行方案，重复 边总权为51。
思考



这样的可行方案是不是只有一种呢？ 在确定一个可行方案后，怎么判断这个方案是 否为最优方案？ 若不是最优方案，如何调整这个方案？

欧拉图及求欧拉回路的算法
欧拉行迹—含所有边恰好一次的行迹 欧拉回路—含所有边恰好一次的回路 欧拉图—存在欧拉回路的图

设G是连通图, 下列命题等价: (1) G是欧拉图. (2) 每个顶点的度数都是偶数. (3) G是两两无公共边的圈的并.
欧拉图及求欧拉回路的算法
求欧拉回路的算法(Fleury算法，1921年) 算法思想: “过河拆桥,尽量不走独木桥”. 即若已选定迹 Wi v0e1v1e2 eivi , 从 G Wi 中选 取下一条边 ei 1 使得ei 1 与 vi 相关联, 且ei 1 不是 G Wi 的桥, 除非无边可选.

● 管梅谷首先提出的方法是奇偶点图上作业法（1962 年） ● Edmonds，Johnson（1973 年）给出有效算法。
Edmonds-Johnson 算法
有奇点的中国邮路问题，这种情形下，有的边要通过至少两次。下图中，边旁写的是权。
图3
（1）在图 3 中，奇点集合为
V 0={v1 , v2 , v3, v4}
(5,6)，(9,7)。
邮递员问题
一位邮递员从邮局选好邮件去投递，然后返回邮局，他必须经过由他负责投递的每条街 道至少一次，为这位邮递员设计一条投递线路，使其耗时最少。
用图的语言来描述，就是给定一个连通图 G，在每条边 e 上有一个非负的权 w(e)，要寻 求一个回路 W，经过 G 的每条边至少一次，并且回路 W 的总权数最小。
图论中的图是由点和点与点之间的线所组成的。 通常，我们把点与点之间不带箭头的线叫做边，带箭头的线叫做弧。
如果边 [ vi, v j]∈ E ，E 是边集合，那么称 vi, vj 是边的端点，或者称 vi, vj 是相邻的。 如果一个图 G 中，一条边的两个端点是相同的，那么称为这条边是环。 如果两个端点之间有两条以上的边，那么称为它们为多重边。 一个无环，无多重边的图标为简单图。 一个无环，有多重边的图标图称为多重图。
∑ w(e )=min
e∈W
如果 G 是欧拉图，则所求的 W 就是一条欧拉回路。 由于这个问题是我国菅梅谷同志于 1962 年首先提出来的，因此国际上长称它为中国邮递 员问题。
求无奇点连通图的中国邮递员问题的算法(Fleury 算法)
就是求欧拉回路。算法思想：“过河拆桥，尽量不走独木桥”。 例如，下图是欧拉图，设从 v1 开始，寻找一条欧拉回路，如果开始三步是 v1v3v2v1，那 么就失败了，因为回到 v1 之后发现左侧的 v3 上的边还没有用过，而 v1 的关联边已全用过， 不能从 v1 再去通过左侧那些未用过的边了（注意每边只能用一次）。

中国邮递员问题解法中国邮递员问题是一个著名的组合优化问题，实际上是一个旅行商问题（Traveling Salesman Problem，TSP）的变种。

问题描述：给定一个城市集合和城市之间的距离矩阵，求解一个最短的邮递员路径，使邮递员能够从出发城市出发，经过每个城市恰好一次，最后回到出发城市。

解法：1.暴力搜索暴力搜索是最简单直观的解法。

遍历所有可能的路径，计算每个路径的总距离，最后选择最短的路径。

这种解法的时间复杂度为O(n!)，随着城市数量的增加而急剧增加，效率非常低，只适用于小规模问题。

2.动态规划动态规划是一个更高效的解法。

使用一个二维数组dp[i][j]表示从城市i出发经过城市集合j的最短路径长度，其中j是一个二进制数，表示哪些城市已经访问过。

动态规划的转移方程为：dp[i][j] = min{dp[k][j XOR (1 << k)] + distance[i][k]}，其中k表示已经访问的最后一个城市。

利用这个递推关系，可以逐步计算出dp[0][1<<n-1]，即从城市0出发经过所有城市的最短路径。

最后，将此路径与每个城市的距离相加，得到最终的最短路径长度。

3.贪心算法贪心算法是一种更简单的解法。

首先选择一个起始城市，然后每次选择距离最近且未被访问过的城市，将其加入路径中。

重复此过程，直到访问完所有城市，然后回到起始城市。

这种解法的时间复杂度为O(n^2)，但由于贪心策略的局限性（可能会出现回头或死胡同），所以得到的解并不一定是最优解。

以上是三种常用的解决中国邮递员问题的方法，具体可以根据实际情况选择合适的算法进行求解。

6
5
3 4
v5 4
v9
3 v8 4
v1
9
v4
4
v7
v3 5 v2 5
v1
2
v6 4
3
6
4
v5
4
v9
3 v8
4
9
v4
4
v7
运筹学
判定标准1: 在最优邮递路线上，图中的每一条 边至多有一条重复边。
判定标准2 : 在最优邮递路线上，图中每一个 圈的重复边总权小于或等于该圈总权的一半。
例8.12 求解下图所示网络的中国邮路问题，图中数 字为该边的长。
v3 2 v6 4 v9
5
3
v2
6 v5
5
4
3
4
v8
4
v1
9
v4
4
v7
v3 2 v6 4 v9
A
C
D
B
二、 奇偶点图上作业法 （1）找出图G中的所有的奇顶点，把它们两两配 成对，而每对奇点之间必有一条通路，把这条通路 上的所有边作为重复边追加到图中去，这样得到的 新连通图必无奇点。 （2）如果边e=（u,v）上的重复边多于一条，则 可从重复边中去掉偶数条，使得其重复边至多为一 条，图中的顶点仍全部都是偶顶点。 （3）检查图中的每一个圈，如果每一个圈的重 复边的总长不大于该圈总长的一半，则已经求得最 优方案。如果存在一个圈，重复边的总长大于该圈 总长的一半时，则将这个圈中的重复边去掉，再将 该圈中原来没有重复边的各边加上重复边，其它各 圈的边不变，返回步骤（2）。
运筹学
中国邮递员问题
一、 欧拉回路与道路 定义8.18 连通图G中，若存在一条道路，经过每 边一次且仅一次，则称这条路为欧拉道路。若存 在一条回路，经过每边一次且仅一次，则称这条 回路为欧拉回路。 具有欧拉回路的图称为欧拉图。 定理8.7 一个多重连通图G是欧拉图的充分必要 条件是G中无奇点。 推论 一个多重连通图G有欧拉道路的充分必要 条件是G有且仅有两个奇点。

从一点到任意点的最短路
• 木器厂有六个车间，办事员经常 要到各个车间了解生产进度。从 办公室到各车间的路线由图1给出。
找出点1（办公室）到其它各点 （车间）的最短路
11
27
2
2
1 5 3 5 55 7
3
1
4
3
1
6
7
5
12
2
权wij(dij)
2
距离、价格 2
15
3
点（vi）
边eij或记为（vi，vj） 13
3
5
3
3 0 v1
v2
3
v6
2.5
2
53
1
2
v3
4 3
4
v7 2
v4
v9
4 v8
41
v5
3
5
3
3 0 v1
v2
3
v6
2.5
2
53
1
2
v3
4 3
4
v7 2
v4
v9
4 v8
42
6 v5
3
5
3
v2
3
6
3
v6
2.5
0
v1
2
53
1
2
v3
4 3
4
v7 2
v4
v9
4 v8
43
6 v5
3
5
3
v2
3
6
3
v6
2.5
最短路问题不仅可以求解交通图中两点之间的最短距离，实际 中很多问题也可变为最短路问题加以求解。例如设备更新问题，厂 区合理布局问题等。兹举一例：
例1（设备更新问题）某企业使用一台设备，在每年年底，企业 都要决策下年度是购买一台新设备呢？还是继续使用这台设备。若 购买新的，就要支付一笔购置费；如果使用旧设备，只要支付维修 费，而维修费随着设备的使用年限延长而增加。现根据以往统计资 料已经估算出设备在各年初的价格和不同使用年限的修理费用，分 别如表1、表2所示。

G-E（C）仍然无奇数度结点。
?
由于G是连通的，C中应至少存在一点v，使G-
E（C）中有一条包含v的回路C′。（见示意图）
2019/7/8

计算机学院
7
C
v
C'
这样，就可以构造出一条由C和C′组成的 G的回路，其包含的边数比C多，与假设矛盾。 因此，C必是Euler回路，结论成立。
2019/7/8
计算机学院
类似于无向图的讨论，对有向图我们有以下 结论： 定理13-1.2 ⅰ）有向连通图G含有有向欧拉道路，当且仅当
除了两个结点以外，其余结点的入度等于出度， 而这两个例外的结点中，一个结点的入度比出 度大1，另一个结点的出度比入度大1。 ⅱ）有向连通图G含有有向欧拉回路，当且仅当G 中的所有结点的入度等于出度。
计算机学院
16
显然，当这个图是欧拉图时，任何一条欧拉回路都 符合要求；当这个图不是欧拉图时，所求回路必然要重复 通过某些边。
对此，管梅谷曾证明，若图的边数为m，则所求回 路的长度最小是m，最多不超过2m，并且每条边在其中 最多出现两次。中国邮递员问题，一般为在带权连通图 中找一条包括全部边的且权最小的关回键路是。：复制哪些边？
V6
d(V2,V5)=3， d(V3,V5)=4
G
各路径:V1V2(3),V3V5(4)—7
V1V3(5),V2V5(3)—8
V1
V1V5(4),V2V3(2)—6
∴两条长度最短P1=V1V7V5,P2=V2V3
3．构造G’的任一E图就是中国邮递员 V6
问题的解。
G′
V2
3
2
1 3
3 6
V3
3
V7
7

中国邮递员问题引言H T T P ://W W W .588K U .C O M /P P Tu 中国邮递员问题是由山东师范大学管梅谷同志1960年首先提出的。

u 该问题涉及著名的的哥尼斯堡(Königsberg)七桥问题。

u 这是数学中为数不多的几个以“中国”命名的问题或定理之一。

u 七桥问题是图论和拓扑学的起源。

引言1哥尼斯堡七桥问题2欧拉图及判定定理3Fleury算法4中国邮递员问题5奇偶点图上作业法6理论根据（选讲）哥尼斯堡(Königsberg)今称加里宁格勒，建城于1255年，是位于波罗的海海岸的俄罗斯海港城市与加里宁格勒州的首府。

加里宁格勒州位于波兰北方、立陶宛西南，原为德国东普鲁士一部分，现为俄罗斯的外飞地。

图1 加里宁格勒图2 哥尼斯堡七桥示意图有一条普雷格尔(Pregel)河流经哥尼斯堡，河上有七个桥。

一个散步者能否从某处出发走遍七个桥且每个桥只走一次，最后回到出发点？哥尼斯堡七桥问题大数学家欧拉在1736年解决了这个问题。

欧拉Euler(1707-1783)莱昂哈德·欧拉（Leonhard Euler，1707年4月15日－1783年9月18日）u瑞士数学家和物理学家，近代数学先驱之一。

u欧拉是18世纪数学界最杰出的人物之一。

u欧拉是科学史上最多产的一位杰出的数学家，据统计他那不倦的一生，共写下了886本书籍和论文。

u30岁左右右眼几乎完全失明，60岁左右左眼又几乎完全失明。

u在1775年，他平均每周就完成一篇数学论文。

u1783年9月18日于俄国彼得堡去逝。

n 将上图中A，B，C和D这四个区域各看成一个顶点，两区域之间有一个桥相连，就将相应的两个顶点连一条边，得到一个图。

AB CD图3 七桥问题对应图欧拉Euler(1707-1783)的走法为一个欧拉通路。

n如果进一步该走法还回到出发点，则称之为欧拉环游（回路）。

n具有欧拉环游的图称之为欧拉图。

中国邮递员问题的求解实例前面已经讲过，对于欧拉图，可以直接用Fleury算法找出一条欧拉巡回路线；对于半欧拉图，可以先求出奇点u和v之间的最短路径P,令G =G P，贝U G *为欧拉图，然后用Fleury算法来确定一个G *的欧拉巡回，它就是G的最优巡回。

当G有2n个奇点(n>1),可以用Edmonds算法解决，步骤如下：(1) 用Floyd算法求出所有奇点之间的最短路径和距离矩阵。

(2) 用匈牙利法或0-1规划法求出所有奇点之间的最佳配对。

(3) 在原图上添加最佳配对所包含的两两顶点之间的最短路得到欧拉图G *。

⑷用Fleury算法确定一个G *的欧拉巡回，这就是G的最优巡回。

以上步骤的关键是找出2n个奇点的最佳配对，举例如下。

例图3是某区街道示意图，各边的长度数据如下表所示。

现在需要对每条街道找最优巡回，需要先求26个奇点的最佳配对。

先用Floyd算法求出所有42个顶点之间的最短路距离和路径。

程序如下：E=[1 2 10261 4 402........ 注：每一行代表一条边(两个顶点和边长)，此处省略59行40 39 198];for i=1:42for j=1:42if j==ia(i,j)=0; elsea(i,j)=inf; end end endfor k=1:62 i=E(k,1);j=E(k,2);a(i,j)=E(k,3);a(j,i)=E(k,3); end[D,R]=floyd(a);图3某区街道示意图然后求26个奇点的最优配对，这可以用Lin go 求解，编写程序如下:MODEL: SETS:4U12°26"30 O3539 40413*27 21 4128* 3338仆2934O114251015• 1724，25201922 23 32313637dot/2,4,5,6,8,9,10,11,12,13,14,15,17,18,19,20,22,24,25,26,28,29,30,36,40,41/;LINKS(dot,dot)| &2 # GT # & 1:C,X;ENDSETSDATA:C=1319 1065 651 650 939 1228 1463 1500 1213 617 895 1590 1709 1377 1033 1112 1652 1761 1853 1418 1832 2124 2151 2479 1687254 668 1173 1462 1751 198 181 402 1140 1418 2113 453 601 945 1635 2175 2284 597 1941 2355 868 1463 1498 2104414 919 1208 1497 1732 435 148 886 1164 1859 679 347 691 1381 1921 2030 823 1687 2101 1094 1689 1724 1850505 794 1083 1318 849 562 472 750 1445 1058 726 382 967 1507 1616 1202 1273 1687 1473 2005 2103 1541289 578 813 1354 1067 471 245 940 1563 1231 887 462 1002 1111 1707 768 1182 1978 2005 2333 1541 289 524 1643 1356 760 534 651 1852 1520 1176 504 828 886 1996 594 1008 2267 2197 2525 1733235 1932 1645 1049 823 362 2141 1809 1465 793 706 597 2285 883 890 2556 2486 2814 20222167 1880 1284 1058 163 2376 2044 1700 1028 507 398 2520 1105 691 2766 2658 2986 2194306 1321 1599 2294 272 505 849 1571 2111 2220 416 1877 2291 687 1282 1317 20081034 1312 2007 531 199 543 1265 1805 1914 675 1571 1985 946 1541 1576 1702360 1411 1203 871 527 577 1117 1226 1347 883 1297 1618 1534 1862 10701101 1563 1231 887 217 757 866 1707 523 937 1978 1894 2222 14302282 1950 1606 884 344 235 2426 942 528 2603 2495 2823 2031332 676 1398 1938 2047 144 1704 2118 415 1010 1045 1824344 1066 1606 1715 476 1372 1786 747 1342 1377 1503722 1262 1371 820 1028 1442 1091 1623 1721 1159540 649 1542 306 720 1813 1729 2057 1265109 2082 598 184 **** **** 2479 16872191 707 293 2368 2260 2588 17961848 2262 271 866 901 1680414 1711 1603 1931 11392075 1967 2295 1503595 630 1409360 832792;ENDDATA图4 26个奇点的最优配对MIN=@SUM(LINKS:C *X);@FOR(LINKS:@BIN(X));@FOR(dot(l):@SUM(LINKS(J,K)| J #EQ# I #OR# K #EQ# I:X(J,K))=1);END运行以上程序，得到最优配对结果为：2与6、4与12、5与13、8与9、10与11、14 与15、17 与25、18 与26、19 与20、22 与28、24 与29、30 与36、40 与41。

•
新的T（vj）=min{老的T（vj），p（vi）+ ωij }
• 若T（vj）= p（vi）+ ωij ，则记k（vj ）=vi（前点标记）;
• 3°找出具有最小T标号的点，将其标号改为p标号。若vt 已获得p
标号，则已找到最短路，由k（vt）反向追踪，就可找出vs 到vt 的最
短路径，p（vt）就是vs 到vt 的最短距离。否则，转2°。
p（v2）
=3 3
p（v1） v1
p（v=30）
=4
6
v2
51 1
v4
7 4
v5
v3 3 2
5
v7
26 v6 9 15
v8
T（v4）=min{6,4+1}=5, k（v4 ）=v3
T（v6）=min{7,4+2}=6, k（v6 ）=v3
目前，点v4 具有最小T标号，将其标号改为p标号： p（v4）=5；
向继续前进，则最先到达终点vt 的流所走过的路径一定是最短的。
为了实现这一想法，对假想流依次到达的点，依次给予p标号，表
示vs到这些点的最短距离。对于假想流尚未到达的点给予T标号，
表示vs到这些点的最短距离的估计值。具体作法如下：
• 1°标p（vs）=0，其余点标T（vi）=+∞;
• 2°由刚刚获得p标号的vi 点出发，改善它的相邻点vj 的T标号,即
对于点v2 ：d（v2）=min｛16+31,22+23,30+18,41｝=41， v对2→于v点6 v；1 ：d（v1）=min｛16+41,22+31,30+23,41+18,59｝
试确定一个五年内的设备更新计划，使五年内总支出最小。

的最优环游。下左图的最优环游即为右图。
3
1
5
2
1
3
2
6
2
3
3
1
5
2
1
3
2
6
2
3
-
思考：如何求恰好有 2k(k个0奇) 点的赋权图的最优环游？
-
(2)去掉 G 中关于G 的某一对相邻顶点有多于2条边连接它们，则去掉其
中的偶数条边，留下1条或2条边连接这两个顶点。直到每一对相邻顶点 至多由2条边连接。
(3)检查G 的每一个回路，如果某个回路 C 上多重边 e的权和超过此回路 权和的一半，则将 C 进行调整：删除 e， Ce 的边重数增加 1。
4.2、中国邮路问题
1、提出问题
邮递员的工作是每天在邮局里选出邮件，然后送到他所管
辖的客户中，再返回邮局。自然地，若他要完成当天的投递任
务，则他必须要走过他所投递邮件的每一条街道至少一次。问
怎样的走法使他的投递总行程为最短？这个问题就称为中国邮
路问题。
R13 13
房屋 12
R14
房屋 11
R15
R9 房屋 10
图 G 的环游；
-
返回 结束
定理4.2.1（管梅谷，1960）设 G是一个连通的赋权图，G 是G的
一个Euler赋权生成母图，则
w (e ) m in w (e )|G * 是 G 的E 一 u 赋 l个 eபைடு நூலகம் r生
e E (G ) E (G )
e E (G * E )(G )
当且仅当 G 没有重复数大于2的边。并且 G的每一个长度至少
权图G中找一条最优环游。
-
街道结构图
R13 13