《離散數(shù)學(xué)課件》4二部、平面

1、1/60,9.6 二部圖,(一) 二部圖(二) 完全二部圖(三)判定定理,2/60,例,假設(shè)5個(gè)教師共講授8門課程。令課程和教師是圖的頂點(diǎn)，只要某教師能夠講授某課程，就在該課程與該教師之間畫一條邊，如下圖所示：,,,,,,,,,,,,,,課程,教師,,,,,,,,,,,,,,,,,3/60,二部圖（二分圖、偶圖）,定義：設(shè)G=(V,E)是一個(gè)圖， 若存在頂點(diǎn)集 的一個(gè)劃分{V1, V2}，使得：

2、 對(duì)于任意的e?E， 存在v1?V1，v2?V2滿足 {v1, v2}=e, 則稱（V1，V2）是圖G的頂點(diǎn)的二分類。 稱圖G為二部圖，或稱二分圖，也稱偶圖， 又稱G為具有二分類（V1，V2）的偶圖。,4/60,完全二部圖,G=(V, E) 是一個(gè)二部圖，（V

3、1，V2）是G的二分類，若對(duì)于任意的v1?V1，v2?V2，有 {v1,v2} ?E，說G是一個(gè)完全二部圖。,,5/60,完全二部圖Kn,m,一個(gè)完全二部圖G，（V1，V2）是它的二分類，|V1|=n，|V2|=m，記G為Kn,m。,,圖9.17 兩個(gè)完全二部圖,二部圖的判別法,定理 無向圖G=是二部圖當(dāng)且僅當(dāng)G的所有回路的長度均是偶數(shù)。例 下述各圖都是二部圖,6,7/60,例(習(xí)題9.2

4、6, p123),已知： a，b，c，d，e，f，g的下述事實(shí)：(a)說漢語、日語；(b)說日語、法語；(c)說德語、法語、西班牙語；(d)說漢語、德語、俄語、葡萄牙語；(e)說俄語、朝語；(f)說朝語、西班牙語；(g)說葡萄牙語。試問：能否將七個(gè)人分成兩組，使同一組中沒有兩個(gè)人能互相交談？并用圖論方法，說明你的結(jié)論。,8/60,例(習(xí)題9.26, p123),解： 能！ 將頂點(diǎn)分成{a,c,e,g}與{b,d,f}這兩

5、組后，關(guān)系圖可以表示成二分圖的形式，即各組中沒有兩個(gè)人能互相交談。,9/60,9.7 平面圖與平面圖的著色,(一) 平面圖的定義(二) 歐拉公式 (定理1)(三) 兩種必要條件(定理2定理3)(四) 充分必要條件(庫拉道夫斯基定理)(五) 四色猜想(六) 對(duì)偶圖(七) 五色定理,10/60,平面圖的問題,一個(gè)怎樣的圖，可以邊不相交的畫在一塊平面上?,11/60,并非所有的圖都能嵌入平面,設(shè)有三座房子和三個(gè)公共設(shè)施，能否使

6、每座房子與每個(gè)公共設(shè)施之間均有道路連接而無交叉？,12/60,平面圖,定義 一個(gè)圖G=(V,E)，如果能夠畫在一個(gè)平面上，除頂點(diǎn)外，它的邊彼此不相交，這種圖稱為平面圖，反之稱為非平面圖。,平面嵌入: 把一個(gè)平面圖 G畫在一個(gè)平面上，使得它的邊僅在頂點(diǎn)相交這樣的一種畫法稱為G的一個(gè)平面嵌入。,,13/60,例 平面圖——非平面圖,?,14/60,區(qū)域,把一個(gè)平面圖畫在一個(gè)平面上，使它的邊僅在頂點(diǎn)相交，然后，用剪刀沿各邊剪下，每一條邊

