淺談圖論中兩個重要的通路

孫玲

【摘要】圖論是一門應用廣泛和內容豐富的數學分支，其應用滲透到各大領域，例如：物理、化學、信息和運籌學等.本文重點介紹“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）.