欧拉图和哈密顿图的判定及应用

-1-上海大学2015～2016学年冬季学期研究生课程论文课程名称：图论及其应用课程编号：01SAH9009论文题目:欧拉图和哈密顿图的判定及应用研究生姓名:孙亚南学号:15720007论文评语:成绩:任课教师:评阅日期:-2-欧拉图和哈密顿图的判定及应用孙亚南（上海大学理学院，上海200444）摘要：图论在生活中有着较为广泛的应用。本文主要介绍了欧拉图和哈密顿图的几种判定方法，解决了中国邮路问题、旅行售货员问题、排座位问题、判定图是否可一笔画问题等问题。关键词：图论；欧拉图；哈密顿图DeterminationandApplicationofEulerandHamiltonGraphSunYanan(SchoolofScience,ShanghaiUniversity,Shanghai200444,China)Abstract:Graphtheoryhasarelativelywideapplication.Inthepage,thismainlyintroducesseveraldeterminationsofEulerandHamiltongraph,andsolveChinesePostmanProblem,andTravelingSalesmanProblem,andRowofSeatsProblemandsoon.Keywords:GraphTheory;EulerGraph;HamiltonGraph1引言图论在我们的生活中起着重要的角色，在现实生活中有着较为广泛的应用。欧拉图和哈密顿图的判定方法是研究欧拉图、哈密顿图的性质，应用的基础。欧拉图和哈密顿图的判定方法有很多种，每种都给出了欧拉图、哈密顿成立的条件。通过对欧拉图、哈密顿图的多种判定，利用这种判定的性质，可以研究欧拉图、哈密顿图解决什么样的问题，怎样解决这种问题等问题。图论内容是相当现实和必须的，欧拉图和哈密顿图在现实生活中有着较为广泛的应用。2欧拉图的判定方法2.1欧拉图定义的判定方法定义：通过图G的每条边恰好一次的路成为欧拉路。通过图G的每条边恰好一次的回路称为欧拉回路。具有欧拉回路的图成为欧拉图。约定平凡图为欧拉图。为了更好的说明欧拉图，下面我们给出一个例子。-3-例1：图（1）有欧拉路但无欧拉回路，图（2）有欧拉路也有欧拉回路，图（3）既无欧拉路也无欧拉回路。（1）（2）（3）2.2欧拉图定理判定方法定理1一个连通无向图G是欧拉图的的充分必要条件是G中每个结点都是偶数度结点。证明必要性：若连通无向图G有欧拉回路，设是G的一条欧拉回路，则通过G的任意结点时必通过关联该点的两条边，而G中每条边仅出现一次，所以所通过的每个结点必为偶数度结点。充分性：若G中每个结点都是偶数度结点，因G连通，所以G中至少含有一个基本回路1G，从G中删除1G上的各边得到子图1G，若1G中仍然有边，由1G中每个结点仍为偶数度的结点，则可得到基本回路2G，且使得1G与2G有一个公共点。续行此法，直到删去G中的所有的边。于是得到一系列基本回路mGGG,,,21，且ijiG11与jG有一个公共结点，则由mGGG,,,21构成一个欧拉回路。定理2连通无向图EVG,，Vvu,且vu，vu,之间存在欧拉路的充分必要条件G中仅有vu,为奇数度结点。证明对G加上一条边],[vu得到新图1G,G中vu,之间存在欧拉路1G中有欧拉回路1G中每个结点为偶数度结点G中除vu,外其余结点均为偶数度结点G中仅有vu,为奇数度结点。定理3强连通有向图G有欧拉回路的充分必要条件是G中的每个结点的入度等于出度。这里不给出该定理的证明了，但为了更好的应用该定理，我们给出了下面的例子。例2：根据定理3，我们可以判定图4为欧拉图。（4）-4-定理4单向连通图EVG,，Vvu,且vu，vu,之间存在欧拉路的充分必要条件是G中惟有vu,的入度不等于出度，且u的出度比其入度大1，v的出度比其入度小1。3哈密顿图的判定方法3.1哈密顿图定义的判定方法定义：经过图中每个结点恰好一次的路成为哈密顿路。经过图中每个结点恰好一次的回路成为哈密顿回路。具有哈密顿回路的图成为哈密顿图。例3：图5有哈密顿路但无哈密顿回路，图6既有哈密顿路又有哈密顿回路，图7既无哈密顿路也无哈密顿回路。（5）（6）（7）3.2哈密顿定理的判定方法判断一个图是哈密顿图不是一件容易的事情，至今还没有找到判定一个图还哈密顿图的“平凡的”重要条件，只能给出若干个必要条件或是充分条件。定理5若连通图EVG,是哈密顿图，S是V的任意真子集，则SSG)(。证明：若连通图EVG,是哈密顿图，设C是G的哈密顿回路，则SC是SG的生成子图，所以)()(SCSG。易知当S中的结点互不邻接时，SC的连通分支数达到最大值S，所以有SSG)(。故SSG)(。推论若连通图EVG,存在哈密顿路，S是V的任意真子集，则1)(SSG。该定理是判定哈密顿图的必要条件，用它可以证明某些图不是哈密顿图。如下图8和图9：（8）（9）根据上面的定理所述，可以得出图8和图9都不是哈密顿图。定理6设EVG,是n阶简单图，3n。-5-（1）如任意两个不相邻结点Vvu,，均有1)()(nvdud，则在G中存在一条哈密顿路。（2）如任意两个不相邻结点Vvu,，均有nvdud)()(，则G是哈密顿图。证明：（1）先证明G是连通的。若G不是连通的，设21GG，为其两个连通分支，Vvu,分别是21GG，的结点，则vu,在G中不相邻且有21)(1)()()(21nGVGVvdud，与已知的矛盾，所以G是连通的。再证G中存在一条哈密顿路。设svvvT21:是G的最长的基本路，则ns。若ns，先证G中必经过svvv21的回路。若svv,1邻接，则T与边],[1svv构成了一个回路。若svv,1不邻接，因为svvvT21:是G的最长的基本路，所以svv,1的邻接点都在T上。设1v在T上的顺序为)112(,,,21sikivvvikii，若sv与11211,,,ikiivvv的结点都不邻接，则1)(ksvds，于是11)()(21nkskvdvd，矛盾呢。所以存在kj,,2,1，使sv与1ijv邻接，这时1111vvvvvvijssij构成回路。由于G是连通的，而ns，所以存在G的不在T上的结点v，v至少在T上的某个结点邻接。不妨设v与rv邻接，若1ijr，则1111rijsijrrvvvvvvvv构成长度为s的基本路；若1ijr，则111rijijsrvvvvvvv构成长度为s的基本路，与T的选择矛盾。所以ns。svvvT21:就是G的一条哈密顿路。（2）设svvvT21:是G中的哈密顿路，若nvv,1邻接，则nvvT,1是一条哈密顿回路；若nvv,1不邻接，利用（1）的证明方法可以证出有一条通过T的所有结点的回路，该回路即为哈密顿回路。推论G是n阶简单图，若23nGn，，则G是哈密顿图。定理6是判定哈密顿图的充分条件的，即不满足定理条件是，也可能存在哈密顿回路。3欧拉图和哈密顿图的应用3.1中国邮路问题在欧拉图和哈密顿图的应用中，有着一个最著名的数学问题：一个邮递员在投送邮件时，每次要走遍负责投递范围内的各条街道，饭后再回到邮局，他应该按照什么样的路线走，使他所走的路程最短那？为了是题目更加清晰，我们把投递地点用点表示，邮递员可供选择的路线用边来表示，每条边上的权表示两个相邻地点的距离，这就构成了一个赋权图G。-6-容易看到，中国邮路问题实际就是在赋权图G上找到一条通过各边的回路，且个变得权和最小，称真养的回路为最优回路。如果邮递员所走的街道的图形是一个欧拉图，则中国邮路问题容易解决，因为图G中任何一条欧拉回路都是最优回路。但如果图G不是欧拉图，问题就不好解决了。则图G的最优回路将通过图中有些边超过一次。如在设计公园景区路径，要考虑两个主要的因素，一是尽可能观赏全部的经典，同时尽量少走重复路径，以节省体力。如何设计各景点之间的路径连续才能科学合理地便于游客游览，也可用欧拉图的知识来解决。3.2旅行售货员问题售货员从某城市出发到各个城市一次并且只去一次，然后回到出发城市，要求出一条巡回路线，使得该巡回路线的总和最小，这就是旅行售货员问题。旅行售货员问题实质上是在一个边赋权的无向完全图上找到一条哈密顿回路，使得回路上各边的权之和最小，边上的权即为连接两城市交通线路的长度。求解旅行售货员问题的有效算法至今没有成功，有一种近似算法最邻近算法，它的基本思想非常简单：当售货员在某一个城市时，下一步就选择与这个城市最邻近的，还没有去过的城市作为他的下一站，如此进行下去直到走完所有的城市为止。最邻近算法：步骤1在完全图中任选一点作为起始点，找出一个与起始点最近的点，形成一条边的初始路，然后用步骤2逐点扩充这条路。步骤2设x表示最新加入到这条路上的顶点，从不在路上的所有的顶点中，选一个与x最邻近的点，把连接x与此点的边加到这条路上。重复这一步，直到完全图中的所有的顶点都包含在路中。步骤3把起始点和最后加入的顶点间的边放入，得到回路。3.3座位安排问题假设已知下列事实：a会讲英语，b会讲英语和汉语，c会讲英语、意大利语和俄语，d会讲日语和汉语，e会讲德语和意大利语，f会讲法语、日语和俄语，g会讲法语和德语。问这7个人应如何排座位，才能使每个人和他身边的人交谈？解：设无向图EVG,，其中},,,|,{},,,,,,,{有共同的语言且vuVvuvuEgfedcbaV,如下图所示，图G是连通图，将这七个人排座位圆桌而坐，使得每个人能与两边交谈，即在图G找哈密顿回路，经观察，该回路是abdfhe。-7-例4某次会议由20个参加，其中每人都至少有10个朋友，这20个人围城圆桌而坐，要想使每个人相邻的两位都是朋友是否可能？根据是什么？解：用结点表示人，根据题意，两人是朋友时相应结点间连一条边，则得到一个无向图EVG,，课转化为求哈密顿回路问题。由于对任意结点Vvu,，有,10)deg(,10)deg(vu，因而20)deg()deg(vu。根据求哈密顿回路的充分条件定理，可知图G是哈密顿图，图G中存在哈密顿回路，按此回路各点位置入席即为所求。3.4判断一个图是否可以一笔画出一个无向图G可一笔画出的两种情况是从图的一点出发经过每条边一次且只一次到达图的另一点和从图的一点出发通过每边一次且一次又回到顶点。判断图形是否可以一笔画出，实际上即判断是否含有所有边的欧拉图，即一个图全为偶数度结点或恰有两个结点是技术其余都是偶数。例5判定下图10和图11是否可一笔连续画出而不在任意边上重复画过。（10）（11）图10是不可以一笔画出的，有4个奇度结点，如11可以一笔画出，每个结点的度数均为偶数。4结束语本文通过对欧拉图和哈密顿图判定方法的讨论，给出了判定欧拉图和哈密顿图的定义的方法和定理的方法。在判定欧拉图和哈密顿图的过程中，利用判定过程中的性质，分别讨论了欧拉图和哈密顿图在解决中国邮路问题、旅行售货员问题、排座位问题和判定图是否可以一笔画出等问题中的具体使用，使现实生活中的问题在数学图论中得到解决，充分体现了图论在我们生活中的实用性跟重要性。参考文献：[1]徐凤生.离散数学及其应用[M].北京:机械工程出版社,2009:198-201.[2]王维凡,吕新忠.图论及其应用[M].南京:东南大学出版社,2015:89-108.[3]伍庆成.论欧拉图、哈密顿图的判定及应用[J].中国高新技术企业,2007(7):207-208.-8-