歐拉哈密頓通路ppt課件-資料下載頁
2025-05-01 02:53本頁面
【正文】 頓通路 Euler and Hamilton Path [定理 4] 狄拉克定理 若 G是帶 n個(gè)頂點(diǎn)的連通簡(jiǎn)單圖 ， n≥3， 且 G中每個(gè)頂點(diǎn)的度都至少為 n/2， 則 G有哈密頓回路 。 要判別一個(gè)圖不存在 H通路 /H回路 ， 也不是很容易的 ， 只能對(duì)無向圖給出一些必要條件： 1) H通路存在必要條件 ： ① 連通 ② 至多只能有二個(gè)頂點(diǎn)的度＜ 2， 其余頂點(diǎn)的度 ≥2。 b c d a 歐拉通路與哈密頓通路 Euler and Hamilton Path 2) H回路存在必要條件 ： 對(duì) V的 任一 非空真子集 S， GS的連通分支個(gè)數(shù) ≤|S|。 歐拉通路與哈密頓通路 Euler and Hamilton Path AA2BBA1BAABBBAB解：取 S={A1, A2} GS存在 3個(gè)連通分支 AA2BBA1BAABBBAB根據(jù) H回路存在的必要條件之二 ，可知 H回路不存在 ！ 歐拉通路與哈密頓通路 Euler and Hamilton Path 應(yīng)用問題之一： Knight’s tour 應(yīng)用問題之二： Gray Code 應(yīng)用問題之三： Tower of Hanoi 歐拉通路與哈密頓通路 Euler and Hamilton Path ? 旋轉(zhuǎn)的指針的位置可以表示成數(shù)字的形式 。 ? 一種方式是把圓周等分成 2n段弧并且用長(zhǎng)度為 n的位串給每段弧賦值 。 格雷碼 Gray Code ? 在指針上用 n個(gè)接觸點(diǎn)來確定指針位置 ， 每個(gè)接觸點(diǎn)用來讀出位置的數(shù)字表示中的一位 格雷碼 Gray Code ? 當(dāng)指針靠近兩段弧的邊界時(shí) ， 讀出指針的位置可能出錯(cuò) 格雷碼 Gray Code 3位都錯(cuò) 最多 1位錯(cuò) ? 可用 n立方體 Qn來為問題建模 ? 弧的滿足要求的標(biāo)記就是求 Qn的一個(gè)哈密頓回路 。 格雷碼 Gray Code Q3 ? 格雷碼是上世紀(jì) 40年代弗蘭克 格雷為把數(shù)字信號(hào)傳送過程中錯(cuò)誤的影響降到最低而發(fā)明的 。 思考題 在某次國(guó)際會(huì)議的預(yù)備會(huì)議中，共有 8人參加，他們來自不同的國(guó)家。已知他們中任何兩個(gè)無共同語言的人中的每一個(gè)，與其余有共同語言的人數(shù)之和大于或等于 8，問能否將這 8個(gè)人排在圓桌旁，使其任何人都能與兩邊的人交談。 思考題 解：設(shè) 8個(gè)人分別為 v1,v2,…, v8，作無向簡(jiǎn)單圖 G=(V,E)，其中V={v1,v2,…, v8}， ?vi,vj∈ V，且 i≠j，若 vi與 vj有共同語言，就在 vi,vj之間連無向邊 (vi,vj)，由此組成邊集合 E，則 G為 8階無向簡(jiǎn)單圖， ?vi∈ V， d(vi)為與 vi有共同語言的人數(shù)。 由已知條件可知， ?vi,vj∈ V且 i≠j，均有 d(vi)+d(vj)≥8。 由定理 3可知， G中存在哈密頓回路，設(shè) C＝ vi1vi2… vi8為 G中一條哈密頓回路，按這條回路的順序安排座次即可。 作 業(yè) P274： 17
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1