[科普中國(guó)]-哈密頓圈多面體

哈密頓圈多面體(Hamiltonian circuit polytope)是一種特殊的多面體。它是由哈密頓圈導(dǎo)出的多面體。它的頂點(diǎn)相應(yīng)一個(gè)圖上的哈密頓圈的鄰接矩陣。

概念哈密頓圈多面體(Hamiltonian circuit polytope)是一種特殊的多面體。它是由哈密頓圈導(dǎo)出的多面體。它的頂點(diǎn)相應(yīng)一個(gè)圖上的哈密頓圈的鄰接矩陣。因?yàn)槿魏我粋€(gè)圖G的哈密頓多面體均為與G同階的完全圖Kn(n為G的階)的哈密頓多面體的一個(gè)面，所以通常所說(shuō)的哈密頓多面體均指完全圖的哈密頓多面體。這時(shí)，Kn的哈密頓圈的集合與如下的方程和不等式組解集確定的多面體整頂點(diǎn)的集合之間有一個(gè)一一對(duì)應(yīng)關(guān)系：

其中，W為Kn關(guān)聯(lián)矩陣，e=(1，1，…，1)為一個(gè)n維向量，x=(x1，x2，…，xε)，ε=n(n-1)/2，為ε維向量，t表示向量的轉(zhuǎn)置。由此，哈密頓多面體就是上面方程和不等式組整數(shù)解集的凸包。任何一個(gè)哈密頓圈均相應(yīng)旅行售貨員問(wèn)題(參見(jiàn)“旅行售貨員問(wèn)題”)的一個(gè)可行解。也可以說(shuō)，哈密頓多面體為旅行售貨員問(wèn)題所有可行解的凸包。若將Kn用K*n代替，即將Kn的每一邊用兩個(gè)有向邊代替，在K*n上考查有向哈密頓圈，則在K*n上的所有有向哈密頓圈的鄰接矩陣的凸包稱(chēng)為有向哈密頓多面體。若在旅行售貨員問(wèn)題中，將可行解限制在有向哈密頓圈上，則這時(shí)被稱(chēng)為有向旅行售貨員問(wèn)題，或非對(duì)稱(chēng)旅行售貨員問(wèn)題。相應(yīng)地，原旅行售貨員問(wèn)題也稱(chēng)為對(duì)稱(chēng)旅行售貨員問(wèn)題。由此，有向哈密頓多面體也可以說(shuō)是非對(duì)稱(chēng)旅行售貨員問(wèn)題所有可行解的凸包。

哈密頓圈問(wèn)題圖論中著名的難題之一。設(shè)有一個(gè)圖，若其上存在一個(gè)圈，這個(gè)圈包含該圖上的每一節(jié)點(diǎn)，則稱(chēng)該圈為哈密頓圈，這個(gè)圖稱(chēng)為哈密頓圖。哈密頓圈問(wèn)題可敘述為：什么樣的圖為哈密頓圖，或者說(shuō)判斷一個(gè)圖是哈密頓圖的行之有效的充分必要條件是什么。目前這一問(wèn)題尚未解決。關(guān)于哈密頓圈的研究，最早是歐拉(Euler，L.)研究騎士(相當(dāng)于中國(guó)象棋中的馬)從棋盤(pán)上的某一位置出發(fā)，走遍所有可能的位置且每個(gè)位置只通過(guò)一次后，回到原來(lái)的位置。而哈密頓(Hamilton，W.R.)研究環(huán)游世界的游戲是在歐拉之后近一個(gè)世紀(jì)，然而卻由此開(kāi)始引起人們對(duì)于這個(gè)問(wèn)題的注意。實(shí)際上，哈密頓的游戲就是，在一個(gè)正十二面體上，從一個(gè)頂點(diǎn)開(kāi)始沿著棱走遍所有的十二個(gè)頂點(diǎn)回到原地，使得每一頂點(diǎn)只通過(guò)一次。就是在十二面體相應(yīng)的圖上求一個(gè)哈密頓圈。若一個(gè)圖上存在一條路，這條路包含該圖上的所有節(jié)點(diǎn)，則稱(chēng)該圖為可跡圖，稱(chēng)這樣的路為哈密頓路。若對(duì)于一個(gè)圖上的每一節(jié)點(diǎn)，存在一個(gè)以該節(jié)點(diǎn)為始點(diǎn)的哈密頓路，則稱(chēng)該圖為齊次可跡圖。一個(gè)圖被稱(chēng)為哈密頓連通圖，若對(duì)于這圖上任何兩節(jié)點(diǎn)，存在一條哈密頓路連結(jié)這兩節(jié)點(diǎn)。稱(chēng)一個(gè)圖為亞哈密頓圖，若從這圖上去掉無(wú)論哪一節(jié)點(diǎn)，所得的圖都是哈密頓圖。稱(chēng)一個(gè)圖為亞可跡圖，若從這圖上去掉無(wú)論哪一節(jié)點(diǎn)，所得的圖都是可跡圖。

