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

鄧聯龍

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

關鍵詞：最小泡泡;邊合并;極大的初級回路

0引言

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

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

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

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

“最小泡泡”指的是回路內任意兩點在圖中沒有除回路的連線之外的連線的初級回路。任意一個點如果不是在圖中獨立存在或者直接通過一條線與圖相連，那么就應該包含在某一個最小泡泡中。如果是直接只通過一條線與圖相連，那么，這個圖有回路包含這個點，也不可能構成哈密頓回路。

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

“一個點的合并”：比如兩個菱形只有一個頂點相連。這種情況，作為兩個菱形中的那個相連的點，就一定會被經過至少兩次，所以是不可能通過合并形成初級回路的。

“兩個點的合并”：如果，兩個正方形只有一條“簡單邊”相連，刪去這條簡單邊即可形成一個囊括兩個正方形所有點的初級回路，這個初級回路可以繼續和其他“最小泡泡”合并。因為所有的初級回路都可以劃分成“最小泡泡”，所以與其合并其他普通初級回路來添加點，不如通過合并“最小泡泡”來添加點。但是如果公共邊上有一個或多個點，那么這一條邊會被劃分成多條邊，當成多條邊來看不能用兩個點的合并的方法合并，因為兩點中間的點無法被哈密頓回路經過。如果從中間的點開始出發，則有邊無法經過。如圖，如果從v1～v7出發經過所有的邊則不能過v8，從v8出發則不能過v2v8或v8v5中的一條線段。所以，兩個點的合并，中間不能有其他點，只有一條邊的合并，才叫做“邊合并”。

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

“由任意數量一點或兩點組成的多點合并”：這種情況，我們理解為兩個初級回路不止一條邊相接觸。我設想的理想情況是，兩個正方形接觸，中間一條邊，但是那條邊上還有一個復雜圖形，比如平行四邊形，或其他多邊形。因為這個多邊形和這條邊是“一個點的合并”類型。我們仍然無法形成哈密頓回路。

所以我們只有在僅有“簡單邊”的“兩個點的合并”的條件下，初級回路可以合并成更大的初級回路。從兩個不同的“最小泡泡”開始，可能會形成不同的極大的初級回路。

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

很好理解，哈密頓回路包含所有點，且每個點只經過一次。因為每個點只經過一次，那么每個點連接的邊最多經過一條邊的一次，也就不會有重復的邊，也就是一個特殊的初級回路。極大的初級回路不能加入新的點，那么它要么是哈密頓回路，要么不是哈密頓回路。如果已經包括了所有的點，那么就是哈密頓回路。反之，則不是哈密頓回路。

4結論

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

對于此次研究，限于本人學術水平有限，很多資料看不懂，離散數學也不是主攻方向，所以參考的資料比較少。今后如果深入學習，會逐漸彌補這個不足。

參考文獻

[1]傅彥，顧小豐，王慶先，等.離散數學及其應用[M].第3版.北京：高等教育出版社，2019.