【正文】 徑已構(gòu)造好的路徑組合成一條路徑。因此充分性得證。就是判斷一個圖形能否一筆畫成 ,實質(zhì)上就是判斷圖形是否存在歐拉路徑和歐拉回路的問題。 第 8章 圖論 (b)我們想知道是否可能將 28塊不同的多米諾骨牌排成一個圓形 ,使得在這個排列中 ,每兩塊相鄰的多米諾骨牌其相鄰的兩個半面是相同的。 第 8章 圖論 圖 ―9 第 8章 圖論 定理 ―5 一個有向連通圖具有歐拉回路 ,當(dāng)且僅當(dāng)它的每個頂點的引入次數(shù)等于引出次數(shù)。證明是類似的 ,不重復(fù)?，F(xiàn)以旋轉(zhuǎn)鼓設(shè)計為 例說明布魯英序列。圖中陰影區(qū)表示用導(dǎo)電材料制成 ,空白區(qū)用絕緣材料制成 ,終端 a、 b和 c是接地或不是接地分別用二進制信號 0或 1表示。試問應(yīng)如何選取這 8個扇形的材料使每轉(zhuǎn)過一個扇形都得到一個不同的二進制信號 ,即每轉(zhuǎn)一周 ,能得到 000到 111的 8個數(shù)。穿程于 G的每個結(jié)點一次且僅一次的回路稱為哈密爾頓回路。 哈密爾頓 ,愛爾蘭數(shù)學(xué)家 ,1859年他首先提出這一類問題。 ) 第 8章 圖論 圖 ―11 第 8章 圖論 定理 ―6 若 G=〈 V,E〉 是哈密爾頓圖 ,則對 V的每個非空真子集 S均成立 : ω(GS)≤｜ S｜ 這里 |S|表示 S中的頂點數(shù) ,ω(GS)表示 G刪去頂點集 S后得到的圖的連通分圖個數(shù)。但 G是由 C和一些不在 C中的邊構(gòu)成的 ,CS是 GS的生成子圖 ,所以 ω(GS)≤ω(CS)≤|S| 應(yīng)用本定理可以判定某些圖不是哈密爾頓圖 ,例如 ,圖 ―12 所示的圖 ,刪去其中 3個黑點 ,即知此圖不符合必要條件 ,因而不是哈密爾頓圖。 第 8章 圖論 圖 ―12 第 8章 圖論 例 4 證明圖 ― 13(a)中的圖沒有哈密爾頓路徑 。繼續(xù)不斷地用 A標記所有鄰接于 B的頂點 ,用 B標記所有鄰接于 A的頂點 ,直到所有頂點標記完 ,得到如圖 ―13( b)所示的圖 ,圖中有 3個頂點標 A和 5個頂點標 B,標號 A和 B崐相差 2個 ,因此不可能存在一條哈密爾頓路徑。 定理 ―7 設(shè) G=〈 V,E〉 是具有 n個頂點的簡單無向圖 ,若在 G中每一對頂點的次數(shù)之和大于等于 n,則在 G中存在一條哈密爾頓回路。設(shè) G是符合題設(shè)條件 ,但不是哈密爾頓圖 ,通過把不相鄰的頂點加邊 ,總可得到一個最大的非哈密爾頓圖 G′。于是必存在兩個相鄰的頂點 vi和 vi1使 v1與 vi,vi1與vn相鄰 ,如圖 ―14 所示。 121 1 1, , ,ki i i? ? ?? ? ?12, ki i i? ? ?第 8章 圖論 圖 ―14 第 8章 圖論 v1與 vi相鄰 ,vn與 vi1相鄰 ,于是 G′存在一條哈密爾頓回路 (v1,v2,…,vi1,vn,vn1,…,vi+1,vi,v1),但這與 G ′是最大的非哈密爾頓圖矛盾。 容易看出定理 ―7 的條件是充分的但非必要。 第 8章 圖論 推論 ―7 在簡單無向圖中 ,若每一頂點的度 數(shù) ,則該圖是哈密爾頓圖。 1 ( 3 )2 nn??第 8章 圖論 一個售貨員希望去訪問 n個城市的每一個 ,開始和結(jié)束于 v1城市。 這個問題用圖論術(shù)語敘述就是 :G=〈 V,E,W〉 是 n個頂點的無向完全圖 ,這里 W是從 E到正實數(shù)集的一個函數(shù) ,對在 V中任意三點 vi,vj,vk滿足 W(i,j)+W(j,k)≥W(i,k) 試求出賦權(quán)圖上的最短哈密爾頓回路 。 (1)選任意點作為始點 ,找出一個與始點最近的點 ,形成一條邊的初始路徑。 (2)設(shè) x表示最新加到這條路徑上的點 ,從不在路徑上的所有點中 ,選一個與 x最鄰近的點 ,把連接 x與此點的邊加到這條路徑中。 第 8章 圖論 圖 ―15 第 8章 圖論 (3)把始點和最后加入的頂點之間的邊放入 ,這樣就得出一個回路 。 第 8章 圖論 二部圖 定義 ― 1若無向圖 G=〈 V,E〉 的頂點集合 V可 以劃分成兩個子集 X和 Y,使 G中的 每一條邊 e的一個端點在 X中 ,另一個端點在 Y中 ,則稱 G為二部圖或偶圖 。 由定義可知 ,二部圖不會有自回路 。 下圖給出 K2,4和 K3,3的圖示。 定義 ―3 給定一個二部圖 G=〈 X,E,Y〉 ,如果 E 的子集 M中的邊無公共端點 ,則稱 M為二部圖 G的一個匹配。 例如 ,下圖中 ,M={(x1,y5),(x3,y1),(x4,y3)}是 G的一個匹配 。 第 8章 圖論 定義 ―4 如果二部圖 G中的一條鏈由不屬于匹 配 M的邊和屬于 M的邊交替組成 ,且鏈的兩端點不是 M中邊的端點 ,那么稱此鏈為 G中關(guān)于匹配 M的交替鏈。 第 8章 圖論 交替鏈可用標記法找出 ,標記法的過程如下 : 首先把 X中所有不是 M的邊的端點用 ()加以標記 ,然后交替進行以下所述的過程 Ⅰ 和 Ⅱ 。對所有 X的新標記過的結(jié)點重復(fù)這一過程。對所有 Y的新標記過結(jié)點重復(fù)這一過程。 (2) 從 x2出發(fā) ,應(yīng)用過程 Ⅰ ,把 y1和 y3標記 (x2)。從 y3出發(fā) ,應(yīng)用過程 Ⅱ ,把 x4標記 (y3)。 第 8章 圖論 在二部圖 G中 ,如果能找出一條關(guān)于匹配 M的交替鏈 γ,則把 γ中屬于 M的邊從 M中刪去 ,而把 γ中不屬于 M的邊添到 M中 ,得到一新集合 M′,此 M′也是 G的匹配。例如在圖 ―2 中作這樣變換后 ,所得的 M′(用粗黑線標出 )如圖 ―3 所示。因此 ,反復(fù)進行這樣的過程 ,直至找不出關(guān)于 M的交替鏈為止 ,就可崐求出 G的最大匹配 ,即 M。 解步驟 、 操作內(nèi)容及 M情況 (1)置 M為 M= (2) 找出一條邊的交替鏈 (x2,y2) M={(x2,y2)} (3)找出一條邊的交替鏈 (x3,y3) M={(x2,y2),(x3,y3)} (4)找出一條邊的交替鏈 (x4,y4) M={(x2,y2),(x3,y3),(x4,y4)} ? ?第 8章 圖論 (5)用標記法找出交替鏈 (x1,y3,x3,y2,x2,y1),進行變換得 M={(x1,y3),(x3,y2),(x2,y1),(x4,y4)}。但已找不到交替鏈。