18支配集、覆蓋集、獨(dú)立集、匹配與著色

1、第18章 支配集、覆蓋集、獨(dú)立集、匹配與著色離離 散散 數(shù)數(shù) 學(xué)學(xué)中國(guó)地質(zhì)大學(xué)本科生課程中國(guó)地質(zhì)大學(xué)本科生課程本章說(shuō)明本章說(shuō)明q本章的主要內(nèi)容本章的主要內(nèi)容支配集、點(diǎn)覆蓋集與獨(dú)立集支配集、點(diǎn)覆蓋集與獨(dú)立集邊覆蓋集與匹配邊覆蓋集與匹配二部圖中的匹配二部圖中的匹配點(diǎn)著色點(diǎn)著色地圖著色與平面圖的點(diǎn)著色地圖著色與平面圖的點(diǎn)著色邊著色邊著色 本章所涉及到的圖均指無(wú)向圖。本章所涉及到的圖均指無(wú)向圖。q 1 18.1 8.1 支配集、點(diǎn)覆蓋集與獨(dú)立集支配集、點(diǎn)覆蓋集與獨(dú)立集q 1 18.2 8.2 邊覆蓋集與匹配邊覆蓋集與匹配q 18.3 18.3 二部圖中的匹配二部圖中的匹配q 1 18.4 8.4 點(diǎn)著

2、色點(diǎn)著色q 18.5 18.5 地圖著色與平面圖的點(diǎn)著色地圖著色與平面圖的點(diǎn)著色q 18.6 18.6 邊著色邊著色q 本章小結(jié)本章小結(jié)q 習(xí)習(xí) 題題q 作作 業(yè)業(yè)定義定義18.718.7 設(shè)設(shè)G G是具有互補(bǔ)結(jié)點(diǎn)子集是具有互補(bǔ)結(jié)點(diǎn)子集V V1 1和和V V2 2的二部圖，其的二部圖，其中中V V1 1=v=v1 1，v v2 2，v vr r ，V V1 1對(duì)對(duì)V V2 2的的匹配匹配是是G G的一個(gè)子圖，它的一個(gè)子圖，它由由r r條邊條邊vv1 1，v v 1 1 ，vv2 2，v v 2 2 ，vvr r，v v r r 組成，其中，組成，其中，v v 1 1，v v 2 2，v v r

3、 r是是V V2 2中中r r個(gè)不同的元素。個(gè)不同的元素。否否 例例1 1 下下圖所給出的二部圖是否存在圖所給出的二部圖是否存在V V1 1對(duì)對(duì)V V2 2的匹配？是否的匹配？是否存在存在V V2 2對(duì)對(duì)V V1 1的匹配？的匹配？存在存在V V1 1對(duì)對(duì)V V2 2的匹配的匹配18.318.3二部圖中的匹配二部圖中的匹配 例例2 2 某班級(jí)成立了三個(gè)運(yùn)動(dòng)隊(duì)：籃球隊(duì)、排球隊(duì)和某班級(jí)成立了三個(gè)運(yùn)動(dòng)隊(duì)：籃球隊(duì)、排球隊(duì)和足球隊(duì)。今有張、王、李、趙、陳足球隊(duì)。今有張、王、李、趙、陳5 5名同學(xué)，若已知張、名同學(xué)，若已知張、王為籃球隊(duì)員；張、李、趙為排球隊(duì)員；李、趙、陳為足王為籃球隊(duì)員；張、李、趙為排球

