1、1,第8章 一些特殊的圖,8.1 二部圖 8.2 歐拉圖 8.3 哈密頓圖 8.4 平面圖,2,8.1 二部圖,二部圖 完全二部圖 匹配 極大匹配 最大匹配 匹配數(shù) 完備匹配,3,二部圖,定義 設無向圖 G=, 若能將V 劃分成V1 和 V2 (V1V2=V, V1V2=), 使得G中的每條邊的兩個端 點都一個屬于V1, 另一個屬于V2, 則稱G為二部圖, 記為, 稱V1和V2為互補頂點子集. 又若G 是簡單圖, 且V1中每個頂點都與V2中每個頂點相鄰, 則稱G為完全二部圖, 記為Kr,s, 其中r=|V1|, s=|V2|. 注意: n 階零圖為二部圖.,4,二部圖的判別法,定理 無向圖G=

2、是二部圖當且僅當G中無奇圈 例 下述各圖是否是二部圖,5,匹配,設G=, 匹配(邊獨立集): 任2條邊均不相鄰的邊子集 極大匹配: 添加任一條邊后都不再是匹配的匹配 最大匹配: 邊數(shù)最多的匹配 匹配數(shù): 最大匹配中的邊數(shù), 記為1 例 下述3個圖的匹配數(shù) 依次為多少？,6,匹配 (續(xù)),設M為G中一個匹配 vi與vj被M匹配: (vi,vj)M v為M飽和點: M中有邊與v關聯(lián) v為M非飽和點: M中沒有邊與v關聯(lián) M為完美匹配: G的每個頂點都是M飽和點 例 關于M1, a,b,e,d是飽和點 f,c是非飽和點 M1不是完美匹配 M2是完美匹配,7,二部圖中的匹配,定義 設G=為二部圖, |

3、V1|V2|, M是G中最 大匹配, 若V1中頂點全是M飽和點, 則稱M為G中V1 到V2的完備匹配. 當|V1|=|V2|時, 完備匹配變成完美 匹配.,8,Hall定理,定理(Hall定理) 設二部圖G=中，|V1|V2|. G中存 在從V1到V2的完備匹配當且僅當V1中任意k 個頂點至少與V2 中的k個頂點相鄰(k=1,2,|V1|). 由Hall定理不難證明, 上一頁圖(2)沒有完備匹配. 定理 設二部圖G=中, 如果存在t1, 使得V1中每個 頂點至少關聯(lián) t 條邊, 而V2中每個頂點至多關聯(lián)t條邊，則G 中存在V1到V2的完備匹配. Hall定理中的條件稱為“相異性條件”, 第二個

4、定理中的條件 稱為 t 條件. 滿足 t 條件的二部圖一定滿足相異性條件.,9,一個應用實例,例 某課題組要從a, b, c, d, e 5人中派3人分別到上海、廣州、香港去開會. 已知a只想去上海，b只想去廣州，c, d, e都 表示想去廣州或香港. 問該課題組在滿足個人要求的條件下，共有幾種派遣方案？ 解 令G=, 其中V1=s, g, x, V2=a, b, c, d, e, E=(u,v) | uV1, vV2, v想去u, 其中s, g, x分別表示上海、廣州和香港. G如圖所示. G 滿足相異性條件，因而可給 出派遣方案，共有9種派遣方案 (請給出這9種方案).,10,8.2 歐拉

5、圖,歐拉通路 歐拉回路 歐拉圖 半歐拉圖,11,哥尼斯堡七橋問題,歐拉圖是能一筆畫出的邊不重復的回路.,12,歐拉圖,歐拉通路: 圖中行遍所有頂點且恰好經(jīng)過每條邊一次的通路. 歐拉回路: 圖中行遍所有頂點且恰好經(jīng)過每條邊一次的回路. 歐拉圖: 有歐拉回路的圖. 半歐拉圖: 有歐拉通路而無歐拉回路的圖. 幾點說明： 上述定義對無向圖和有向圖都適用. 規(guī)定平凡圖為歐拉圖. 歐拉通路是簡單通路, 歐拉回路是簡單回路. 環(huán)不影響圖的歐拉性.,13,歐拉圖(續(xù)),例 圖中, 哪些圖是歐拉圖，哪些是半歐拉圖，不是歐拉圖的圖至少要添加幾條邊才能成為歐拉圖.,14,歐拉圖的判別法,定理 無向圖G為歐拉圖當且僅