哈密頓圖1859年，英國(guó)數(shù)學(xué)家哈密頓提出一種名為“周游世界”的游戲。他用正十二面體(如圖1)的20個(gè)頂點(diǎn)代表20個(gè)大城市，要求沿著棱從一個(gè)城市出發(fā)，經(jīng)過(guò)每個(gè)城市恰好一次，然后回到出發(fā)點(diǎn)。

這個(gè)游戲曾經(jīng)風(fēng)靡一時(shí)。為了清楚起見(jiàn)，我們作一個(gè)平面圖(如圖2)，與這個(gè)十二面體的頂點(diǎn)和棱所組成的圖同構(gòu)，則圖中粗的邊組成的圈就是一個(gè)所求的路線。我們還可以找到其他的路線。

一般地，在一個(gè)給定的圖中，若存在一條回路，經(jīng)過(guò)每個(gè)頂點(diǎn)恰好一次，則這個(gè)回路稱(chēng)為哈密頓回路;若一個(gè)圖中可以找到一個(gè)哈密頓回路，則這個(gè)圖稱(chēng)為哈密頓圖。表面上看哈密頓圖的概念與歐拉圖的概念非常相似，但兩者迥然不同?？梢哉业揭粋€(gè)歐拉圖但不是哈密頓圖的例子，也可以找到一個(gè)哈密頓圖但不是歐拉圖的例子。

對(duì)哈密頓圖的判定問(wèn)題，迄今還沒(méi)有像歐拉圖那樣能找到一個(gè)很漂亮的充分必要條件。奧爾給出了一個(gè)很重要的充分條件：G為簡(jiǎn)單圖，頂點(diǎn)數(shù)n≥3，且對(duì)每一對(duì)不相鄰的點(diǎn)u，v，有：

這里degu表示與u相關(guān)聯(lián)的邊數(shù)，則G為哈密頓圖。由此還可以得到一個(gè)推論：G為簡(jiǎn)單圖，頂點(diǎn)數(shù)n≥3，若對(duì)G中任何點(diǎn)u，有：degu≥n/2，則G為哈密頓圖。

哈密頓英國(guó)數(shù)學(xué)家、物理學(xué)家。生于愛(ài)爾蘭都柏林(Dublin)，卒于都柏林。他自幼才智過(guò)人，5歲時(shí)能讀拉丁語(yǔ)、希臘語(yǔ)和希伯來(lái)語(yǔ)，14歲時(shí)已學(xué)會(huì)12種語(yǔ)言。1823年入都柏林三一學(xué)院學(xué)習(xí)。1827年被聘為該校天文學(xué)教授，并獲得皇家天文學(xué)家的稱(chēng)號(hào)。1837—1845年任愛(ài)爾蘭皇家學(xué)院院長(zhǎng)，并被選為多個(gè)科學(xué)院和學(xué)術(shù)機(jī)構(gòu)的成員。1836年獲倫敦皇家學(xué)會(huì)皇家勛章。

哈密頓早年曾精讀牛頓(Newton，I.)和拉普拉斯(Laplace，P.-S.)的著作，1822年撰文指出拉普拉斯的《天體力學(xué)》中的一個(gè)錯(cuò)誤，從此開(kāi)始數(shù)學(xué)研究。他對(duì)數(shù)學(xué)的主要貢獻(xiàn)是創(chuàng)立了四元數(shù)理論和發(fā)展了變分法和微分方程理論。1835年，撰文詳細(xì)討論復(fù)數(shù)x+iy的性質(zhì)，進(jìn)而試圖尋找三維“復(fù)數(shù)”，由此導(dǎo)致創(chuàng)立了形如a+bi+cj+dk(a，b，c，d為實(shí)數(shù))的所謂四元數(shù)，這是一種不同于實(shí)數(shù)系和復(fù)數(shù)系的新數(shù)系。四元數(shù)的出現(xiàn)，深化了人們對(duì)“數(shù)”的認(rèn)識(shí)，推動(dòng)了向量代數(shù)、向量分析和物理學(xué)的發(fā)展。哈密頓用分析的方法研究幾何光學(xué)，引入了特征函數(shù)概念，并利用這一概念和最小作用原理(亦稱(chēng)哈密頓原理)把光學(xué)和動(dòng)力學(xué)的問(wèn)題轉(zhuǎn)化為變分法問(wèn)題。他建立的動(dòng)力學(xué)方程稱(chēng)為“哈密頓正則方程”，其中以廣義坐標(biāo)和廣義動(dòng)量作為獨(dú)立變量，代表總能量的函數(shù)H稱(chēng)為“哈密頓函數(shù)”。這些結(jié)果在現(xiàn)代物理學(xué)中獲得廣泛應(yīng)用。他的主要著作有《四元數(shù)講義》(1853)、《光束論》(1827)和《動(dòng)力學(xué)一般方法》(1834)等。1

本詞條內(nèi)容貢獻(xiàn)者為:

李宗秀 - 副教授 - 黑龍江財(cái)經(jīng)學(xué)院