離散數(shù)學(xué)課件圖論(1)(編輯修改稿)
2025-02-14 02:32 本頁面
【文章內(nèi)容簡介】 V1 |. c ? ?e b? a? ?d 無向哈密頓圖的一個必要條件 School of Information Science and Engineering 無向哈密頓圖的一個必要條件 推論 設(shè)無向圖 G=V,E是半哈密頓圖，對于任意的 V1?V且 V1?? 均有 p(G?V1) ? |V1|+1 證 令 ?為 G中起于 u終于 v哈密頓通路，令 G? = G?(u,v) 則 G?為哈密頓圖 . 由定理 ， p(G ? ?V1) ? |V1| 而 p(G?V1) = p(G??V1?(u,v)) ? |V1|+1 School of Information Science and Engineering 幾點(diǎn)說明 ?定理 ，但不是充分條件 ?常利用定理 。 例 2 設(shè) G為 n階無向連通簡單圖，若 G中有割點(diǎn)或橋，則 G不 是哈密頓圖。 證明：設(shè) v為割點(diǎn)，則 p(G?v) ? 2|{v}|=1. K2有橋，它顯然不是哈密頓圖。 除 K2外，其他有橋的圖（連通的）均有割點(diǎn) . 其實，本例對非簡單連通圖也對 . School of Information Science and Engineering 無向哈密頓圖的一個充分條件 定理 設(shè) G是 n階無向簡單圖，若對于任意不相鄰的頂點(diǎn) vi,vj，均有 d(vi)+d(vj) ? n?1 則 G 中存在哈密頓通路 . 推論 設(shè) G為 n (n?3) 階無向簡單圖，若對于 G中任意兩個不相鄰的頂點(diǎn) vi,vj，均有 d(vi)+d(vj) ? n 則 G中存在哈密頓回路，從而 G為哈密頓圖 . School of Information Science and Engineering 幾點(diǎn)說明 ?定理 ，但不是必要條件。 ? 長為 n?1（ n?4）的路徑構(gòu)成的圖不滿足（ ?）條件，但它顯然是半哈密頓圖。 ?定理 ? G為長為 n的圈，不滿足（ ??）條件，但它當(dāng)然是哈密頓圖。 ?由定理 ， Kn（ n?3）均為哈密頓圖。 School of Information Science and Engineering 定理 若 D為 n（ n?2）階競賽圖，則 D中具有哈密頓通路 (注意，競賽圖的基圖是無向完全圖 ) 證明思路：對 n（ n?2）做歸納 . 書 P302,定理 無向哈密頓圖的充分條件 School of Information Science and Engineering 判斷某圖是否為哈密頓圖方法 判斷某圖是否為哈密頓圖至今還是一個難題 . 總結(jié)判斷某圖是哈密頓圖或不是哈密頓圖的某些可行的方法 . 1. 觀察出哈密頓回路 . 例 3 下圖 (周游世界問題 ) 是哈密頓圖 易知 a b c d e f g h i j k l m n p q r s t a 為圖中的一條哈密頓回路 . School of Information Science and Engineering 2．滿足定理 . 例 4 完全圖 Kn (n?3) 中任何兩個頂點(diǎn) u,v，均有 d(u)+d(v) = 2(n?1) ? n（ n?3）， 所以 Kn為哈密頓圖 . 3．破壞定理 . 判斷某圖是否為哈密頓圖方法 School of Information Science and Engineering 設(shè) P是 G中的一條通路， P中所有邊的權(quán)之和稱為 P的長度， 記作 W(P)，即 ???)()()(PEeewPW[定義 ] 給定圖 G = V,E， (G為無向圖或有向圖 )，給定W:E?R (R為實數(shù)集 )，對 G中任意邊 e = (vi,vj) (G為有向圖 時， e = vi,vj)，設(shè) W(e) = wij，稱實數(shù) wij 為邊 e上的 權(quán) ，并將
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1