基于鄰接矩陣和遞歸算法的哈密頓回路研究①

葉志琳

(泉州工藝美術(shù)職業(yè)學(xué)院教務(wù)處,福建 泉州 362500)

0 引 言

在組合數(shù)學(xué)中，有一個(gè)分支叫做圖論。圖是作為圖論的討論對(duì)象。一些固定的點(diǎn)以及點(diǎn)之間的連起來(lái)的線形成了圖[1]。這種圖可以描述線兩端頂點(diǎn)之間的關(guān)系。事物可以用點(diǎn)標(biāo)記，兩個(gè)事物之間的聯(lián)系，用它們間的連線來(lái)標(biāo)記。在實(shí)際生活中，有許多問(wèn)題與哈密爾頓圖息息相關(guān)[2]。比如著名的旅行商問(wèn)題(TSP)：一個(gè)旅行商打算出差去其他地方[3,4]，他要去某些客戶所居住的城市，然后返回到他出發(fā)的城市。在他要前往的城市中，一些城市之間存在航班，而也有一些沒(méi)有，他能否做出這樣的安排，使他只經(jīng)過(guò)所有城市一次，并返回起始的城市。文中通過(guò)鄰接矩陣和遞歸算法對(duì)TP問(wèn)題的哈密頓回路進(jìn)行分析，以期快速得出圖存在哈密頓回路的充分條件。

1 哈密頓圖的概述

1.1 哈密頓的定義

在一個(gè)圖中，如果圖中所有的點(diǎn)都被一條路徑包含，那么這條路就是哈密頓路。如果這條路徑，經(jīng)過(guò)全部的頂點(diǎn)，并且這條路徑僅能經(jīng)過(guò)每個(gè)點(diǎn)一次，那么這條路徑就是哈密頓通路。如果這條路徑經(jīng)過(guò)了圖中的每一個(gè)頂點(diǎn)有且只有一次，并且最后這條路徑返回到了起點(diǎn)，就把這條路徑叫做哈密頓回路。如果一條哈密頓回路存在于一個(gè)圖中，這個(gè)圖即哈密頓圖[5]。圈的定義：圈是一條封閉的路徑中只有第一個(gè)點(diǎn)和最后一個(gè)點(diǎn)相同，其他的點(diǎn)互不相同。因此在n階圖G中，哈密頓圈就是一個(gè)是度為n的圈:x1-x2-…-xn-x1[6]。其中x1-x2-…-xn-x1是G的按次排序頂點(diǎn)。連接G的頂點(diǎn)a和b的長(zhǎng)度為n-1的鏈：

a=x1-x2-...-xn=b

叫做G中的一條哈密頓鏈。

1.2 圖存在哈密頓回路的充分條件

并不是每個(gè)圖都存在哈密頓回路。圖中的每一條邊把A={a,b,c}中的一個(gè)頂點(diǎn)與B={x,y}中的一個(gè)頂點(diǎn)連接起來(lái)。因此，哈密頓回路就必須從A中的頂點(diǎn)到B中的頂點(diǎn)交錯(cuò)通過(guò)。如果|A|=|B|,這種情況可以發(fā)生。

定理1[4]：若G是存在n個(gè)頂點(diǎn)，并且n≥3的一個(gè)圖，而且只要x≠y的頂點(diǎn)沒(méi)有連在一起，就有x的度數(shù)和y的度數(shù)的和一定大于等于n，這時(shí)，G有哈密頓回路。

證明：假設(shè)G沒(méi)有哈密頓回路。將證明對(duì)于V(G)中的某些不連接的x,

degG(x)+degG(y)

(1)

其中degG(a)表示a在G中的度數(shù)。如果增加G的邊，那么最終可以獲得一個(gè)完全圖，這個(gè)完全圖沒(méi)有哈密頓回路。因此，在增加邊的過(guò)程中，必定會(huì)遇到有下面性質(zhì)的圖H：H沒(méi)有哈密頓回路，但是在H中增加一條邊，可以給出有哈密頓回路的圖。將證明在H中，不鄰接的x和y使得

degH(x)+degH(y)

(2)

但是，對(duì)于所有a，有degG(a)