4、隊(duì)員；李、趙、陳為足球隊(duì)員，問(wèn)能否從這球隊(duì)員，問(wèn)能否從這5 5人中選出人中選出3 3名不兼職的隊(duì)長(zhǎng)？名不兼職的隊(duì)長(zhǎng)？在圖中存在在圖中存在V V1 1對(duì)對(duì)V V2 2的匹配，因此題目的要求可以滿足。的匹配，因此題目的要求可以滿足。 解解構(gòu)造二部圖構(gòu)造二部圖G=G=（V V1 1，V V2 2，E E），）， V V1 1V V2 2定理定理18.618.6 設(shè)設(shè)G G是具有互補(bǔ)結(jié)點(diǎn)子集是具有互補(bǔ)結(jié)點(diǎn)子集V V1 1和和V V2 2的二部圖，若存在的二部圖，若存在一整數(shù)一整數(shù)t0t0，(1)(1)對(duì)對(duì)v v1 1中的每個(gè)結(jié)點(diǎn)，至少有中的每個(gè)結(jié)點(diǎn)，至少有t t條邊與其相關(guān)聯(lián)；條邊與其相關(guān)聯(lián)；(2)(

5、2)對(duì)對(duì)v v2 2中的每個(gè)結(jié)點(diǎn)，至多有中的每個(gè)結(jié)點(diǎn)，至多有t t條邊與其相關(guān)聯(lián)。條邊與其相關(guān)聯(lián)。則則G G中存在中存在v v1 1對(duì)對(duì)v v2 2的匹配。的匹配。v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7v v8 8 定理中的條件不是二部圖存定理中的條件不是二部圖存在在匹配匹配的必要條件。的必要條件。V V1 1V V2 2二部圖存在匹配的充分條件：二部圖存在匹配的充分條件：1 18.4 8.4 點(diǎn)著色點(diǎn)著色規(guī)定：規(guī)定：點(diǎn)著色都是對(duì)無(wú)環(huán)無(wú)向圖進(jìn)行的。點(diǎn)著色都是對(duì)無(wú)環(huán)無(wú)向圖進(jìn)行的。一、關(guān)于頂點(diǎn)著色的基本概念一、關(guān)于頂點(diǎn)著色的基本概念定義定義1 18.8

6、8.8 （1）圖）圖G的一種著色的一種著色對(duì)無(wú)環(huán)圖對(duì)無(wú)環(huán)圖G的每個(gè)頂點(diǎn)涂上一種顏的每個(gè)頂點(diǎn)涂上一種顏 色，使相鄰頂點(diǎn)涂不同的顏色。色，使相鄰頂點(diǎn)涂不同的顏色。（2）對(duì)）對(duì)G進(jìn)行進(jìn)行k著色（著色（G是是k-可著色的）可著色的）能用能用k種顏色給種顏色給G 的頂點(diǎn)著色。的頂點(diǎn)著色。（3）G的色數(shù)的色數(shù) (G)=kG是是k-可著色的，但不是可著色的，但不是(k 1)-可著可著 色的。色的。二、關(guān)于頂點(diǎn)著色的幾個(gè)簡(jiǎn)單結(jié)果二、關(guān)于頂點(diǎn)著色的幾個(gè)簡(jiǎn)單結(jié)果q (G)=1當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G為零圖。為零圖。q (Kn)=n。 q 奇圈或奇階輪圖的色數(shù)均為奇圈或奇階輪圖的色數(shù)均為3，偶階輪圖的色數(shù)為偶階輪圖的色數(shù)

7、為4。q 設(shè)設(shè)G中至少含有一條邊，則中至少含有一條邊，則 (G)=2當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G為二部圖。為二部圖。三、色數(shù)的上界三、色數(shù)的上界定理定理1 18.78.7 對(duì)于任意無(wú)向圖對(duì)于任意無(wú)向圖G，均有均有 (G) (G)+1。q n=1時(shí)，結(jié)論成立。時(shí)，結(jié)論成立。q 設(shè)設(shè)n=k(k1)時(shí)結(jié)論成立，則當(dāng)時(shí)結(jié)論成立，則當(dāng)n=k+1時(shí)，時(shí)， 設(shè)設(shè)v為為G中任一個(gè)頂點(diǎn)，令中任一個(gè)頂點(diǎn)，令G=G-v，則則G的階數(shù)為的階數(shù)為k，由假設(shè)由假設(shè)可知可知 (G) (G)+1 (G)+1。 當(dāng)將當(dāng)將G還原成還原成G時(shí)，由于時(shí)，由于v至多與至多與G中中(G)個(gè)頂點(diǎn)相鄰，而在個(gè)頂點(diǎn)相鄰，而在G的點(diǎn)著色中，的點(diǎn)著色中，(

8、G)個(gè)頂點(diǎn)至多用了個(gè)頂點(diǎn)至多用了(G)種顏色，于是在種顏色，于是在(G)+1種顏色中至少存在一種顏色給種顏色中至少存在一種顏色給v涂色，使涂色，使v與相鄰頂點(diǎn)與相鄰頂點(diǎn)涂不同顏色。涂不同顏色。 證證明明提示：對(duì)提示：對(duì)G的階數(shù)的階數(shù)n作歸納法。作歸納法。例例1 18.48.4 求下面各圖的色數(shù)。求下面各圖的色數(shù)。 定理定理1 18.88.8 ( (布魯克斯定理布魯克斯定理) 若連通無(wú)向圖若連通無(wú)向圖G不是不是Kn(n 3)，也不是奇也不是奇數(shù)階的圈，則數(shù)階的圈，則 (G) (G)。q 因?yàn)橐驗(yàn)?1)為為二部圖，由定理二部圖，由定理17.22可知，可知， (G) =2。q (2)為為6階輪圖階輪

