哈密爾頓圖的判定及應(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在相鄰座位問題上的應(yīng)用..................................................................................54.2在旅行售貨問題上的應(yīng)用.......

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

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

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

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