孫玲

【摘要】圖論是一門應(yīng)用廣泛和內(nèi)容豐富的數(shù)學(xué)分支，其應(yīng)用滲透到各大領(lǐng)域，例如：物理、化學(xué)、信息和運(yùn)籌學(xué)等.本文重點(diǎn)介紹“Euler通路”和“Hamilton回路”的聯(lián)系和區(qū)別，以及如何判斷“Euler環(huán)游”和“Hamilton”回路.

【關(guān)鍵詞】Euler通路；Euler環(huán)游；Hamilton通路；Hamilton回路

圖論是一門應(yīng)用十分廣泛和內(nèi)容非常豐富的數(shù)學(xué)分支，圖論的應(yīng)用也滲透到物理、化學(xué)、信息學(xué)和運(yùn)籌學(xué)等領(lǐng)域.其中“Euler環(huán)游”或“Hamilton回路”是圖論這門學(xué)科中的兩個基本且最重要的環(huán)游，利用這兩個環(huán)游我們解決了許多問題.

“Euler通路”和“Hamilton回路”是兩個意義不同的通路.一個圖具有“Euler通路”是指這個圖里存在著這樣一條通路，他經(jīng)過圖的每條邊一次并且只經(jīng)過一次；“Hamilton通路”是指它經(jīng)過圖上各頂點(diǎn)一次并且僅僅一次，那么這種通路就叫“Hamilton通路”.

“Hamilton通路”強(qiáng)調(diào)圖上的“各頂點(diǎn)”一次并且僅僅一次，“Euler通路”強(qiáng)調(diào)的是圖上“各邊”要經(jīng)過一次并且僅僅一次.“Hamilton通路”并不要求經(jīng)過圖的每條邊，“Euler通路”卻必然要經(jīng)過圖上的各頂點(diǎn)并且容許重復(fù)經(jīng)過.需要注意的是：一個圖有“Euler通路”，但不一定有“Hamilton通路”.

一般來講一個圖的“Euler通路”和“Hamilton通路”是不重合的，但在特殊類型的圖中它們是重合的，例如：多邊形圖.實(shí)際應(yīng)用當(dāng)中，判斷一個圖是否具有“Euler環(huán)游”和“Hamilton回路”就顯得特別重要，以下內(nèi)容我們介紹如何判斷“Euler環(huán)游”和“Hamilton回路”.

關(guān)于圖的奇頂點(diǎn)個數(shù)，還有一個簡單常用的定理，也是Euler先發(fā)現(xiàn)并證明的，通常認(rèn)為它是圖論中最早出現(xiàn)的一個定理：對于任意的圖G，奇頂點(diǎn)的個數(shù)一定是偶數(shù).

現(xiàn)在我們回頭來看“七橋問題”，我們把七橋轉(zhuǎn)化為點(diǎn)與邊的關(guān)系，我們發(fā)現(xiàn)圖中含有奇點(diǎn)，所以該問題不含有Euler回路，因?yàn)閳D中含有奇點(diǎn)的個數(shù)不止兩個，所以也沒有Euler通路，所以七橋問題的答案是否定的.

一、直接找——（環(huán)游路線）

對于前面所說的世界環(huán)游問題，我們采用“直接求解”的方法.也就是從圖的某一個頂點(diǎn)開始，采用一步步試探的方法，來找到圖的Hamilton回路.如果找到了一條，解就得出來了；如果找不到，就可能沒有解.

二、充分條件

定理1 有n個頂點(diǎn)的圖（n≥2），如果它的任意兩個頂點(diǎn)度數(shù)的和大于或等于n-1，那么它有一條Hamilton通路.

定理2 有n個頂點(diǎn)的圖（n≥3），如果它有任意兩個頂點(diǎn)度數(shù)的和大于或等于n，那么它一定有一條Hamilton回路.

例：某廠生產(chǎn)由6種不同顏色的紗織成的雙色布，已知花布品種中，每種顏色至少分別和其他3種不同的顏色搭配，要求證明：可以挑出3種雙色布，它們恰好含有6種不同的顏色.

我們現(xiàn)在把它轉(zhuǎn)化為一個圖論問題，讓每種顏色對應(yīng)一個頂點(diǎn)，這樣就有6個頂點(diǎn)：a、b、c、d、e、f，哪兩種顏色搭配織成一種雙色布，我們就在這兩種顏色對應(yīng)的頂點(diǎn)之間連一條邊，因此在這個圖里，一條邊代表一種雙色布，它們所對應(yīng)的兩條邊沒有相同的頂點(diǎn).要找到含有6種不同顏色的3種雙色布，就變成要在圖上找到三條彼此沒有公共頂點(diǎn)的邊，如果圖上恰好有一條經(jīng)過6個頂點(diǎn)各一次的Hamilton通路或回路，那么這樣3條彼此沒有公共頂點(diǎn)的邊總是存在的，在這個圖里3條實(shí)線邊或3條虛線邊都滿足這個條件.

三、交錯標(biāo)記法

對于一種特殊類型的問題，我們也將采用一種特殊的方法——“交錯標(biāo)記法”來判斷它是否有Hamilton通路或回路.

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

我們的某一個頂點(diǎn)最上面的一個頂點(diǎn)標(biāo)記上A，然后給和它相鄰的各頂點(diǎn)標(biāo)記上B，依次類推，直到所有的頂點(diǎn)都標(biāo)記上了A或B為止.

由于16個頂點(diǎn)交錯標(biāo)記了A和B，所以，如果圖上存在Hamilton通路的話，它必然要交錯地走過頂點(diǎn)A和頂點(diǎn)B，也就是說如果走到了A點(diǎn)的話，下一步無論沿著哪條邊走只能走到B點(diǎn)，如果從B點(diǎn)出發(fā)，無論怎樣走只能走到A點(diǎn).在這條Hamilton通路上只能交錯地出現(xiàn)頂點(diǎn)A、B、A、B……而不可能連續(xù)地出現(xiàn)兩個A或兩個B.要想把這16個頂點(diǎn)都走到且不重復(fù)，無論怎么安排都至少有兩個A挨在一起，但是在圖上的任何一條通路都不可能連續(xù)經(jīng)過2個A點(diǎn)的，于是可以看出在圖上是不可能存在Hamilton通路的.

在解決這個問題時，我們所采用的就是“交錯標(biāo)記法”：先給圖的頂點(diǎn)交錯標(biāo)記上兩種不同的符號，再根據(jù)在這類圖里可能有Hamilton通路所具備的必要條件，就是通路上不能連續(xù)地出現(xiàn)同一種符號，來判斷這個圖是否可能具有Hamilton通路.

【參考文獻(xiàn)】

[1]卜月華.圖論及其應(yīng)用[M].南京：東南大學(xué)出版社，2003.

[2]單樽.趣味的圖論問題[M].上海：上海教育出版社，1980.

[3]林國寧，等.圖論及其應(yīng)用習(xí)題解答[M].北京：清華大學(xué)出版社，1988.

[4]張素芬，王琳.歐拉定理的應(yīng)用——“一筆畫”問題淺析[J].現(xiàn)代經(jīng)濟(jì)信息，2008（3）.