離散數(shù)學(xué)課件圖論(1)(參考版)
2025-01-21 02:32本頁面
【正文】 ?由定理 ， Kn（ n?3）均為哈密頓圖。 ? 長為 n?1（ n?4）的路徑構(gòu)成的圖不滿足（ ?）條件，但它顯然是半哈密頓圖。 證明：設(shè) v為割點，則 p(G?v) ? 2|{v}|=1. K2有橋，它顯然不是哈密頓圖。 (4)既不是哈密頓圖，也不是半哈密頓圖 定理 :(必要條件 ) 若圖 G=V,E有 H回路 ,則對 V的任何非空子有限集 V1, 均有 p(G?V1) ? |V1| , 其中 p(G?V1)是從 G中刪去 V1中所有結(jié)點及與這些結(jié)點關(guān)聯(lián)的邊所得到的子圖的連通分支數(shù) . 證明 :設(shè) C是圖 G的一條 H回路 ,則對于 V的任何非空子集 V1, 在 C中刪去 V1中任意一個結(jié)點 v1后 , 則 Cv1仍是連通的路 , 若再刪去 V1中的另一個結(jié)點 v2, 則 p (Cv1 v 2)≤2, 若 | V1 |=n 則刪去 V1中的 n個結(jié)點 ,有 p (Cv1 v 2 ...vn)≤n, 所以 p(Cv1 v 2 ...vn)≤| V1 | . 因為 C是 H回路 ,所以它包含了 G的所有結(jié)點 , 即 C是 G的生成子圖 . 所以 C V1 也是 G V1 的生成子圖 , 故 p (G V1)≤| V1 |. 用此定理可以判斷一個圖不是 H圖 . 如右圖 G 取 V1 ={c} 不滿足 p (G V1)≤| 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 幾點說明 ?定理 ，但不是充分條件 ?常利用定理 。 School of Information Science and Engineering 實例 在上圖中， (1),(2) 是哈密頓圖 。 證明： 必要性簡單 . 充分性（利用定理 151） 設(shè) u,v為 G 中的兩個奇度頂點，令 G ? =G?(u,v) 則 G ? 連通且無奇度頂點，由定理 151知 G ?為歐拉圖，因而 存在歐拉回路 C，令 ?=C?(u,v) 則 ? 為 G 中歐拉通路 . 理解： G有兩個奇數(shù)度結(jié)點：就從一個奇數(shù)度結(jié)點出發(fā)，每當(dāng)?shù)竭_(dá)一個偶數(shù)度結(jié)點，必然可以再經(jīng)過另一條邊離開此結(jié)點，如此重復(fù)下去，經(jīng)過所有邊后到達(dá)另一個奇數(shù)度結(jié)點。 由 vi 的任意性，結(jié)論為真。 (1) G 連通顯然。 ?環(huán)不影響圖的歐拉性。 說明： ?規(guī)定平凡圖為歐拉圖。 [歐拉圖 ] 有歐拉回路的圖。 School of Information Science and Engineering 第十五章 歐拉圖與哈密頓圖 ?主要內(nèi)容 ? 歐拉圖 ? 哈密頓圖 ? 帶權(quán)圖與貨郎擔(dān)問題 School of Information Science and Engineering 歐拉圖 歷史背景：哥尼斯堡七橋問題與歐拉圖 A B C D e1 e5 e7 e6 e3 e4 e2 A B C D School of Information Science and Engineering 歐拉圖定義 [歐拉通路 ] 經(jīng)過圖中每條邊一次且僅一次行遍所有頂點的通路。 [歐拉回路 ] 經(jīng)過圖中每條邊一次且僅一次行遍所有頂點的回路。 [半歐拉圖 ] 有歐拉通路而無歐拉回路的圖。 ?歐拉通路是生成的簡單通路，歐拉回路是生成的簡單回路。
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1