在H中選擇任意不鄰接的x和y。然后在H中加上邊{x,y}就有哈密頓回路。因?yàn)镠沒(méi)有哈密頓回路，所以這條哈密頓回路必須使用邊{x,y}，因此這條回路可以寫(xiě)成：x,y,a1，a2，…,an-2,x?，F(xiàn)在，V(H)={x,y,a1，a2，…,an-2}。另外，注意到對(duì)于i>1,有

{y,ai}∈E(H)?{x,ai-1}?E(H)

(3)

因?yàn)槿绻鲜讲怀闪ⅲ敲淳陀?/p>

y,ai,ai+1,…,an-2,x,ai-1,ai-2,…,a1,y

這條哈密頓回路是H中的，這是矛盾的?，F(xiàn)在，(3)式和邊{x,y}?E(H)蘊(yùn)含(2)式。

推論1：若G是存在n個(gè)頂點(diǎn)的圖并且n≥3，每一個(gè)邊的度數(shù)至少等于n/2,那么G有哈密頓回路。

推論2：若G是存在n個(gè)頂點(diǎn)的圖，并且n≥3,x和y是G中不鄰接的點(diǎn)，使得deg(x)+deg(y)≥n,那么G有哈密頓回路當(dāng)且僅當(dāng)G加上邊{x,y}有哈密頓回路時(shí)。

2 商旅問(wèn)題中求解權(quán)值最小的哈密頓回路

2.1 提出問(wèn)題

如果《美麗中國(guó)》準(zhǔn)備拍第二季，準(zhǔn)備錄制10個(gè)城市的節(jié)目。從北京出發(fā)，目標(biāo)城市有天津，上海，重慶，南寧，哈爾濱，長(zhǎng)春，沈陽(yáng)，石家莊，鄭州這十個(gè)城市。劇組通過(guò)乘飛機(jī)飛往各個(gè)城市，現(xiàn)在各個(gè)城市之間都有航班，那么怎樣安排，才能使經(jīng)過(guò)所有的城市并且只經(jīng)過(guò)一次，所走的航線最短？各個(gè)城市之間的距離簡(jiǎn)化圖如圖1所示。

圖1 各個(gè)城市之間的距離簡(jiǎn)化圖

由題目可知，所有城市之間都有航班。這種問(wèn)題可以簡(jiǎn)單概括為求最小權(quán)的哈密頓回路問(wèn)題，即從一個(gè)點(diǎn)開(kāi)始，遍歷圖中所有的點(diǎn)，并且路線最短。那么怎么選擇路線，才能讓總行程最小。在圖論中，這問(wèn)題要求在一個(gè)帶權(quán)的，完全無(wú)向圖的里面，能夠得出一條最小權(quán)值的哈密頓回路。不難發(fā)現(xiàn)這個(gè)問(wèn)題需要解出的是全部頂點(diǎn)的所有排列。當(dāng)頂點(diǎn)變多時(shí)，會(huì)有及其多的組合。一共有45條航線，有9！種組合。

2.2 算法思路

在完全圖中，構(gòu)建出每個(gè)城市點(diǎn)間的路徑的圖的，運(yùn)用鄰接數(shù)組，把每個(gè)城市間的航程長(zhǎng)度放在這個(gè)圖的數(shù)組中，城市間的距離如表1所示，并且運(yùn)用遞歸方法，尋找從某一個(gè)城市出發(fā)，遍歷全部其他的城市，并且只經(jīng)過(guò)一次后的路徑，進(jìn)而計(jì)算出每條路徑的長(zhǎng)度，將每條路徑與其長(zhǎng)度一起輸出，然后選用冒泡排序?qū)λ新窂酱笮∵M(jìn)行排序，通過(guò)比較得到的路徑長(zhǎng)度然后得到最短的路徑，整個(gè)運(yùn)算過(guò)程由C++程序完成。

表1 各個(gè)城市間距離(km)

2.3 具體實(shí)現(xiàn)過(guò)程

首先做所有的定義，包括設(shè)置的最大的頂點(diǎn)數(shù)；定義一個(gè)結(jié)構(gòu)體，包含下面4個(gè)屬性(頂點(diǎn)向量、鄰接矩陣、頂點(diǎn)數(shù)、邊數(shù))；定義一個(gè)G，其中G包含上述的4個(gè)屬性，聲明一個(gè)無(wú)向圖的鄰接矩陣類型并且設(shè)置標(biāo)志數(shù)組。

