歐拉哈密頓通路ppt課件(編輯修改稿)
2025-05-28 02:53 本頁面
【文章內(nèi)容簡介】 沒有度為 0的孤立頂點(diǎn)的無向圖 存在歐拉回路的充要條件 是： (1)圖是連通的； (2)圖中沒有奇度頂點(diǎn) 。 歐拉通路與哈密頓通路 Euler and Hamilton Path [定理 2] 有向圖的歐拉定理： 不含出 /入度為 0的孤立頂點(diǎn)的有向圖具有歐拉通路的充要條件是： （ 1）弱連通； （ 2）除了可能有 2個(gè)頂點(diǎn)，一個(gè)入度比出度大 1，一個(gè)出度比入度大 1，其余頂點(diǎn)出度等于入度。 [推論 ] 不含出 /入度為 0的孤立頂點(diǎn)的有向圖具有歐拉回路的充要條件是： （ 1）弱連通； （ 2）所有頂點(diǎn)出度等于入度。 歐拉通路與哈密頓通路 Euler and Hamilton Path 歐拉通路 /回路的應(yīng)用與推廣： 1） 一筆畫問題 2） 如果奇度頂點(diǎn)個(gè)數(shù)為 2K個(gè) ， 此問題是 K筆畫問題 3） 中國郵遞員問題 4） 電路布線 、 網(wǎng)絡(luò)組播和分子生物學(xué) 歐拉通路與哈密頓通路 Euler and Hamilton Path 歐拉通路 /回路的應(yīng)用與推廣： 1） 一筆畫問題 2） 如果奇度頂點(diǎn)個(gè)數(shù)為 2K個(gè) ， 此問題是 K筆畫問題 3） 中國郵遞員問題 4） 電路布線 、 網(wǎng)絡(luò)組播和分子生物學(xué) 歐拉通路與哈密頓通路 Euler and Hamilton Path Hamilton(哈密頓 )通路問題： ? 1857年發(fā)明的一種游戲 。 ? 在一個(gè)實(shí)心的正十二面體 ， 20個(gè)頂點(diǎn)標(biāo)上世界著名大城市的名字 ， 要求游戲者從某一城市出發(fā) ， 遍歷各城市一次 ， 最后回到原地 。 ? 這就是“繞行世界”問題。即找一條經(jīng)過所有頂點(diǎn)（城市）的基本回路。 歐拉通路與哈密頓通路 Euler and Hamilton Path [定義 1]哈密頓通路 /回路 ： G=(V, E)， G中經(jīng)過 V中所有頂點(diǎn)的基本通路稱為 哈密頓通路 /Hamilton Path， 簡稱 H通路 。 G=(V, E)， G中經(jīng)過 V中所有頂點(diǎn)的基本回路稱為 哈密頓回路 /Hamilton Circuit， 簡稱 H回路 。 注：存在哈密頓回路的圖稱為哈密頓圖 /H圖 歐拉通路與哈密頓通路 Euler and Hamilton Path A B 圖 A 每個(gè)頂點(diǎn)都是奇度的，不存在 E通路，但有 H通路。 圖 B存在 E通路，不存在 H通路。 歐拉通路與哈密頓通路 Euler and Hamilton Path 歐拉通路與哈密頓通路 Euler and Hamilton Path 有哈密頓回路或通路嗎？ 圖 G1 有 H回路；圖 G2 有 H通路，無 H回路； 圖 G3無 H通路，也無 H回路 [定理 3] 設(shè) G=(V,E) 是 n個(gè)頂點(diǎn)的簡單圖， 如果任一對(duì)不相鄰的頂點(diǎn)度之和 ≥n1，則 G中一定有 H通路 (n≥2)。 證明： 1） G一定連通 ，否則 G分為二個(gè)不連通的分圖 G1， G2，其中 G1有 n1個(gè)頂點(diǎn)， G2有 n2個(gè)頂點(diǎn)， G1中每個(gè)頂點(diǎn)度 ≤n11，
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1