證明圖中是否有哈密頓回路并利用定義證明是否是哈密頓圖的方法

鄧聯(lián)龍

摘要：哈密頓回路是一個(gè)初級(jí)回路，而且是圖中最大的初級(jí)回路。我們可以通過尋找圖中最大的初級(jí)回路，判斷它是不是一個(gè)哈密頓回路，如果是，則圖中有哈密頓回路，如果不是，則沒有哈密頓回路。所以我一共有三個(gè)主要的論點(diǎn)：1、初級(jí)回路中如果有兩點(diǎn)不相鄰還可以連線，那么這條連線可以把這個(gè)初級(jí)回路分為更小的初級(jí)回路，直到圖內(nèi)沒有不相鄰的兩點(diǎn)相連。（這種最小的初級(jí)回路，我稱為“最小泡泡”）2、“最小泡泡”能夠通過相鄰的邊合并成更大的初級(jí)回路，直至無法合并成更大的初級(jí)回路。（這種初級(jí)回路我稱為“極大的初級(jí)回路”，圖中可能不止一個(gè)極大的初級(jí)回路。）3、極大的初級(jí)回路如果包含了圖中所有的點(diǎn)，則是哈密頓回路，如果沒有包括所有的點(diǎn)，則不是哈密頓回路。

關(guān)鍵詞：最小泡泡;邊合并;極大的初級(jí)回路

0引言

哈密頓回路是一個(gè)初級(jí)回路，而且是圖中最大的初級(jí)回路。我們可以通過尋找圖中最大的初級(jí)回路，判斷它是不是一個(gè)哈密頓回路，如果是，則圖中有哈密頓回路，如果不是，則沒有哈密頓回路。下面就筆者的論點(diǎn)進(jìn)行介紹。

1論點(diǎn)一：初級(jí)回路中如果有兩點(diǎn)不相鄰還可以連線，那么這條連線可以把這個(gè)初級(jí)回路分為更小的初級(jí)回路，直到圖內(nèi)沒有不相鄰的兩點(diǎn)相連。這種最小的初級(jí)回路，我稱為“最小泡泡”。

如圖是一個(gè)初級(jí)回路，中間兩點(diǎn)尚未連接但是圖中存在這條線，是存在圖中卻不存在于回路中的線。在這個(gè)圖中，v1v2v3v7v6v5v4v1構(gòu)成一個(gè)大的初級(jí)回路，而v2v5并不相連。如果連上v2和v5，則線段v2v5與線段v2v3v7v6v5等價(jià)，所以v1v2v5v4v1構(gòu)成一個(gè)更小的初級(jí)回路。因?yàn)檫B線只有兩個(gè)點(diǎn)，回路中這兩點(diǎn)不相鄰，至少還要過一個(gè)點(diǎn)，即至少三個(gè)點(diǎn)的線被一個(gè)兩個(gè)點(diǎn)的線段所取代。所以只要有不相鄰的兩點(diǎn)可以連線，那么這個(gè)初級(jí)回路就可以被這條連線分成更小的初級(jí)回路。

一條邊相連，不考慮邊上是否有點(diǎn)，我認(rèn)為是兩個(gè)點(diǎn)的合并。如果沒有點(diǎn)，我稱為“簡(jiǎn)單邊”。我把初級(jí)回路由小的合并成大的過程分為：“一個(gè)點(diǎn)的合并”、“兩個(gè)點(diǎn)的合并”、“由任意數(shù)量一點(diǎn)或兩點(diǎn)組成的多點(diǎn)合并”。然后，我提出一個(gè)叫做“最小泡泡”的概念，最小泡泡是一種特殊的初級(jí)回路。

“最小泡泡”指的是回路內(nèi)任意兩點(diǎn)在圖中沒有除回路的連線之外的連線的初級(jí)回路。任意一個(gè)點(diǎn)如果不是在圖中獨(dú)立存在或者直接通過一條線與圖相連，那么就應(yīng)該包含在某一個(gè)最小泡泡中。如果是直接只通過一條線與圖相連，那么，這個(gè)圖有回路包含這個(gè)點(diǎn)，也不可能構(gòu)成哈密頓回路。

2論點(diǎn)二是：“最小泡泡”能夠通過相鄰的邊合并成更大的初級(jí)回路，直至無法合并成更大的初級(jí)回路。（這種初級(jí)回路我稱為“極大的初級(jí)回路”，圖中可能不止一個(gè)極大的初級(jí)回路。）論點(diǎn)三是：初級(jí)回路通過消去一條相鄰的，上面無點(diǎn)的邊之間的合并我稱為“兩個(gè)點(diǎn)的合并”也稱為“邊合并”，并認(rèn)為，只有通過“邊合并”才能形成一個(gè)更大的初級(jí)回路。

