尋找哈密爾頓回路的一種高效算法

摘要：針對基于深度優先搜索的尋找哈密爾頓回路算法，首次采用必選邊和分層檢測機制對解空間的搜索樹進行大量裁剪，從而使得算法能夠處理絕大部分含幾百個頂點的無向圖。

關鍵詞：哈密爾頓回路；必選邊；分層檢測；深度優先搜索

doi：10.3969/J.ISSN.1672-7274.2023.03.029

中圖分類號：TP 302" " " " " " " "文獻標示碼：A" " " " " " " "文章編碼：1672-7274（2023）03-00-03

An Efficient Algorithm for Finding Hamiltonian Circuits

HAN Hai

（School of Artificial Intelligence， Jianghan University， Wuhan 430056， China）

Abstract： For the first time， the required edge and hierarchical detection mechanism are used to cut a large number of search trees in the solution space， so that the algorithm can deal with most undirected graphs containing hundreds of vertices.

Key words： hamilton circuit; required edges; layered detection; depth-first search

設G=（V，E）是有n個頂點e條邊的連通無向圖，，，如果頂點序列x1x2…xn的各個頂點互不相同，并且對于i=1，2，…n-1，（xi，xi+1）∈E，以及（x1，xn）∈E，則稱該序列是G的一條哈密爾頓回路。哈密爾頓回路有重要的實際應用價值，如用于DNA表面計算模型[1]。一個圖是否存在哈密爾頓回路，已經發現的充分條件都是針對邊的數量很多的圖，或者圖具有某種特定的結構，文獻[2]搜集了此類條件，但是，目前還沒有有效辦法在不滿足前述充分條件時尋找哈密爾頓回路，文獻[3]是一種有創意的試探。研究發現，設置必選邊可以對圖中特定結構進行簡化，利用分層機制可以檢測出一部分不存在哈密爾頓回路的圖，從而大大提高深度優先搜索的效率，使得能夠處理的圖的規模擴大到上千個頂點[3]。

1" 針對特定結構的簡化

必選邊是在尋找哈密爾頓回路的過程中指定某一條或者某幾條邊，如果該圖存在哈密爾頓回路，則回路必須包含該邊。引入必選邊機制直接影響了圖中是否存在哈密爾頓回路。比如，v1v2v3v6v5v4是圖1（a）的一條哈密爾頓回路，但如果指定（v1，v4）、（v2，v5）和（v3，v6）為必選邊，則該圖就不存在哈密爾頓回路。

針對圖的某些特定結構，利用必選邊機制可以對圖進行簡化。如果圖G中存在度為2的頂點，不妨記作vk，（va，vk）和（vk，vb）是與vk相關聯的僅有的邊。如果（va，vb）是圖G的必選邊，則圖G不存在哈密爾頓回路，否則可以進行以下處理從而減少頂點和邊的數量。

（1）刪除頂點vk及其相關聯的邊（va，vk）、（vk，vb）。

（2）如果在原圖中va和vb之間沒有邊，則添加（va，vb）。

（3）設置（va，vb）為必選邊。

記處理后的圖為G'，顯然，如果G'存在哈密爾頓回路，則原圖G也存在哈密爾頓回路，反之亦然。

利用必選邊可以從圖中消除度為2的頂點，從而減少頂點總數。不僅如此，引入必選邊后，對圖中的特定結構還可以進一步處理。

（1）如果一個頂點關聯的必選邊的數量大于2，則該圖不存在哈密爾頓回路。比如圖1（b）經過對度為2的頂點進行處理后，v7關聯了3條必選邊。

（2）如果一個頂點關聯了兩條必選邊，則可以采取類似針對度為2的頂點的做法進行簡化，得到頂點數和邊數更少的圖[2]。

2" 分層檢測必要條件

分層的規則是在尚未確定層數的頂點中，把與第i層頂點相鄰的頂點劃分在第i+1層。對于無向連通圖G，首先在頂點集V中選擇一個頂點vt作為分層的起始頂點，以vt作為第1層，把與vt相鄰的頂點劃歸第2層，剩下頂點中與第2層相鄰的頂點劃歸第3層，以此類推。根據需要，也能夠以一條邊的兩個頂點作為起始頂點進行分層。假設一個連通圖進行上述處理后共分為k層，以Ci表示第i層的頂點數，以Di表示連接第i層頂點的邊的數目，Ti表示連接第i層與第i+1層頂點的邊的數目，不難證明如下結論。

（1）確定第1層的頂點后，每一個頂點有唯一確定的層號。

（2）每一條邊要么連接同一層內的兩個頂點，要么連接相鄰兩層之間的頂點。

（3）對于1lt;ilt;k，如果Ci=1，即第i層只有1個頂點，則該頂點一定是割點。

（4）對于1lt;ilt;k，如果第i層只有唯一頂點關聯到第i+1層，則該頂點一定是割點。

如果圖G存在哈密爾頓回路，上述分層中的vt當然是回路中的一個頂點，回路上的各個頂點和邊分布在各層。以Mi表示該回路中關聯頂點均在第i層的邊的數量，Wi表示該回路在第i層與第i+1層之間的邊的數量，并令W0=Wk=0，則：

（5）對于1lt;=ilt;k，Wi必定是偶數，并且W1=2。

