浅谈图论中两个重要的通路

【摘要】图论是一门应用广泛和内容丰富的数学分支，其应用渗透到各大领域，例如：物理、化学、信息和运筹学等.本文重点介绍“Euler通路”和“Hamilton回路”的联系和区别，以及如何判断“Euler环游”和“Hamilton”回路.

【关键词】Euler通路；Euler环游；Hamilton通路；Hamilton回路

图论是一门应用十分广泛和内容非常丰富的数学分支，图论的应用也渗透到物理、化学、信息学和运筹学等领域.其中“Euler环游”或“Hamilton回路”是图论这门学科中的两个基本且最重要的环游，利用这两个环游我们解决了许多问题.

“Euler通路”和“Hamilton回路”是两个意义不同的通路.一个图具有“Euler通路”是指这个图里存在着这样一条通路，他经过图的每条边一次并且只经过一次；“Hamilton通路”是指它经过图上各顶点一次并且仅仅一次，那么这种通路就叫“Hamilton通路”.

“Hamilton通路”强调图上的“各顶点”一次并且仅仅一次，“Euler通路”强调的是图上“各边”要经过一次并且仅仅一次.“Hamilton通路”并不要求经过图的每条边，“Euler通路”却必然要经过图上的各顶点并且容许重复经过.需要注意的是：一个图有“Euler通路”，但不一定有“Hamilton通路”.

一般来讲一个图的“Euler通路”和“Hamilton通路”是不重合的，但在特殊类型的图中它们是重合的，例如：多边形图.实际应用当中，判断一个图是否具有“Euler环游”和“Hamilton回路”就显得特别重要，以下内容我们介绍如何判断“Euler环游”和“Hamilton回路”.

关于图的奇顶点个数，还有一个简单常用的定理，也是Euler先发现并证明的，通常认为它是图论中最早出现的一个定理：对于任意的图G，奇顶点的个数一定是偶数.

现在我们回头来看“七桥问题”，我们把七桥转化为点与边的关系，我们发现图中含有奇点，所以该问题不含有Euler回路，因为图中含有奇点的个数不止两个，所以也没有Euler通路，所以七桥问题的答案是否定的.

一、直接找——（环游路线）

对于前面所说的世界环游问题，我们采用“直接求解”的方法.也就是从图的某一个顶点开始，采用一步步试探的方法，来找到图的Hamilton回路.如果找到了一条，解就得出来了；如果找不到，就可能没有解.

二、充分条件

定理1 有n个顶点的图（n≥2），如果它的任意两个顶点度数的和大于或等于n-1，那么它有一条Hamilton通路.

定理2 有n个顶点的图（n≥3），如果它有任意两个顶点度数的和大于或等于n，那么它一定有一条Hamilton回路.

例：某厂生产由6种不同颜色的纱织成的双色布，已知花布品种中，每种颜色至少分别和其他3种不同的颜色搭配，要求证明：可以挑出3种双色布，它们恰好含有6种不同的颜色.

我们现在把它转化为一个图论问题，让每种颜色对应一个顶点，这样就有6个顶点：a、b、c、d、e、f，哪两种颜色搭配织成一种双色布，我们就在这两种颜色对应的顶点之间连一条边，因此在这个图里，一条边代表一种双色布，它们所对应的两条边没有相同的顶点.要找到含有6种不同颜色的3种双色布，就变成要在图上找到三条彼此没有公共顶点的边，如果图上恰好有一条经过6个顶点各一次的Hamilton通路或回路，那么这样3条彼此没有公共顶点的边总是存在的，在这个图里3条实线边或3条虚线边都满足这个条件.

三、交错标记法

对于一种特殊类型的问题，我们也将采用一种特殊的方法——“交错标记法”来判断它是否有Hamilton通路或回路.

例：判断是否具有Hamilton通路.

我们的某一个顶点最上面的一个顶点标记上A，然后给和它相邻的各顶点标记上B，依次类推，直到所有的顶点都标记上了A或B为止.

由于16个顶点交错标记了A和B，所以，如果图上存在Hamilton通路的话，它必然要交错地走过顶点A和顶点B，也就是说如果走到了A点的话，下一步无论沿着哪条边走只能走到B点，如果从B点出发，无论怎样走只能走到A点.在这条Hamilton通路上只能交错地出现顶点A、B、A、B……而不可能连续地出现两个A或两个B.要想把这16个顶点都走到且不重复，无论怎么安排都至少有两个A挨在一起，但是在图上的任何一条通路都不可能连续经过2个A点的，于是可以看出在图上是不可能存在Hamilton通路的.

在解决这个问题时，我们所采用的就是“交错标记法”：先给图的顶点交错标记上两种不同的符号，再根据在这类图里可能有Hamilton通路所具备的必要条件，就是通路上不能连续地出现同一种符号，来判断这个图是否可能具有Hamilton通路.

【参考文献】

[1]卜月华.图论及其应用[M].南京：东南大学出版社，2003.

[2]单樽.趣味的图论问题[M].上海：上海教育出版社，1980.

[3]林国宁，等.图论及其应用习题解答[M].北京：清华大学出版社，1988.

[4]张素芬，王琳.欧拉定理的应用——“一笔画”问题浅析[J].现代经济信息，2008（3）.

推荐访问： 通路 浅谈 两个 图论

---