7、都被剪開，于是一個(gè)平面分成了若干個(gè)小片，每個(gè)小片叫平面的一個(gè)區(qū)域，也就是一個(gè)平面圖的區(qū)域是由圖中的邊圍成的，且不能再分成更小的區(qū)域。如果區(qū)域的面積是有限的，稱它為有限區(qū)域，如果區(qū)域的面積是無限的，稱它為無限區(qū)域。,例,,,,,,15,平面圖的面與次數(shù),設(shè)G是一個(gè)平面嵌入G的面: 由G的邊將平面劃分成的每一個(gè)區(qū)域無限面(外部面): 面積無限的面, 用R0表示有限面(內(nèi)部面): 面積有限的面, 用R1, R2,…, Rk表示 面Ri

8、的邊界: 包圍Ri的所有邊構(gòu)成的回路組面Ri的次數(shù): Ri邊界的長度，用deg(Ri)表示 說明: 構(gòu)成一個(gè)面的邊界的回路組可能是初級(jí)回路, 簡單回路, 也可能是復(fù)雜回路, 甚至還可能是非連通的回路之并. 定理 平面圖各面的次數(shù)之和等于邊數(shù)的2倍.,16,平面圖的面與次數(shù)(續(xù)),例1 右圖有4個(gè)面, deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8. 請(qǐng)寫各面的邊

9、界.,,例2 左邊2個(gè)圖是同一個(gè)平面圖的平面嵌入. R1在(1)中是外部面, 在(2)中是內(nèi)部面; R2在(1)中是內(nèi)部面, 在(2)中是外部面. 其實(shí), 在平面嵌入中可把任何面作為外部面.,17/60,歐拉(Euler)公式,定理1 對(duì)于任何一個(gè)連通的平面圖G=(V,E)， |V|=n，|E|=m，則有n-m+r=2， 其中r 代表G的面數(shù)。,頂點(diǎn)5個(gè)邊8條面數(shù)55-8+5=

10、2,18,與歐拉公式有關(guān)的定理,,19/60,例 K5和K3,3,n=6m=9≤3n-6=12滿足必要條件，但仍然不知道K3,3是否平面圖。,取l=3,20/60,例,,,顯然，右圖與左圖同構(gòu)。,同胚與收縮,,21,,,消去2度頂點(diǎn)v 如上圖從(1)到(2)插入2度頂點(diǎn)v 如上圖從(2)到(1)G1與G2同胚: G1與G2同構(gòu), 或經(jīng)過反復(fù)插入、或消去2度頂點(diǎn)后同構(gòu)收縮邊e 如下圖從(1)到(2),22/60,庫拉道

11、夫斯基定理,定理4 G是平面圖?G中不含與K5同胚的子圖, 也不含與K3,3同胚的子圖. G是平面圖?G中無可收縮為K5的子圖, 也無可收縮為K3,3的子圖.,K5與K3,3也稱庫拉道夫斯基圖。,波蘭數(shù)學(xué)家?guī)炖婪蛩够↘uratowski）在1930年給出了判定一個(gè)圖是平面圖的這個(gè)充要條件。這個(gè)定理證明太復(fù)雜，我們僅介紹不證明。,,23

12、/60,例 皮德森(Petersen)圖,皮德森圖不是平面圖，因?yàn)橐蛔訄D與K3,3同胚。,?,?,24/60,例 證明下圖是哈密爾頓圖, 但它不是平面圖。,擦去三邊后的子圖是K3,3,哈密爾頓回路adbecfa,25/60,平面圖的著色,一個(gè)平面圖的任意二個(gè)區(qū)域若有一條公共邊，則稱這二個(gè)區(qū)域是相鄰的。一個(gè)平面圖的著色問題是對(duì)平面圖的區(qū)域著上顏色，至少要用幾種不同顏色才能使得任何相鄰兩個(gè)區(qū)域有不同的顏色。,例,,26/60,,,27

