【正文】 但已找不到交替鏈。因此 ,反復(fù)進(jìn)行這樣的過程 ,直至找不出關(guān)于 M的交替鏈為止 ,就可崐求出 G的最大匹配 ,即 M。 第 8章 圖論 在二部圖 G中 ,如果能找出一條關(guān)于匹配 M的交替鏈 γ,則把 γ中屬于 M的邊從 M中刪去 ,而把 γ中不屬于 M的邊添到 M中 ,得到一新集合 M′,此 M′也是 G的匹配。 (2) 從 x2出發(fā) ,應(yīng)用過程 Ⅰ ,把 y1和 y3標(biāo)記 (x2)。對所有 X的新標(biāo)記過的結(jié)點(diǎn)重復(fù)這一過程。 第 8章 圖論 定義 ―4 如果二部圖 G中的一條鏈由不屬于匹 配 M的邊和屬于 M的邊交替組成 ,且鏈的兩端點(diǎn)不是 M中邊的端點(diǎn) ,那么稱此鏈為 G中關(guān)于匹配 M的交替鏈。 定義 ―3 給定一個(gè)二部圖 G=〈 X,E,Y〉 ,如果 E 的子集 M中的邊無公共端點(diǎn) ,則稱 M為二部圖 G的一個(gè)匹配。 由定義可知 ,二部圖不會有自回路 。 第 8章 圖論 圖 ―15 第 8章 圖論 (3)把始點(diǎn)和最后加入的頂點(diǎn)之間的邊放入 ,這樣就得出一個(gè)回路 。 (1)選任意點(diǎn)作為始點(diǎn) ,找出一個(gè)與始點(diǎn)最近的點(diǎn) ,形成一條邊的初始路徑。 1 ( 3 )2 nn??第 8章 圖論 一個(gè)售貨員希望去訪問 n個(gè)城市的每一個(gè) ,開始和結(jié)束于 v1城市。 容易看出定理 ―7 的條件是充分的但非必要。于是必存在兩個(gè)相鄰的頂點(diǎn) vi和 vi1使 v1與 vi,vi1與vn相鄰 ,如圖 ―14 所示。 定理 ―7 設(shè) G=〈 V,E〉 是具有 n個(gè)頂點(diǎn)的簡單無向圖 ,若在 G中每一對頂點(diǎn)的次數(shù)之和大于等于 n,則在 G中存在一條哈密爾頓回路。 第 8章 圖論 圖 ―12 第 8章 圖論 例 4 證明圖 ― 13(a)中的圖沒有哈密爾頓路徑 。 ) 第 8章 圖論 圖 ―11 第 8章 圖論 定理 ―6 若 G=〈 V,E〉 是哈密爾頓圖 ,則對 V的每個(gè)非空真子集 S均成立 : ω(GS)≤｜ S｜ 這里 |S|表示 S中的頂點(diǎn)數(shù) ,ω(GS)表示 G刪去頂點(diǎn)集 S后得到的圖的連通分圖個(gè)數(shù)。穿程于 G的每個(gè)結(jié)點(diǎn)一次且僅一次的回路稱為哈密爾頓回路。圖中陰影區(qū)表示用導(dǎo)電材料制成 ,空白區(qū)用絕緣材料制成 ,終端 a、 b和 c是接地或不是接地分別用二進(jìn)制信號 0或 1表示。證明是類似的 ,不重復(fù)。 第 8章 圖論 (b)我們想知道是否可能將 28塊不同的多米諾骨牌排成一個(gè)圓形 ,使得在這個(gè)排列中 ,每兩塊相鄰的多米諾骨牌其相鄰的兩個(gè)半面是相同的。因此充分性得證。 第 8章 圖論 并且因?yàn)樵瓉淼膱D是連通的 ,因此 ,這個(gè)子圖必與我們已畫過的路徑在一個(gè)點(diǎn)或多個(gè)點(diǎn)相接。對于偶數(shù)次數(shù)的頂點(diǎn) ,通過一條邊進(jìn)入這個(gè)頂點(diǎn) ,總可通過一條未畫過的邊離開這個(gè)頂點(diǎn)。因此必要性得證。 證必要性。穿程于圖 G的每條邊一次且僅一次的回路 ,稱為歐拉回路 ,具有歐拉回路的圖稱為歐拉圖。古時(shí)城中居民 熱衷于一個(gè)問題 :游人從任一地點(diǎn)出發(fā) ,怎樣才能做到穿過每座橋一次且僅一 次后又返回原出發(fā)地。然后計(jì)算 : D(v2)=min(+∞,2+3)=5 D(v3)=min(+∞,+∞)=+∞ D(v4)=min(10,2+7)=9 如此類推 ,直至 T= 終止 。 (b)如果從 a到 t有一條最短路徑 ,它從 a到 x不包含 T′中的結(jié)點(diǎn) ,接著是邊 W(x,t),在此情況下 ,D′(t)是D(x)+W(x,t)。 第 8章 圖論 其次說明計(jì)算 D(t)的方法。 D(t)表示從 a到 t的不包含 T中其它結(jié)點(diǎn)的最短通路的長度 ,但 D(t)不一定是從 a到 t的距離 ,因?yàn)閺?a到 t可能有包含 T中另外結(jié)點(diǎn)的更短通路。 初始時(shí) ,S={a},T=VS。若 i和 j之間沒有邊 ,那么 W(i,j)=∞。 第 8章 圖論 強(qiáng)連通的也一定是單向連通和弱連通的 ,單向連通的一定是弱連通的 ,但其逆均不真 。 第 8章 圖論 圖 ―2 一個(gè)無向圖或者是一個(gè)連通圖 ,如圖 ―2( a)所示 ,或者是由若干個(gè)連通分圖組成 ,如圖 ―2( b)所示。 如果從 vi到 vj存在一條路徑 ,則稱 vj從 vi可達(dá)。 注意 ,在有向圖中 ,d(vi,vj)不一定等于 d(vj,vi),但一般地滿足以下性質(zhì) : (1) d(vi,vj)≥0。 基本路徑的長度比所經(jīng)結(jié)點(diǎn)數(shù)少 1,圖中共 n個(gè)結(jié)點(diǎn) ,故基本路徑長度不超過 n1。 (但注意習(xí)慣上不定義長度為 0的回路。 第 8章 圖論 在無向圖上 ,以上各術(shù)語的定義完全類似 ,故不重復(fù) 。 基本路徑也一定是簡單路徑。 圖 ― 11是 4個(gè)結(jié)點(diǎn)的有向完全圖和無向完全圖的圖示 。 (3) 若子圖 G′中沒有孤立結(jié)點(diǎn) ,G′由 E′唯一確定 ,則稱G′為由邊集 E′導(dǎo)出的子圖 。 (1) 如果 V′ V和 E′ E,則稱 G′是 G的 子圖 。 ?第 8章 圖論 除以上 4種運(yùn)算外 ,還有以下兩種操作 : (1) 刪去圖 G的一條邊 e。 (2)G1與 G2的交 ,定義為圖 G3＝ 〈 V3,E3〉 , 其中 V3=V1∩V2,E3=E1∩E2,記為 G3=G1∩G2。例如下圖中 (a)、 (b)兩圖雖然滿足以上3條件 ,但不同構(gòu)。 第 8章 圖論 兩圖同構(gòu)的 必要條件 : (1) 結(jié)點(diǎn)數(shù)相等 。 上述定義說明 ,兩個(gè)圖的各結(jié)點(diǎn)之間 ,如果存在一一對應(yīng)關(guān)系 ,而且這種對應(yīng)關(guān)系保持了結(jié)點(diǎn)間的鄰接關(guān)系(在有向圖時(shí)還保持邊的方向 )和邊的重?cái)?shù) ,則這兩個(gè)圖是同構(gòu)的 ,兩個(gè)同構(gòu)的圖除了頂點(diǎn)和邊的名稱不同外實(shí)際上代表同樣的 組合結(jié)構(gòu)。證畢。 由上一定理得 iE?iO?121 1 12 d eg ( ) d eg ( ) d eg ( )iinnni E Oi i im ? ? ?? ? ?? ? ?? ? ? 因?yàn)榇螖?shù)為偶數(shù)的各結(jié)點(diǎn)次數(shù)之和為偶數(shù)。 第 8章 圖論 定理 ―1 設(shè) G是一個(gè) (n,m)圖 ,它的結(jié)點(diǎn)集合為V={v1,v2,…,vn},則 11d eg ( ) d eg ( ) 2nniiiim??????????1d eg ( ) 2niim????