然后設(shè)置圖的一些基本操作，用于尋找點(diǎn)V的位置，若查找成功則返回頂點(diǎn)的下標(biāo)；下面用數(shù)組鄰接矩陣表示法構(gòu)造無(wú)向圖，用freopen打開(kāi)錄入的信息，接著表明頂點(diǎn)v1,v2.并且標(biāo)明權(quán)值，即兩點(diǎn)之間的長(zhǎng)度，接著構(gòu)造定點(diǎn)向量，初始化鄰接矩陣，構(gòu)造鄰接矩陣；

最后輸出圖頂點(diǎn)，并顯示該圖的鄰接矩陣，并輸出鄰接矩陣；根據(jù)遞歸函數(shù)，產(chǎn)生排列，用以尋找最佳路徑，定義數(shù)組的行數(shù)，當(dāng)滿足條件后，接著生成排列，并且將其存儲(chǔ)在數(shù)組中，找出所有的路徑，然后計(jì)算所有的路徑的長(zhǎng)度，進(jìn)行比較并找出最短的路徑；輸出所有路徑及其長(zhǎng)度，對(duì)輔助數(shù)組冒泡排序，找最小值，得到MINWAY為最小路徑；輸出最短路徑并指出長(zhǎng)度，遞歸生成排列組合。

2.4 計(jì)算結(jié)果

現(xiàn)在用它來(lái)解決上述的10個(gè)城市的最短路徑規(guī)劃問(wèn)題，在C++軟件中依次輸入城市個(gè)數(shù)，路線數(shù)量，城市名，每一個(gè)城市間的距離，運(yùn)行輸出結(jié)果如圖2所示。

從圖2可知：從北京出發(fā)，經(jīng)過(guò)所有城市再回到北京的路線一共有368200條，其中最短的路徑一共有6條，它們分別是：

圖2 10個(gè)城市之間的最佳路線

(1)北京-哈爾濱-長(zhǎng)春-沈陽(yáng)-天津-上海-南寧-重慶-鄭州-石家莊-北京

(2)北京-沈陽(yáng)-哈爾濱-長(zhǎng)春-天津-上海-南寧-重慶-鄭州-石家莊-北京

(3)北京-沈陽(yáng)-長(zhǎng)春-哈爾濱-天津-上海-南寧-重慶-鄭州-石家莊-北京

(4)北京-石家莊-鄭州-重慶-南寧-上海-天津-沈陽(yáng)-長(zhǎng)春-哈爾濱-北京

(5)北京-石家莊-鄭州-重慶-南寧-上海-天津-長(zhǎng)春-哈爾濱-沈陽(yáng)-北京

(6)北京-石家莊-鄭州-重慶-南寧-上海-天津-哈爾濱-長(zhǎng)春-沈陽(yáng)-北京

但是，通過(guò)觀察不難發(fā)現(xiàn)，其中1-3中的路線分別與4-6條中的路線重復(fù)，

(1)北京-哈爾濱-長(zhǎng)春-沈陽(yáng)-天津-上海-南寧-重慶-鄭州-石家莊-北京

(2)北京-沈陽(yáng)-哈爾濱-長(zhǎng)春-天津-上海-南寧-重慶-鄭州-石家莊-北京

(3)北京-沈陽(yáng)-長(zhǎng)春-哈爾濱-天津-上海-南寧-重慶-鄭州-石家莊-北京

這并不影響最后的結(jié)果。

所以，最短路徑一共有6條，長(zhǎng)度均為8512 km。

3 結(jié) 論

通過(guò)C++程序有效地解決了城市間的路徑規(guī)劃問(wèn)題，很實(shí)用。優(yōu)點(diǎn)：節(jié)約了計(jì)算時(shí)間，更直觀地顯示最短路徑，大大提高出行效率。缺點(diǎn)：由于是點(diǎn)的遍歷問(wèn)題，當(dāng)點(diǎn)的數(shù)目過(guò)大。由于算法并不完美的原因，導(dǎo)致最后的運(yùn)算量遠(yuǎn)遠(yuǎn)超過(guò)了該版本C++的分配運(yùn)行的內(nèi)存，會(huì)導(dǎo)致計(jì)算失敗。