13、/60,四色猜想(四色問題),在1852年，一個(gè)英國青年名叫蓋思里（Francis Guthrie）提出：任何連通的平面圖，可以用不多于4種顏色對(duì)每一個(gè)區(qū)域著色，使相鄰區(qū)域著不同顏色。1878～1880年兩年間，數(shù)學(xué)家肯普和泰勒兩人分別宣布證明了四色定理。后來，人們發(fā)現(xiàn)他們實(shí)際上證明了一個(gè)較弱的命題——五色定理。就是說對(duì)平面圖著色，用五種顏色就夠了。1976年美國伊利諾州立大學(xué)的兩位教授，阿佩爾（Kenneth Appel）和?？希?/p>

14、Wolfgang Haken）宣布，用計(jì)算機(jī)證明了這個(gè)問題。他們的證明需要對(duì)1900多種情況進(jìn)行詳盡的分析，在一臺(tái)高速計(jì)算機(jī)上耗時(shí)超過1200小時(shí)。對(duì)數(shù)學(xué)家來說總還是希望能找到數(shù)學(xué)方法的證明。,28/60,n色圖,頂點(diǎn)著色：對(duì)一個(gè)圖的每一個(gè)頂點(diǎn)著上一種顏色，使得相鄰接的兩個(gè)頂點(diǎn)著不同顏色。,定義 如果一個(gè)圖至少需 n種顏色才能完成對(duì)頂點(diǎn)的著色就稱這個(gè)圖為 n色圖, 記為 χ(G)=n,29/60

15、,可k-著色的,是否可以把平面圖的區(qū)域著色問題轉(zhuǎn)化為平面圖的頂點(diǎn)著色問題？答案是肯定的。,定義 一個(gè)圖G稱為可k-著色的（k-chromatic），如果可用k種顏色給G的所有頂點(diǎn)著色，使每個(gè)頂點(diǎn)著一種顏色，而同一邊的兩個(gè)端點(diǎn)著不同顏色。,30/60,對(duì)偶圖,設(shè)G是一個(gè)連通平面圖。G已經(jīng)被嵌入某一平面內(nèi)，把平面分為n個(gè)區(qū)域f1，f2，…，fn，在每一個(gè)區(qū)域fi內(nèi)取定一點(diǎn)ri代表這個(gè)區(qū)域，若ri和rj是兩個(gè)區(qū)域，它們之間有若干條公共邊，對(duì)

16、每一條公共邊我們連接ri和rj，并與這條公共邊相交叉一條線（直線或曲線），有多少條公共邊畫多少條，這樣我們得到一個(gè)新圖記為G*，稱為圖G的對(duì)偶圖。,從畫法知， G和G*有相同的邊數(shù)。,,,,,,,,,,,G,G*,例,在本例中, G和G*同構(gòu)。一般地，未必同構(gòu)。,,31/60,例,圖9.21(p153) 注意圖中的自環(huán)是怎樣處理的(書上有錯(cuò))。,,,,,,,,,,,,,,,,,32/60,例,,,,,,,,,,,,,,,,,注意圖中的

17、一度頂點(diǎn)和自環(huán)是怎樣處理的。,例,注意，當(dāng)G1，G2為同構(gòu)圖的兩種不同圖示，那么它們的對(duì)偶圖G1’與G2’不僅圖示可能不同，而且可能是根本不同的圖（不同構(gòu)）。這就是說，一個(gè)圖的對(duì)偶圖未必是唯一的。,,,34/60,對(duì)偶圖的性質(zhì),圖G的面與G*的頂點(diǎn)一一對(duì)應(yīng)，且G中面的度(邊界的長度)等于G*中對(duì)應(yīng)頂點(diǎn)的度 。G中兩個(gè)面有公共邊界，當(dāng)且僅當(dāng)G*中對(duì)應(yīng)頂點(diǎn)之間有邊關(guān)聯(lián)。G為平面圖當(dāng)且僅當(dāng)G*為平面圖。,對(duì)于圖的面著色問題，可以通過研究其