哈密爾頓圖的判定及應(yīng)用（determination and application of hamilton graph）

1、目錄中文摘要.............................................................................................................1中文關(guān)鍵詞...................................................................................................

2、.......1英文摘要.............................................................................................................1英文關(guān)鍵詞.............................................................................................

3、.............11引言..............................................................................................................12相關(guān)概念.......................................................................................

4、.................23哈密爾頓圖的判定...........................................................................................23.1定義判定法.............................................................................................

5、........33.2充分條件判定法...............................................................................................33.3必要條件判定法...............................................................................................

6、44哈密爾頓圖的應(yīng)用...........................................................................................54.1在相鄰座位問(wèn)題上的應(yīng)用..................................................................................54.2在旅行售貨問(wèn)題上的應(yīng)用.......

7、...........................................................................65結(jié)論...............................................................................................................8參考文獻(xiàn).........................

8、....................................................................................811引言引言哈密爾頓在1857年發(fā)明了一個(gè)游戲它是由一個(gè)木制的正十二面體構(gòu)成將當(dāng)時(shí)很多的城市標(biāo)在每個(gè)棱角的位置.游戲目的是“環(huán)球旅行”即經(jīng)過(guò)每座城市恰好一次然后回到原點(diǎn)為了方便知曉經(jīng)過(guò)的城市在每個(gè)棱角上放上一個(gè)釘子將經(jīng)過(guò)的城市用線連接由此可以獲得旅程的直觀表示.正十二面

9、體的頂點(diǎn)與棱的關(guān)系可以用平面上的圖來(lái)表示：把正十二面體的頂點(diǎn)與棱分別對(duì)應(yīng)圖的頂點(diǎn)與邊就得到圖1中的正十二面體圖這個(gè)游戲就會(huì)有很多答案如圖2就是其中一種答案也就是一個(gè)哈密爾頓圖哈密爾頓圖的定義是怎樣的？它在生產(chǎn)生活中又有哪些應(yīng)用呢？下面將會(huì)給出哈密爾頓圖的定義、判定方法及相關(guān)應(yīng)用.2相關(guān)概念相關(guān)概念定義1二元組稱為圖.其中是非空集合稱為頂點(diǎn)集是諸??????GEGV??GV??GE??GV頂點(diǎn)之間邊的集合.常用表示圖.??EVG?定義2圖

10、中與頂點(diǎn)相關(guān)聯(lián)的邊數(shù)(每個(gè)環(huán)計(jì)算二次)稱為頂點(diǎn)的度.記??EVGvv或.??vdG??vd定義3在一個(gè)圖中如果我們就說(shuō)邊連接頂點(diǎn)和稱????????GGEGVG????uveG??euv和是的端點(diǎn)也稱和相鄰?fù)瑫r(shí)也稱(或)與關(guān)聯(lián).uveuvuve定義4如果對(duì)圖的任何兩個(gè)頂點(diǎn)與中存在一條路能稱是連??EVG?uvG??vu?G通圖否則稱為是非連通圖.定義5圖的一個(gè)點(diǎn)邊交替出現(xiàn)的有限序列??EVG?kkkvevevevevW1322110??