（6）對于1lt;=ilt;=k，2Ci=Mi+Wi-1+Wi。

所以，一個無向連通圖擁有哈密爾頓回路必須滿足如下條件。

必要條件：對連通無向圖以任意頂點為起始頂點進行分層，如果發現有割點，或者某一層的統計數據不可能滿足上述結論（6），則該圖不存在哈密爾頓回路。

針對n個頂點的無向圖，以某個頂點為起點進行分層并判斷是否滿足上述必要條件，其時間復雜度不超過O（n3），可以尋找哈密爾頓回路時加以利用。比如，由k個頂點和m個頂點組成的二部圖在k≠m時不滿足該條件，因而不存在哈密爾頓回路。

3" 算法設計

可以設計如下的深度優先搜索算法，針對給定頂點集V和邊集E尋找哈密爾頓回路。

輸入：頂點集V和邊集E。

輸出：如果找到回路，則輸出V中頂點的排列，否則輸出空序列。

（1）針對度為2的頂點和關聯必選邊數為2的頂點反復進行簡化。

（2）存在以下情況之一則輸出空序列，算法結束；否則轉到（3）。

①V中頂點數小于3。

②存在度小于2的頂點。

③存在關聯的必選邊數大于2的頂點。

④不符合分層檢測必要條件。

（3）如果或者，檢查當前情況是否構成哈密爾頓回路，輸出相應的結果，算法結束；否則轉到（4）。

（4）如果E中有必選邊，則執行以下操作，否則轉（5）。

①任選其中一條必選邊，記作（vs，vt）。記S為vs的相鄰頂點集，T為vt的相鄰頂點集。

②從S和T中各取一個頂點，va∈S，vb∈T，檢查va和vb的每一種組合，如果va=vb或者（va，vb）是必選邊，則在該組合之下不存在哈密爾頓回路；否則從圖中刪除頂點vs、vt及其相關聯的邊，并設置（va，vb）為必選邊，針對簡化后的圖利用本算法尋找哈密爾頓回路。針對va和vb的任何一種組合找到哈密爾頓回路，輸出結果；所有組合都找不到回路，則輸出空序列[4]。

（5）任選一個頂點，記作vt，記T為vt的相鄰頂點集。從T中取兩個頂點va和vb，對va和vb的每一種組合做如下操作：從圖中刪除頂點vt及其相關聯的邊，并設置（va，vb）為必選邊，針對如此處理后的圖利用本算法尋找哈密爾頓回路。如果va和vb的每一種組合之下都找不到哈密爾頓回路，輸出空序列。

4" 實驗結果

采用類似于文獻[4]的方式，測試數據采用隨機生成的無向連通圖，但頂點數更多。首先按頂點數n和邊數e的取值范圍設置若干個類別，n的值從幾十到一千劃分幾檔，e也劃分1.5n到5n以上劃分若干檔，然后隨機生成n、e的值，并在鄰接矩陣中隨機設置e條邊，去除其中不連通和包含度為1的頂點的圖，每個類別取1 000個圖作為測試數據。用C++語言編寫代碼實現上述算法，在一臺主頻3 GHz、內存16 GB的普通計算機上運行，針對測試數據尋找哈密爾頓回路。絕大多數情況下，程序能夠較快地給出結論，僅有極少量的圖不能在短時間內判定。另外，實驗還表明，算法的步驟（4）選取頂點度盡可能大的vs和vt為好，而步驟（5）則選擇度較小的頂點為好[1]。

對于幾個已知不存在哈密爾頓回路的無向圖，比如圖2的兩個3-正則平面圖g38和g46t，該算法都能夠在短時間內給出正確的判定結果。如果允許添加1條邊從而使其擁有哈密爾頓回路，利用該算法可以很快計算出對g38有586種添加方法，對g46t有822種添加方法。

5" 結束語

引入必選邊并輔以分層檢測機制，能夠顯著提高深度優先遍歷的效率。對于測試數據當中有割點的圖，由于算法中的分層檢測機制，因而可以很快輸出“該圖不存在哈密爾頓回路”。在egt;3n時，隨機生成的無向圖絕大多數情況下都存在哈密爾頓回路，而且有很多組解，算法能夠較快地找出其中1條。算法面對的不利情況之一是類似圖3的結構，這樣的圖是沒有哈密爾頓回路的，但是，其中有很多圖能夠滿足前述分層檢測必要條件，對這樣的圖，算法無法在短時間內運行完畢。在尋找哈密爾頓回路時需要應對什么樣的特定結構以及如何應對還有待進一步研究。■

參考文獻

[1] 李朝鵬，成運，李肯立，等．哈密爾頓回路問題的DNA表面計算模型[J]．計算機工程與應用，2010（8）：48-51.

[2] 袁威威，李珊．哈密爾頓圖的判定及應用[J]．黑河學院學報（自然科學研究），2014（4）：123-125.

[3] 黃瀟，呂柏權，張有得．改進匈牙利法求解貨郎擔問題[J]．工業控制計算機，2022（5）：112-114.

[4] 梅俊杰，劉蕻，許歡，等．隨機圖的哈密爾頓回路實驗研究[J]．貴州大學學報（自然科學版），2013（3）：77-81.