淺談圖論中兩個(gè)重要的通路

孫玲

【摘要】圖論是一門(mén)應(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回路

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

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

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

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

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

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

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

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

二、充分條件

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

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

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

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

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

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

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

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

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

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

【參考文獻(xiàn)】

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

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

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

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