“一個(gè)點(diǎn)的合并”：比如兩個(gè)菱形只有一個(gè)頂點(diǎn)相連。這種情況，作為兩個(gè)菱形中的那個(gè)相連的點(diǎn)，就一定會(huì)被經(jīng)過至少兩次，所以是不可能通過合并形成初級(jí)回路的。

“兩個(gè)點(diǎn)的合并”：如果，兩個(gè)正方形只有一條“簡(jiǎn)單邊”相連，刪去這條簡(jiǎn)單邊即可形成一個(gè)囊括兩個(gè)正方形所有點(diǎn)的初級(jí)回路，這個(gè)初級(jí)回路可以繼續(xù)和其他“最小泡泡”合并。因?yàn)樗械某跫?jí)回路都可以劃分成“最小泡泡”，所以與其合并其他普通初級(jí)回路來添加點(diǎn)，不如通過合并“最小泡泡”來添加點(diǎn)。但是如果公共邊上有一個(gè)或多個(gè)點(diǎn)，那么這一條邊會(huì)被劃分成多條邊，當(dāng)成多條邊來看不能用兩個(gè)點(diǎn)的合并的方法合并，因?yàn)閮牲c(diǎn)中間的點(diǎn)無法被哈密頓回路經(jīng)過。如果從中間的點(diǎn)開始出發(fā)，則有邊無法經(jīng)過。如圖，如果從v1～v7出發(fā)經(jīng)過所有的邊則不能過v8，從v8出發(fā)則不能過v2v8或v8v5中的一條線段。所以，兩個(gè)點(diǎn)的合并，中間不能有其他點(diǎn)，只有一條邊的合并，才叫做“邊合并”。

具體的合并方法：兩個(gè)初級(jí)回路僅有一條邊相連，消去這條邊，把邊的一端看做入口，另一端看做出口，把一個(gè)圖看做是原來的圖，另一個(gè)圖看做是附加的圖。原來的圖從入口處進(jìn)入附加的圖繼續(xù)走附加的圖的初級(jí)回路除了消去的邊的路徑，回到出口，繼續(xù)走原來的圖沒走完的初級(jí)回路。

“由任意數(shù)量一點(diǎn)或兩點(diǎn)組成的多點(diǎn)合并”：這種情況，我們理解為兩個(gè)初級(jí)回路不止一條邊相接觸。我設(shè)想的理想情況是，兩個(gè)正方形接觸，中間一條邊，但是那條邊上還有一個(gè)復(fù)雜圖形，比如平行四邊形，或其他多邊形。因?yàn)檫@個(gè)多邊形和這條邊是“一個(gè)點(diǎn)的合并”類型。我們?nèi)匀粺o法形成哈密頓回路。

所以我們只有在僅有“簡(jiǎn)單邊”的“兩個(gè)點(diǎn)的合并”的條件下，初級(jí)回路可以合并成更大的初級(jí)回路。從兩個(gè)不同的“最小泡泡”開始，可能會(huì)形成不同的極大的初級(jí)回路。

3論點(diǎn)四是：極大的初級(jí)回路如果包含了圖中所有的點(diǎn)，則是哈密頓回路，如果沒有包括所有的點(diǎn)，則不是哈密頓回路。

很好理解，哈密頓回路包含所有點(diǎn)，且每個(gè)點(diǎn)只經(jīng)過一次。因?yàn)槊總€(gè)點(diǎn)只經(jīng)過一次，那么每個(gè)點(diǎn)連接的邊最多經(jīng)過一條邊的一次，也就不會(huì)有重復(fù)的邊，也就是一個(gè)特殊的初級(jí)回路。極大的初級(jí)回路不能加入新的點(diǎn)，那么它要么是哈密頓回路，要么不是哈密頓回路。如果已經(jīng)包括了所有的點(diǎn)，那么就是哈密頓回路。反之，則不是哈密頓回路。

4結(jié)論

通過最小泡泡和初級(jí)回路不斷合并新的最小泡泡，總能形成更大的初級(jí)回路，直至無法合并入新的最小泡泡，這樣的初級(jí)回路我們稱為極大的初級(jí)回路。如果有一個(gè)極大的初級(jí)回路囊括了所有的點(diǎn)，那么我們則稱這個(gè)初級(jí)回路是哈密頓回路，這個(gè)圖是哈密頓圖，反之，這個(gè)圖中無哈密頓回路，它不是哈密頓圖。

對(duì)于此次研究，限于本人學(xué)術(shù)水平有限，很多資料看不懂，離散數(shù)學(xué)也不是主攻方向，所以參考的資料比較少。今后如果深入學(xué)習(xí)，會(huì)逐漸彌補(bǔ)這個(gè)不足。

參考文獻(xiàn)

[1]傅彥，顧小豐，王慶先，等.離散數(shù)學(xué)及其應(yīng)用[M].第3版.北京：高等教育出版社，2019.