18支配集、覆蓋集、獨立集、匹配與著色

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

2、色點著色q 18.5 18.5 地圖著色與平面圖的點著色地圖著色與平面圖的點著色q 18.6 18.6 邊著色邊著色q 本章小結(jié)本章小結(jié)q 習(xí)習(xí) 題題q 作作 業(yè)業(yè)定義定義18.718.7 設(shè)設(shè)G G是具有互補(bǔ)結(jié)點子集是具有互補(bǔ)結(jié)點子集V V1 1和和V V2 2的二部圖，其的二部圖，其中中V V1 1=v=v1 1，v v2 2，v vr r ，V V1 1對對V V2 2的的匹配匹配是是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個不同的元素。個不同的元素。否否 例例1 1 下下圖所給出的二部圖是否存在圖所給出的二部圖是否存在V V1 1對對V V2 2的匹配？是否的匹配？是否存在存在V V2 2對對V V1 1的匹配？的匹配？存在存在V V1 1對對V V2 2的匹配的匹配18.318.3二部圖中的匹配二部圖中的匹配 例例2 2 某班級成立了三個運動隊：籃球隊、排球隊和某班級成立了三個運動隊：籃球隊、排球隊和足球隊。今有張、王、李、趙、陳足球隊。今有張、王、李、趙、陳5 5名同學(xué)，若已知張、名同學(xué)，若已知張、王為籃球隊員；張、李、趙為排球隊員；李、趙、陳為足王為籃球隊員；張、李、趙為排球

4、隊員；李、趙、陳為足球隊員，問能否從這球隊員，問能否從這5 5人中選出人中選出3 3名不兼職的隊長？名不兼職的隊長？在圖中存在在圖中存在V V1 1對對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é)點子集是具有互補(bǔ)結(jié)點子集V V1 1和和V V2 2的二部圖，若存在的二部圖，若存在一整數(shù)一整數(shù)t0t0，(1)(1)對對v v1 1中的每個結(jié)點，至少有中的每個結(jié)點，至少有t t條邊與其相關(guān)聯(lián)；條邊與其相關(guān)聯(lián)；(2)(

5、2)對對v v2 2中的每個結(jié)點，至多有中的每個結(jié)點，至多有t t條邊與其相關(guān)聯(lián)。條邊與其相關(guān)聯(lián)。則則G G中存在中存在v v1 1對對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 點著色點著色規(guī)定：規(guī)定：點著色都是對無環(huán)無向圖進(jìn)行的。點著色都是對無環(huán)無向圖進(jìn)行的。一、關(guān)于頂點著色的基本概念一、關(guān)于頂點著色的基本概念定義定義1 18.8

6、8.8 （1）圖）圖G的一種著色的一種著色對無環(huán)圖對無環(huán)圖G的每個頂點涂上一種顏的每個頂點涂上一種顏 色，使相鄰頂點涂不同的顏色。色，使相鄰頂點涂不同的顏色。（2）對）對G進(jìn)行進(jìn)行k著色（著色（G是是k-可著色的）可著色的）能用能用k種顏色給種顏色給G 的頂點著色。的頂點著色。（3）G的色數(shù)的色數(shù) (G)=kG是是k-可著色的，但不是可著色的，但不是(k 1)-可著可著 色的。色的。二、關(guān)于頂點著色的幾個簡單結(jié)果二、關(guā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 對于任意無向圖對于任意無向圖G，均有均有 (G) (G)+1。q n=1時，結(jié)論成立。時，結(jié)論成立。q 設(shè)設(shè)n=k(k1)時結(jié)論成立，則當(dāng)時結(jié)論成立，則當(dāng)n=k+1時，時， 設(shè)設(shè)v為為G中任一個頂點，令中任一個頂點，令G=G-v，則則G的階數(shù)為的階數(shù)為k，由假設(shè)由假設(shè)可知可知 (G) (G)+1 (G)+1。 當(dāng)將當(dāng)將G還原成還原成G時，由于時，由于v至多與至多與G中中(G)個頂點相鄰，而在個頂點相鄰，而在G的點著色中，的點著色中，(

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

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

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

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

12、今日還沒有得到徹底解決。得到徹底解決。 小節(jié)結(jié)束小節(jié)結(jié)束1 18.6 8.6 邊著色邊著色本節(jié)討論的圖是無環(huán)的無向圖。本節(jié)討論的圖是無環(huán)的無向圖。一、對圖一、對圖G進(jìn)行邊著色進(jìn)行邊著色定義定義1 18.108.10 （1）對圖對圖G邊的一種著色邊的一種著色對圖對圖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為簡單平面圖，則為簡單平面圖，則 (G) (G) (G)+1。q 該定理是維津定理。該定理是維津定理。q 定理說明，對簡單圖來說，它的邊色數(shù)定理說明，對簡單圖來說，它的邊色數(shù)只能取它的只能取它的 (G) ，或者是它的或者是它的 (G) +1。q 究竟哪些圖的究竟哪些圖的 (G)是是 (G) ，哪些是哪些是 (G) +1，至今還是至今還是 一個沒有解決的問題。一個沒有解決的問題。例例18.518.5設(shè)設(shè)G為長度大于或等于為長度大于或等于2的偶圈，則的偶圈，則(G)=(G)=2.設(shè)設(shè)G為長度大于

14、或等于為長度大于或等于3的奇圈，則的奇圈，則(G)=(G)+1=3. q n=4時時，由維津定理可知，結(jié)論正確。由維津定理可知，結(jié)論正確。q n=5時，由維津定理可知，結(jié)論正確。時，由維津定理可知，結(jié)論正確。q n6時，時，(Wn)=n-15，Wn中間頂點關(guān)聯(liá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ù)時， (Kn)=n；當(dāng)當(dāng)n為偶數(shù)時，為偶數(shù)時， (Kn)=n 1。例例17.517.5 證明證明(W4)=(W4)=3，(W5)=(W5)=4。由維津定理可知結(jié)論是正確的。由維津定理可知結(jié)論是正確的。 解答解答例例 求下面所示各圖的邊色數(shù)。求下面所示各圖的邊色數(shù)。 小節(jié)結(jié)束小節(jié)結(jié)束q (1)中無奇長回路，所以它為二部圖，由定理中無奇長回路，所以它為二部圖，由定理17.30可知可知=4。q 由維津定理可知，由維津定理可知，(2)中中=4，又存在又存在4種顏色的邊著色，種顏色的邊著色，所以所以4，因而因而=4。解答解答本章主要內(nèi)容本章主要內(nèi)容q 頂點的著色與點色數(shù)。頂點的著色與點色數(shù)。q 關(guān)于點色數(shù)的一些定理。關(guān)于點色數(shù)的一些定理。q 地圖及其面著色、面色數(shù)。地圖及其面著色、面色數(shù)。q 平面圖的四色定理。平面圖的四色定理。q 邊著色及邊色數(shù)。邊著色及邊色數(shù)。q 關(guān)于邊著色的一些定理。