9、圖W6，由定理由定理17.21可知，可知， (G) =4。q 由定理由定理17.24可知，可知， (G)4，又因?yàn)橛忠驗(yàn)?3)中有奇圈，于是中有奇圈，于是 (G) 3，因而因而 (G)為為3或或4，用，用3種顏色不可能給種顏色不可能給G4著色，于是只能著色，于是只能是是 (G) =4。解答解答小節(jié)結(jié)束小節(jié)結(jié)束1 18.5 8.5 地圖著色與平面圖的點(diǎn)著色地圖著色與平面圖的點(diǎn)著色一、地圖與面著色一、地圖與面著色1、地圖與國(guó)家、地圖與國(guó)家（1）地圖）地圖連通無(wú)橋平面圖的平面嵌入與所有的面。連通無(wú)橋平面圖的平面嵌入與所有的面。（2）國(guó)家）國(guó)家地圖的面。地圖的面。（3）兩個(gè)國(guó)家相鄰）兩個(gè)國(guó)家相鄰兩個(gè)國(guó)

10、家的邊界至少有一條公共邊。兩個(gè)國(guó)家的邊界至少有一條公共邊。有有5個(gè)國(guó)家，個(gè)國(guó)家，1與與2相鄰，相鄰，1與與4相鄰，相鄰，2,3,4均與均與5相鄰。相鄰。541232、地圖的面著色、地圖的面著色定義定義1 18.98.9（1）地圖）地圖G的一種面著色的一種面著色對(duì)地圖對(duì)地圖G的每個(gè)國(guó)家涂上一種的每個(gè)國(guó)家涂上一種 顏色，使相鄰國(guó)家涂不同的顏色。顏色，使相鄰國(guó)家涂不同的顏色。（2）G是是k-面可著色的面可著色的能用能用k種顏色給種顏色給G的面著色，就稱的面著色，就稱 對(duì)對(duì)G的面進(jìn)行了的面進(jìn)行了k著色。著色。（3）G的面色數(shù)的面色數(shù) *(G)=kG是是k-面可著色的，但不是面可著色的，但不是(k-1)

11、- 面可著色的，即最少用面可著色的，即最少用k種顏色給種顏色給G的面著色。的面著色。 q研究地圖的著色可以轉(zhuǎn)化成對(duì)它的對(duì)偶圖的點(diǎn)著色研究地圖的著色可以轉(zhuǎn)化成對(duì)它的對(duì)偶圖的點(diǎn)著色 。說(shuō)說(shuō)明明二、地圖的面著色轉(zhuǎn)化成對(duì)偶圖的點(diǎn)著色二、地圖的面著色轉(zhuǎn)化成對(duì)偶圖的點(diǎn)著色定理定理1 18.98.9 地圖地圖G是是k-面可著色的當(dāng)且僅當(dāng)它的對(duì)偶圖面可著色的當(dāng)且僅當(dāng)它的對(duì)偶圖G*是是k-點(diǎn)點(diǎn)可著色的?？芍?。三、四色定理三、四色定理定理定理1 18.108.10 任何平面圖都是任何平面圖都是4-可著色的可著色的 。 四色猜想四色猜想問(wèn)題，提出來(lái)已經(jīng)近問(wèn)題，提出來(lái)已經(jīng)近150年了，但時(shí)至今日還沒(méi)有年了，但時(shí)至

12、今日還沒(méi)有得到徹底解決。得到徹底解決。 小節(jié)結(jié)束小節(jié)結(jié)束1 18.6 8.6 邊著色邊著色本節(jié)討論的圖是無(wú)環(huán)的無(wú)向圖。本節(jié)討論的圖是無(wú)環(huán)的無(wú)向圖。一、對(duì)圖一、對(duì)圖G進(jìn)行邊著色進(jìn)行邊著色定義定義1 18.108.10 （1）對(duì)圖對(duì)圖G邊的一種著色邊的一種著色對(duì)圖對(duì)圖G的每條邊涂上一種顏色，的每條邊涂上一種顏色， 使相鄰的邊涂不同的顏色使相鄰的邊涂不同的顏色。（2）G是是k-邊可著色的邊可著色的能用能用k種顏色給種顏色給G的邊著色。的邊著色。（3）G的邊色數(shù)的邊色數(shù)(G)=k若若G是是k-邊可著色的，但不是邊可著色的，但不是 (k-1)-邊可著色的，即邊可著色的，即最少用最少用k種顏色給種顏色給G

