南大面試課程離散課件二24圖

哈密爾頓圖離散數(shù)學第24講上一講內容的回顧歐拉回路與歐拉圖歐拉通路與半歐拉圖歐拉圖的充分必要條件半歐拉圖的充分必要條件構造歐拉回路的Fleury算法隨機歐拉圖哈密爾頓圖哈密爾頓回路與哈密爾頓圖哈密爾頓通路與半哈密爾頓圖哈密爾頓圖的必要條件哈密爾頓圖的充分條件尋找哈密爾頓回路旅行推銷員問題(TSP)周游世界的游戲1859年英國數(shù)學家哈密爾頓提出了一種名為

“周游世界”的游戲：用一個正十二面體的二十個頂點代表二十個大城市，要求沿著棱，從一個城市出發(fā)，經(jīng)過每個城市恰好一次，然后回到出發(fā)點。哈密爾頓回路和哈密爾頓通路定義：經(jīng)過圖G中所有頂點的初級回路稱為哈密爾頓回路，若G中含哈密爾頓回路，則稱G為哈密爾頓圖。

定義：經(jīng)過圖G中所有頂點的初級通路稱為哈密爾頓通路，若G中含哈密爾頓通路，但不含哈密爾頓回路，則稱G為半哈密爾頓圖。哈密爾頓圖的必要條件注意：任何一個哈密爾頓圖都可以看成是一個初級回路再加上連接該回路上頂點對的若干條邊。哈密爾頓圖的必要條件任何一個哈密爾頓圖都可以看成是一個初級回路再加上連接該回路上頂點對的若干條邊從初級回路上刪除k個頂點，最多形成k個連通分支從一個哈密爾頓圖中刪除K個頂點，最多形成k個連通分支哈密爾頓圖的必要條件任何一個哈密爾頓圖都可以看成是一個初級回路再加上連接該回路上頂點對的若干條邊從初級回路上刪除k個頂點，最多形成k個連通分支從一個哈密爾頓圖中刪除K個頂點，最多形成k個連通分支向一個圖中已有的頂點之間加邊不會增加連通分支。因此：若G是哈密爾頓圖，則對VG的任意非空真子集V1，圖G-V1的連通分支數(shù)不大于V1中的元素個數(shù)。哈密爾頓圖的必要條件若G是哈密爾頓圖，則對VG的任意非空真子集V1，圖G-V1的連通分支數(shù)不大于V1中的元素個數(shù)。證明要點：假設G-V1的連通分支數(shù)為k；模擬哈密爾頓回路C：每次離開某個連通分支，必定進入某個V1中節(jié)點每次進入的V1節(jié)點均不相同至少進入K個V1節(jié)點連通K個分支的C含有K個V1節(jié)點必要條件的應用必要條件的局限性必要條件一般只能判定一個圖不是哈密爾頓圖右圖(Petersen圖)滿足上述必要條件。Petersen圖不是哈密爾頓圖。如何使得一個非哈密爾頓圖變成哈圖？邊越多，越容易！所有的點的度越大越容易！也許平均度達到一定程度？也許最小度達到一定程度？頂點對度數(shù)和與圖的連通只要任意頂點對的度數(shù)和足夠大，圖一定連通。設G是階不小于2的無向簡單圖，若G中任意不相鄰的頂點對u,v均滿足：(條件*)d(u)+d(v)?n-1

(n是G中頂點個數(shù))則G是連通圖。證明：假設G不連通，則至少含2個連通分支，設為G1,G2。取x?VG1,y?VG2,則：d(x)+d(y)￡(n1-1)+(n2-1)￡n-2(其中ni是Gi的頂點個數(shù))，矛盾。將極大路徑改造成回路v1v2vivkVi+1vj若圖G滿足條件(*),設G=v1v2…vk-1vk是G中不含所有頂點的極大路徑(k<n),

