aolm離散數(shù)學ppt課件(編輯修改稿)
2025-06-01 07:59 本頁面
【文章內容簡介】 e a h f a c d h e d? 哈密頓 （ Hamilton） 圖 歐拉圖要求遍歷圖中每邊僅一次并回到起點，與此類似的是遍歷圖中的每個結點僅一次并回到起點的問題。 這個問題的起源與一個游戲密切相關。十九世紀中期，世界上第一個給出復數(shù)的代數(shù)表示而非幾何表示的愛爾蘭著名數(shù)學家 William Hamilton 爵士發(fā)明了一種名為 Icosian 的游戲，亦稱為周游世界游戲。該游戲要求在一個十二面體上移動木栓。十二面體由 20 個結點（體的尖角）、 30 條邊（面的邊界）和 12 個面組成，每個面的形狀為五邊形，如下圖所示。在游戲中，每個結點代表一個著名的城市。游戲的目標是尋找一條旅行世界的路線，使得訪問每個城市恰好一次后，再返回到起點城市。在構造路線時，要求沿著連接城市的邊來移動木栓。 后來，這類問題就以 Hamilton 的名字來命名了。 十二面體圖 2 4 7 5 6 8 3 9 10 1 11 12 13 14 15 16 17 18 19 20 十二面體由 20 個結點（體的尖角）、 30 條邊（面的邊界）和 12 個面組成 * 定義 給定圖 G， 若存在一條路經(jīng)過圖中的 每一個結點恰好一次 ， 這條路稱作 Hamilton 路 。 若存在一條回路 ， 經(jīng)過圖中的每一個結點恰好一次 ， 這個回路稱作 Hamilton 回路 。 具有 Hamilton 回路的圖稱為 Hamilton 圖 。 * 定理 （ Hamilton 回路的必要條件）若圖 G＝ (V, E) 具有 Hamilton 回路，則對于結點集 V 的每一個非空子集 S 均有 W(G－ S)≤ 成立。其中 W(G－ S) 是 G－ S 中連通分支數(shù)。 證明：設 C 是 G 的一條 Hamilton 回路，則對于 V 的任何一個非空子集 S 在 C 中刪去 S 中任一結點 a1，則 C－ a1 是連通非回路，若刪去 S 中的另一個結點 a2，則 W(C － a1－ a2)≤2，由歸納法得知 W(C－ S)≤ 同時 C－ S 是 G－ S 的一個生成子圖，因而 W(G－ S)≤W(C－ S) 所以 W(G－ S)≤ SSSNo 定理 作為圖的性質，可以用來判定某些圖是非 Hamilton 圖。右圖是非 Hamilton 圖，因為若取 S＝ {v1, v4}，則 G－ S 中有三個分圖，故 G 不是 Hamilton 圖。 一個非 Hamilton 圖 v5 v7 v1 v2 v3 v6 v7 v4 No 定理 并不總是有效的 ，右圖所示的著名彼得森圖雖然滿足 W(G－ S)≤ ， 但它不是Hamilton圖 。 彼得森圖 S 關于圖中沒有 Hamilton 路的判別目前沒有有效的方法，下面介紹一個說明性的例子。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 A B A B A B B A B A B A A A A B 不存在 Hamilton 路 在上圖 (a) 中，用 A 標記任意結點（比如：結點1），所有與該結點（結點 1）鄰接的結點均標記為 B，繼續(xù)不斷地用 A 標記所有鄰接于標記為 B 的結點、用 B 標記所有鄰接于標記為 A 的結點，直到所有結點標記完畢，如上圖 (b) 所示。如果在圖中有一條 Hamilton 路，那么它必須交替通過標記為 A 的結點和標記為 B 的結點。而圖中所示有 9 個標記 A 的結點和 7 個標記 B 的結點，所以不可能存在 Hamilton 路。 注意，如果標記過程中遇到相鄰結點出現(xiàn)相同標記時，可以在此相鄰結點對應的邊上增加一個結點，標記為相異標記。 雖然 Hamilton 回路在問題形式與歐拉回路頗為相似，
教學課件相關推薦
鄂ICP備17016276號-1