13、的邊著色。的邊著色。二、關(guān)于邊著色的一些定理二、關(guān)于邊著色的一些定理 定理定理1 18.118.11 G為簡(jiǎn)單平面圖，則為簡(jiǎn)單平面圖，則 (G) (G) (G)+1。q 該定理是維津定理。該定理是維津定理。q 定理說(shuō)明，對(duì)簡(jiǎn)單圖來(lái)說(shuō)，它的邊色數(shù)定理說(shuō)明，對(duì)簡(jiǎn)單圖來(lái)說(shuō)，它的邊色數(shù)只能取它的只能取它的 (G) ，或者是它的或者是它的 (G) +1。q 究竟哪些圖的究竟哪些圖的 (G)是是 (G) ，哪些是哪些是 (G) +1，至今還是至今還是 一個(gè)沒(méi)有解決的問(wèn)題。一個(gè)沒(méi)有解決的問(wèn)題。例例18.518.5設(shè)設(shè)G為長(zhǎng)度大于或等于為長(zhǎng)度大于或等于2的偶圈，則的偶圈，則(G)=(G)=2.設(shè)設(shè)G為長(zhǎng)度大于

14、或等于為長(zhǎng)度大于或等于3的奇圈，則的奇圈，則(G)=(G)+1=3. q n=4時(shí)時(shí)，由維津定理可知，結(jié)論正確。由維津定理可知，結(jié)論正確。q n=5時(shí)，由維津定理可知，結(jié)論正確。時(shí)，由維津定理可知，結(jié)論正確。q n6時(shí)，時(shí)，(Wn)=n-15，Wn中間頂點(diǎn)關(guān)聯(lián)的中間頂點(diǎn)關(guān)聯(lián)的n-1條邊必須用條邊必須用n-1種顏色著色。種顏色著色。 而外圈而外圈Cn-1上的任何邊都準(zhǔn)確的與其余的上的任何邊都準(zhǔn)確的與其余的4條邊相鄰，于是總條邊相鄰，于是總可以找到可以找到n-1種色中的一種為它涂色，所以種色中的一種為它涂色，所以(Wn)n-1。 又由維津定理可知，又由維津定理可知，(Wn)n-1，所以所以(Wn)

15、=n-1。例例18.618.6 (Wn) = (Wn) = n 1，其中其中n 4。定理定理1 18.128.12 二部圖的邊色數(shù)等于最大度。二部圖的邊色數(shù)等于最大度。證證明明例例18.718.7 當(dāng)當(dāng)n(n 1)為奇數(shù)時(shí)，為奇數(shù)時(shí)， (Kn)=n；當(dāng)當(dāng)n為偶數(shù)時(shí)，為偶數(shù)時(shí)， (Kn)=n 1。例例17.517.5 證明證明(W4)=(W4)=3，(W5)=(W5)=4。由維津定理可知結(jié)論是正確的。由維津定理可知結(jié)論是正確的。 解答解答例例 求下面所示各圖的邊色數(shù)。求下面所示各圖的邊色數(shù)。 小節(jié)結(jié)束小節(jié)結(jié)束q (1)中無(wú)奇長(zhǎng)回路，所以它為二部圖，由定理中無(wú)奇長(zhǎng)回路，所以它為二部圖，由定理17.30可知可知=4。q 由維津定理可知，由維津定理可知，(2)中中=4，又存在又存在4種顏色的邊著色，種顏色的邊著色，所以所以4，因而因而=4。解答解答本章主要內(nèi)容本章主要內(nèi)容q 頂點(diǎn)的著色與點(diǎn)色數(shù)。頂點(diǎn)的著色與點(diǎn)色數(shù)。q 關(guān)于點(diǎn)色數(shù)的一些定理。關(guān)于點(diǎn)色數(shù)的一些定理。q 地圖及其面著色、面色數(shù)。地圖及其面著色、面色數(shù)。q 平面圖的四色定理。平面圖的四色定理。q 邊著色及邊色數(shù)。邊著色及邊色數(shù)。q 關(guān)于邊著色的一些定理。