則G中所有頂點可構成初級回路。若v1,vk相鄰，結論成立。若v1,vk不相鄰，令S={vi|v1與vi+1相鄰},T={vj|vj與vk相鄰}注意：|S|=d(v1)，|T|=d(vk)極大路徑使然|S|+|T|=

d(v1)+d(vk)

?n-1意味著什么？|S|+|T|=

d(v1)+d(vk)?n-1若圖G滿足條件(*),設G=v1v2…vk-1vk是G中不含所有頂點的極大路徑(k<n),則G中所有頂點可構成初級回路。v1vivi+1vkv2vkˇS T,

\|S

T|￡k-1<n-1,而根據(jù)容斥原理|S

T|=|S|+|T|-|S T|>0,

即S T非空令vi?S

T,

則vi+1與v1相鄰，vi與vk相鄰。于是C=v1…vivkvk-1…vi+1v1是包含G中所有頂點的初級回路。半哈密爾頓圖的充分條件v1vivi+1vkvj-1

vj條件*是半哈密爾頓圖的充分條件。可以證明：若條件*成立，圖中的最大路徑一定是哈密爾頓通路。假設G=v1v2…vk-1vk是一條最大路徑，但k<n,則可以將它改造為一初級回路C。設vk+1是C以外的頂點。因為G是連通圖，vk+1與C中的頂點必有通路，設其中最短路徑與G的交點是vj(顯然異于v1,vk)。則

G

‘=vk+1…vj…vivk

vk-1…vi+1v1…vj-1是通路G的擴大。矛盾。vk+1哈密爾頓圖的充分條件G是階不小于3的無向簡單圖，若G中任意不相鄰的頂點對u,v均滿足：d(u)+d(v)?n

(n是G中頂點個數(shù))，則G是哈密爾頓圖證明：G是半哈密爾頓圖，設G=v1v2…vn-1vn是G中的哈密爾頓通路。若v1,vk

相鄰，結論成立。否則，令S={vi|v1

與vi+1

相鄰}，T={vj|vj與vk相鄰}；注意：|S|+|T|=d(v1)+d(vn)?n,vnˇS T,

\

|S

T|￡k-1<n,

\

|S

T|=|S|+|T|-|S T|>0,

即S

T非空，令vi?S T,

則vi+1與v1相鄰，vi與vn相鄰。于是C=v1…vivnvn-1…vi+1v1是哈密爾頓回路。v1vivi+1vnv2有關哈密爾頓圖充分條件的討論為什么前提條件中必須包括n?3，而對半哈密爾頓圖只需要n?2不相鄰節(jié)點顯然：d(v)?n/2是d(u)+d(v)?n的充分條件，因此，也是哈密爾頓圖的充分條件加邊總可以使非哈密爾頓圖變成哈密爾頓圖，(而且，這過程中一定存在一個臨界狀態(tài))。但是：如果只在滿足d(u)+d(v)?n

的u,v之間加邊，圖的哈密爾頓性質不會改變。棋盤上的哈密爾頓回路問題在4·4或5·5的縮小了的國際象棋棋盤上，馬

(Knight)不可能從某一格開始，跳過每個格子一次，并返回起點。安排考試日程問題:在6天里安排6門課–A,B,C,D,E,F-的考試，每

天考1門。假設每人選修課的情況有如下的4類：DCA，BCF，EB，AB。如何安排日程，使得沒有人必須連續(xù)兩天有考試？ABCDEFABCDEF再安排考試七天內安排七門課的考試，要求同一個老師教授的課程不要連續(xù)安排。試證明：如果沒有教師同時教授4門及以上課程，這種安排是能實現(xiàn)的。點代表什么？線代表什么？問題是什么？旅行推銷員(TSP)問題問題：n個城市間均有道路，但距離不等，旅行推銷員從某地出發(fā)，走過其它n-1個城市，且只經(jīng)過一次，如何選擇最短路線？數(shù)學模型：構造無向帶權圖G，VG中的元素對應于每個城市，EG中每個元素對應于城市之間的道路，道路長度用相應邊的權表示。則問題的解對應于G中包含所有邊的權最小的哈密爾頓回路。G是帶權完全圖，總共有n!/2條哈密爾頓回路。因此，問題是如何從這n!/2條中找出最短的一條。(給你一點感覺：含20個頂點的完全圖中不同的哈密爾頓回路有約

6000萬億條-(1.21645·1017)/2，若機械地檢查，每秒處理10萬條，需2萬年。)TSP:

一個并非最佳的近似算法過程找“較好的”哈密爾頓回路(總選關聯(lián)的最小權邊)改進：如果在已有回路中W(vi,vj)+W(vi+1,vj+1)<W(vi,vi+1)+ W(vj,vj+1),則分別用邊vivi+1和vjvj+1替代vivj和vi+1vj+1。abce1412967851311d10從a

出發(fā)的“較好的”回路，長度：8aa40dceb7

6591410aadceb765910經(jīng)改進的回路

，長度：37作業(yè)pp.303-8-111420Sir

WilliamHamilton(1805-65)愛爾蘭歷史上最偉大的科學家。關于哈密爾頓早期的才能的傳說，讀起來象一篇拙劣的虛構的故事，但它是真實的。(例如，在十歲時，他差不多掌握了大多數(shù)主要東方語言)哈密爾頓在進大學以前從未上過學…(他)輕而易舉地取得第一名，進入三一學院?！髮W生涯的結束，比它開始還要更令人驚奇；…都柏林大學理事會一致選舉當時22歲的大學生哈密爾頓為教授。在23歲時，他發(fā)表了他還是一個17歲的孩子時作出的“奇怪的發(fā)現(xiàn)”，…即《光線系統(tǒng)理論》第一部分，這是一篇偉大的杰作，它對于光學，就象拉格郎日的《分析力學》之于力學。哈密爾頓最深刻的悲劇既不是酒精，也不是他的婚姻，而是他頑固地相信，四元數(shù)是解決物質宇宙的數(shù)學關鍵?！瓘膩頉]有一個偉大的數(shù)學家這樣毫無希望地錯誤過。摘自貝爾：《數(shù)學精英》“我長期以來欣賞托勒密對他偉大的天文學大師希巴克斯的描繪：‘一個熱愛勞動和熱愛真理的人’。但愿我的墓志銘也如此?！?威廉?哈密爾頓閉合圖定義：圖G中任意不相鄰u,v?VG,d(u)+d(v)?|VG|。令

G’=G+e(u,v).不斷重復該動作，直至找不到u,v節(jié)點。則最終結果稱為G的閉合圖，記為C(G)。注意：可以認為C(G)是在G的基礎上不斷在滿足d(u)+d(v)?|VG|的頂點對之間加邊所得。圖G的閉合圖是唯一的設G1,G2

均為G的閉合圖，其構造過程中加的邊依次為e1,e2,…em和f1,f2,…fn。假設ek+1=uv是第一個不在G2中的邊，則H=G+{e1,e2,…ek}同為G1,G2的子圖。在構造G1時加ek+1說明在H中u,v不相鄰，且d(u)+d(v)?|VG|,顯然該條件在G2中也成立，矛盾。閉合圖與哈密爾頓圖的判定圖G是哈密爾頓圖當且僅當C(G)是哈密爾頓圖。只須證明在構造閉合圖(加邊)過程中的每一步，圖的哈密爾頓性質均雙向保持若u,v?VG,u,v不相鄰，且d(u)+d(v)?|VG|，則G是哈密爾頓圖當且僅當G+e(u,v)是哈密爾頓圖。必要性顯然。反之，若G+{uv}是哈密爾頓圖，但G不是，則G是半哈密爾頓圖，且uv-路徑是哈密爾頓通路，由

d(u)+d(v)?|VG|，可以將uv-路徑改造成哈密爾頓回路，