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