6、當G連通且無奇度頂點. 無向圖G是半歐拉圖當且僅當G連通且恰有兩個奇度頂點. 定理 有向圖D是歐拉圖當且僅當D連通且每個頂點的入度都等于出度. 有向圖D具有歐拉通路當且僅當D連通且恰有兩個奇度頂點, 其中一個入度比出度大1, 另一個出度比入度大1, 其余頂點的入度等于出度.,15,實例,例1 哥尼斯堡七橋問題 例2 下面兩個圖都是歐拉圖. 從A點出發(fā), 如何一次成功地走出一條歐拉回路來？,16,8.3 哈密頓圖,哈密頓通路 哈密頓回路 哈密頓圖 半哈密頓圖,17,哈密頓周游世界問題,18,哈密頓圖的定義,哈密頓通路: 經(jīng)過圖中所有頂點一次且僅一次的通路. 哈密頓回路: 經(jīng)過圖中所有頂點一次且僅

7、一次的回路. 哈密頓圖: 具有哈密頓回路的圖. 半哈密頓圖: 具有哈密頓通路而無哈密頓回路的圖. 幾點說明： 平凡圖是哈密頓圖. 哈密頓通路是初級通路，哈密頓回路是初級回路. 環(huán)與平行邊不影響圖的哈密頓性.,19,實例,例 圖中, 觀察下面圖的哈密頓性質。,20,無向哈密頓圖的一個必要條件,定理 設無向圖G=是哈密頓圖, 則對于任意V1V且 V1, 均有 p(GV1)|V1|. 證 設C為G中一條哈密頓回路, 有p(CV1) |V1|. 又因為 CG, 故 p(GV1) p(CV1) |V1|. 幾點說明 定理中的條件是哈密頓圖的必要條件, 但不是充分條件. 可利用該定理判斷某些圖不是哈密頓圖

8、. 由定理可知, Kr,s當sr+1時不是哈密頓圖. 當r2時, Kr,r是哈密頓圖, 而Kr,r+1是半哈密頓圖.,21,實例,例 設G為n階無向連通簡單圖, 若G中有割點或橋, 則G不是哈密頓圖. 證 (1) 設v為割點, 則p(Gv) 2|v|=1. 根據(jù)定理, G不是哈密頓圖. (2) 若G是K2(K2有橋), 它顯然不是哈密頓圖. 除K2 外, 其他的有橋連通圖均有割點. 由(1), 得證G不是 哈密頓圖.,22,無向哈密頓圖的一個充分條件,定理 設G是n階無向簡單圖, 若任意兩個不相鄰的頂點 的度數(shù)之和大于等于n1, 則G中存在哈密頓通路. 當n3時, 若任意兩個不相鄰的頂點的度數(shù)

9、之和大 于等于n, 則G中存在哈密頓回路, 從而G為哈密頓 圖.,23,哈密頓通路(回路)的存在性(續(xù)),定理中的條件是存在哈密頓通路(回路)的充分條 件, 但不是必要條件. 例如, 設G為長度為n1(n4)的路徑, 它不滿足定理 中哈密頓通路的條件, 但它顯然存在哈密頓通路. 設G是長為n的圈, 它不滿足定理中哈密頓回路的條 件, 但它顯然是哈密頓圖. 由定理, 當n3時, Kn均為哈密頓圖. 判斷某圖是否為哈密頓圖至今還是一個難題,24,判斷是否是哈密頓圖的可行方法,觀察出一條哈密頓回路 例如 右圖(周游世界問題)中紅 邊給出一條哈密頓回路, 故它 是哈密頓圖. 注意, 此圖不滿足定理的條件. 滿足充分條件 例如 當n3時, Kn中任何兩個不同的頂點 u,v, 均 有d(u)+d(v) = 2(n1) n, 所以Kn為哈密頓圖.,25,應用實例,例 某次國際會議8人參加，已知每人至少與其余7人中 的4人有共同語言，問服務員能否將他們安排在同一張 圓桌就座，使得每個人都能與兩邊的人交談？ 解 圖是描述事物之間關系的最好的手段之一. 作無向圖 G=, 其中V=v|v為與會者，E=(u,v)