《中国邮递员问题算法.ppt》由会员分享，可在线阅读，更多相关《中国邮递员问题算法.ppt（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、冯伟森冯伟森Email：07 三月三月 20232023/3/72023/3/7计算机学院计算机学院2 2主要内容主要内容 Euler Euler图及其应用图及其应用欧拉道路（回路）的欧拉道路（回路）的定义定义如何判别欧拉图如何判别欧拉图一个图含有一个图含有欧拉道路的条件欧拉道路的条件连连通通有有向向图图G G中中含含有有有有向向欧欧拉拉道道路路和和回回路路的的充充要条件要条件 FleuryFleury算法算法EulerEuler图的应用图的应用(中国邮递员问题算法中国邮递员问题算法)2023/3/72023/3/7计算机学院计算机学院3 3哥尼斯堡七桥问题哥尼斯堡七桥问题 哥哥尼尼斯斯堡堡城
2、城市市有有一一条条横横贯贯全全城城的的普普雷雷格格尔尔(Pregel)(Pregel)河河，城城的的各各部部分分用用七七座座桥桥联联接接，每每逢逢假假日日，城城中中居居民民进进行行环环城城逛逛游游，这这样样就就产产生生了了一一个个问问题题：能能不不能能设设计计一一次次“遍遍游游”，使使得得从从某某地地出出发发对对每每座座跨跨河河桥桥只只走走一一次次，而而在遍历了七桥之后却又能回到原地？在遍历了七桥之后却又能回到原地？A Ab b2 2B BD DC Cb b4 4b b1 1b b3 3b b5 5b b7 7b b6 62023/3/72023/3/7计算机学院计算机学院4 4EulerEu
3、ler图图定义定义13-1.113-1.1设设G G是一个无孤立结点的图，包含是一个无孤立结点的图，包含G G的每条边的的每条边的简单道路简单道路（回路回路）称为该图的一条）称为该图的一条欧拉道路欧拉道路（回路回路）。具有欧拉回路的图称为）。具有欧拉回路的图称为欧欧拉图拉图。规定规定平凡图为欧拉图平凡图为欧拉图。显然，每个显然，每个欧拉图欧拉图必然是连通图。必然是连通图。因此，一条因此，一条欧拉道路欧拉道路（回路回路）是经过图中）是经过图中每每边一次且仅一次边一次且仅一次的道路（的道路（回路回路）。）。为什么？为什么？2023/3/72023/3/7计算机学院计算机学院5 5例例13-1.11
4、3-1.1v v5 5v v1 1v v2 2v v3 3v v4 4a a)v v5 5v v1 1v v2 2v v3 3v v4 4b b)v v4 4v v1 1v v2 2v v3 3c c)图图a a是是欧欧拉拉图图；图图b b不不是是欧欧拉拉图图，但但存存在在欧欧拉拉道道路；图路；图c c不存在欧拉道路。不存在欧拉道路。2023/3/72023/3/7计算机学院计算机学院6 6定定理理13-1.113-1.1 无无向向连连通通图图G GVE是是欧欧拉拉图图当当且仅当且仅当G G的的所有结点的度数都为偶数所有结点的度数都为偶数。证明：证明：“”设设G G是是EulerEuler图，
5、则图，则G G必然存在一条包含所有边必然存在一条包含所有边（也包含所有结点）的回路（也包含所有结点）的回路C C，对，对 u u V V，u u必然在必然在C C中出现一次（可出现多次），中出现一次（可出现多次），每出现每出现u u一次，都一次，都关联着关联着G G中的两条边，而当中的两条边，而当u u又重复出现时，它又又重复出现时，它又关联着关联着G G中的另外的两条边，（中的另外的两条边，（为什么？为什么？）因而因而u u每出现一次，都将使得结点每出现一次，都将使得结点u u的度数增的度数增加加2 2度，若度，若u u在通路中重复出现在通路中重复出现j j次，则次，则deg(u)deg(u
6、)2j2j。即即u u的度数必为偶数的度数必为偶数。由于在回路由于在回路C中边不可能重中边不可能重复出现复出现2023/3/72023/3/7计算机学院计算机学院7 7“”设设连连通通图图G G的的结结点点的的度度数数都都是是偶偶数数，则则G G必必含含有有简简单单回回路路（可可对对结结点点个个数数进进行行归归纳纳证证明明）。设设C C是一条包含是一条包含G G中边最多的简单回路：中边最多的简单回路：若若C C已已经经包包含含G G中中所所有有的的边边，则则C C就就是是EulerEuler回回路，结论成立。路，结论成立。若若C C不能包含不能包含G G中所有的边，则删边子图中所有的边，则删边
7、子图 G-EG-E（C C）仍然无奇数度结点。）仍然无奇数度结点。由于由于G G是连通的，是连通的，C C中应至少存在一点中应至少存在一点v v，使，使G-G-E E（C C）中有一条包含）中有一条包含v v的回路的回路CC。（见示意图）（见示意图）Why?2023/3/72023/3/7计算机学院计算机学院8 8 这样，就可以构造出一条由这样，就可以构造出一条由C C和和CC组成的组成的G G的回路，其包含的边数比的回路，其包含的边数比C C多，与多，与假设矛盾假设矛盾。因此，因此，C C必是必是EulerEuler回路，结论成立。回路，结论成立。2023/3/72023/3/7计算机学院计
8、算机学院9 9证证明明：“”设设G G具具有有一一条条EulerEuler道道路路L L，则则在在L L中中除除起起点点和和终终点点外外，其其余余每每个个结结点点都都与与偶偶数数条条边边相相关关联联，所所以，以，G G中中仅有零个（仅有零个（EulerEuler回路回路）或者或者两个两个奇数度结点奇数度结点。“”若若 G G没有奇度数结点，则结论显然成立；没有奇度数结点，则结论显然成立；若若G G有有两两个个奇奇度度数数结结点点u u和和v v，则则G+uvG+uv是是EulerEuler图图，从从而而存存在在EulerEuler回回路路C C。从从C C中中去去掉掉边边uvuv，则则得得到到
9、一一条条简简单单道道路路L L（起起点点u u和和终终点点v v），且且包包含含了了G G的的全全部部边边，即即L L是是一一条条EulerEuler道路。道路。推推论论13-1.1.113-1.1.1非非平平凡凡连连通通图图G GVE含含有有欧欧拉拉道道路当且仅当路当且仅当G G仅有零个或者仅有零个或者两个奇数度结点。两个奇数度结点。注意：注意：若有两个奇若有两个奇度数结点，则它们度数结点，则它们是是G G中每条欧拉通路中每条欧拉通路的端点。的端点。2023/3/72023/3/7计算机学院计算机学院1010例例13-1.213-1.2由由定理定理13-1.113-1.1及及推论推论13-1
10、.1.113-1.1.1容易看出：容易看出：a)a)是欧拉图；是欧拉图；b)b)不是欧拉图，但存在欧拉道路；不是欧拉图，但存在欧拉道路；c)c)既不是欧拉图，也不存在欧拉道路。既不是欧拉图，也不存在欧拉道路。V V2 2V V1 1V V5 5V V3 3V V4 4(a)(a)V V2 2V V1 1V V5 5V V3 3V V4 4(b)(b)V V1 1V V4 4V V2 2V V3 3(c)(c)现在，我们是现在，我们是不是已经解决不是已经解决了哥尼斯堡七了哥尼斯堡七桥问题？桥问题？2023/3/72023/3/7计算机学院计算机学院1111有向图的欧拉道路、欧拉图有向图的欧拉道路
11、、欧拉图定理定理13-1.213-1.2）有有向向连连通通图图G G含含有有有有向向欧欧拉拉道道路路，当当且且仅仅当当除除了了两两个个结结点点以以外外，其其余余结结点点的的入入度度等等于于出出度度，而而这这两两个个例例外外的的结结点点中中，一一个个结结点点的的入入度度比比出出度大度大1 1，另一个结点的出度比入度大，另一个结点的出度比入度大1 1。）有有向向连连通通图图G G含含有有有有向向欧欧拉拉回回路路，当当且且仅仅当当G G中的中的所有结点的入度等于出度所有结点的入度等于出度。类似于无向图的讨论，对有向图我们有以下类似于无向图的讨论，对有向图我们有以下结论：结论：同样，同样，有向有向Eu
12、lerEuler图的图的结点度数都为偶数；含有有结点度数都为偶数；含有有向向EulerEuler道路的图道路的图仅有零个或者仅有零个或者两个奇度数结点。两个奇度数结点。2023/3/72023/3/7计算机学院计算机学院1212例例13-1.313-1.3V V1 1V V2 2V V3 3V V4 4V V1 1V V2 2V V3 3V V4 4V V8 8V V2 2V V4 4V V6 6V V1 1V V3 3V V5 5V V7 7图图a)a)存在一条的欧拉道路：存在一条的欧拉道路：v v3 3v v1 1v v2 2v v3 3v v4 4v v1 1；(a)(a)(b)(b)(
13、c)(c)图图(b)(b)中中存存在在欧欧拉拉回回路路v v1 1v v2 2v v3 3v v4 4v v1 1v v3 3v v1 1，因因而而(b)(b)是欧拉图；是欧拉图；图图(c)(c)中中有有欧欧拉拉回回路路v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7v v8 8v v2 2v v4 4v v6 6v v8 8v v1 1因而因而(c)(c)是欧拉图。是欧拉图。2023/3/72023/3/7计算机学院计算机学院1313例例13-1.413-1.4解解在在图图中中，仅仅有有两两个个度度数数为为奇奇数数的的结结点点b b，c c，因因而而存存在
14、在从从b b到到c c的的欧欧拉拉通通路路，蚂蚂蚁蚁乙乙走走到到c c只只要要走走一一条条欧欧拉拉通通路路，边边数数为为9 9条条。而而蚂蚂蚁蚁甲甲要要想想走走完完所所有有的的边边到到达达c c，至至少少要要先先走走一一条条边边到到达达b b，再再走走一一条条欧欧拉拉通通路路，因因而而它它至至少少要要走走1010条边才能到达条边才能到达c c，所以乙必胜。，所以乙必胜。甲、乙两只蚂蚁分别位于右图甲、乙两只蚂蚁分别位于右图中中的的结结点点a a，b b处处，并并设设图图中中的的边边长长度度是是相相等等的的。甲甲、乙乙进进行行比比赛赛：从从它它们们所所在在的的结结点点出出发发，走走过过图图中中的的
15、所所有有边边最最后后到到达达结结点点c c处处。如如果果它它们们的速度相同，问谁先到达目的地？的速度相同，问谁先到达目的地？c cb(b(乙乙)a(a(甲甲)2023/3/72023/3/7计算机学院计算机学院1414FleuryFleury算法算法（构造（构造EulerEuler回路）回路）1.1.任取任取v v0 0VV，令，令P P0 0v v0 0；2.2.设设P P0 0v v0 0e e1 1v v1 1e e2 2e ei iv vi i，按下面的方法从，按下面的方法从 G GK K=E-e=E-e1 1,e,e2 2,e,ei i 中选取中选取e ei+1i+1：1)1)e e
16、i+1i+1与与v vi i相关联相关联；2)2)除非无别的边可选取除非无别的边可选取，否则，否则e ei+1i+1不应该为不应该为 G Gk kG-eG-e1 1,e,e2 2,e,ei i 中的中的桥桥；3.3.当当G Gk k为零图时，算法结束；否则，返回为零图时，算法结束；否则，返回2 2。设设G GVE是一个是一个欧拉图欧拉图即如果即如果e ei+1i+1是割是割边，同时还有其边，同时还有其它边与它边与v vi i相关联，相关联，则不能选则不能选e ei+1i+12023/3/72023/3/7计算机学院计算机学院1515例例13-1.513-1.5v v4 4v v5 5v v6
17、6e e4 4e e5 5e e6 6e e1010e e9 9e e8 8e e3 3在右图所示的欧拉图中，某在右图所示的欧拉图中，某人用算法求中的欧拉回路时，人用算法求中的欧拉回路时，走了简单的回路：走了简单的回路：v v2 2e e2 2v v3 3e e3 3v v4 4e e1414v v9 9e e1010v v2 2e e1 1v v1 1e e8 8v v8 8e e9 9v v2 2之后，无法行遍了，试分析在哪之后，无法行遍了，试分析在哪步他犯了错误？步他犯了错误？v v1 1v v3 3v v7 7e e1 1e e2 2e e7 7v ve e1 1e e1 1e e1
18、1e e1 1v v2 2v v4 4v v5 5v v6 6e e4 4e e5 5e e6 6e e1010e e9 9e e8 8e e3 3v v1 1v v3 3v v7 7e e1 1e e2 2e e7 7v ve e1 1e e1 1e e1 1e e1 1v v2 2此人行遍此人行遍v v8 8时犯了能不走桥就不走桥的错时犯了能不走桥就不走桥的错误，因而未能行遍出欧拉回路。当他走到误，因而未能行遍出欧拉回路。当他走到v v8 8时，时，e e2 2，e e3 3，e e1414，e e1010，e e1 1，e e8 8,见右图，此时，见右图，此时，e e9 9为该图中的桥为
19、该图中的桥，而，而e e7 7、e e1111均不是桥。因此，他不该走均不是桥。因此，他不该走e e9 9，而应该，而应该走走e e7 7或或e e1111。但在行遍。但在行遍v v3 3和和v v1 1时，也遇到桥，时，也遇到桥，为什么没有问题呢？为什么没有问题呢？v v9 9v v9 92023/3/72023/3/7计算机学院计算机学院1616中国邮递员问题中国邮递员问题 山山东东师师范范大大学学，管管梅梅谷谷先先生生19621962提提出出并并解解决决。（参参考考文文献献：19621962（数数学学通通报报）81.10,P81.10,P3232,81.5,81.5）一一个个邮邮递递员员
20、从从邮邮局局出出发发，在在其其分分管管的的投投递递区区域域内内走走遍遍所所有有的的街街道道把把邮邮件件送送到到每每个个收收件件人人手手中中，最最后后又又回到邮局，要走怎样的线路使全程最短。回到邮局，要走怎样的线路使全程最短。这个问题用图来表示：街道为图这个问题用图来表示：街道为图的边，街道交叉口为图的结点，的边，街道交叉口为图的结点，问题就是要从这样一个图中找出问题就是要从这样一个图中找出一条一条至少包含每条边一次的总长至少包含每条边一次的总长最短的回路最短的回路。2023/3/72023/3/7计算机学院计算机学院1717 对此，管梅谷曾证明，对此，管梅谷曾证明，若图的边数为若图的边数为m
21、m，则所求回，则所求回路的长度最小是路的长度最小是m m，最多不超过，最多不超过2m2m，并且每条边在其中最，并且每条边在其中最多出现两次多出现两次。中国邮递员问题，一般为在带权连通图中。中国邮递员问题，一般为在带权连通图中找一条包括全部边的且权最小的回路。找一条包括全部边的且权最小的回路。这个问题有着有效的解决办法，其中最直观的方法这个问题有着有效的解决办法，其中最直观的方法之一是之一是:把图中的某些边复制成两条边，然后在所求图把图中的某些边复制成两条边，然后在所求图中找一条欧拉回路。中找一条欧拉回路。中国邮递员问题是运筹学中一个典型的优化问题。中国邮递员问题是运筹学中一个典型的优化问题。显
22、然，当这个图是欧拉图时，任何一条欧拉回路都显然，当这个图是欧拉图时，任何一条欧拉回路都符合要求；当这个图不是欧拉图时，所求回路必然要重复符合要求；当这个图不是欧拉图时，所求回路必然要重复通过某些边。通过某些边。关键是：复制哪些边？关键是：复制哪些边？2023/3/72023/3/7计算机学院计算机学院1818算法算法（1 1）若若G G不不含含奇奇数数度度结结点点，则则任任一一欧欧拉拉回回路路就就是是问问题题的的解决。解决。（2 2）若若G G含含有有2K(K0)2K(K0)个个奇奇数数度度结结点点，则则先先求求出出其其中中任任何何两两点点间间的的最最短短路路径径，然然后后再再在在这这些些路路
23、径径之之中中找找出出K K条条路路径径P P1 1，P P2 2，P PK K，使得满足以下，使得满足以下条件条件：任何任何P Pi i和和P Pj j（ijij）没有相同的起点和终点。）没有相同的起点和终点。在所满足在所满足的的K K条最短路径的集合中，条最短路径的集合中，P P1 1，P P2 2，P PK K的长度总和最短。的长度总和最短。（3 3）根根据据（2 2）中中求求出出的的K K条条最最短短道道路路P P1 1，P P2 2，P PK K，在在原原图图G G中中复复制制所所有有出出现现的的在在这这条条道道路路上上的的边边，设设所所得得之图为之图为G G。（4 4）构造）构造G
24、G的欧拉回路，即得中国邮递员问题的解。的欧拉回路，即得中国邮递员问题的解。找出需复找出需复制的边制的边连通图中，奇数度结点的个数必为偶数个。连通图中，奇数度结点的个数必为偶数个。2023/3/72023/3/7计算机学院计算机学院1919例例13-1.613-1.61 1因为因为G G含有奇数度结点，所以含有奇数度结点，所以2 2G G中有中有2K=4(K=2)2K=4(K=2)个奇结点个奇结点V V1 1，V V2 2，V V3 3，V V5 5。这。这4 4点间的距离点间的距离 d(Vd(V1 1,V,V2 2)=3)=3，d(Vd(V1 1,V,V3 3)=5)=5，d(Vd(V1 1,
25、V,V5 5)=4)=4，d(Vd(V2 2,V,V3 3)=2)=2，d(Vd(V2 2,V,V5 5)=3)=3，d(Vd(V3 3,V,V5 5)=4)=4各路径各路径:V:V1 1V V2 2(3),V(3),V3 3V V5 5(4)(4)7 7 V V1 1V V3 3(5),V(5),V2 2V V5 5(3)(3)8 8 V V1 1V V5 5(4),V(4),V2 2V V3 3(2)(2)6 6两条长度最短两条长度最短P P1 1=V=V1 1V V7 7V V5 5,P,P2 2=V=V2 2V V3 33 3构造构造G G的任一的任一E E图就是中国邮递图就是中国邮递员问题的解。员问题的解。GG2023/3/72023/3/7计算机学院计算机学院2020习题十三习题十三1 1、2 2、4 4、5 5、7 7、8 8实验三实验三 利利用用KruskalKruskal算算法法，用用C C语语言言编编写写出出给给定定无无向向连连通通加加权权图图G G，构构造造一一棵棵最最小小生生成树的程序。成树的程序。测试数据测试数据:采用教材采用教材P P150150 的例的例11.311.3进行验证。进行验证。2023/3/72023/3/7计算机学院计算机学院2121