離散數(shù)學(xué)第18章 支配集 覆蓋集獨(dú)立集配與著色.

1、5/26/2022 11:38 AM Discrete Math. , Chen Chen1離散數(shù)學(xué)離散數(shù)學(xué)Discrete MathematicsDiscrete Mathematics5/26/2022 11:38 AM Discrete Math. , Chen Chen2主要內(nèi)容主要內(nèi)容n支配集、點(diǎn)覆蓋集與點(diǎn)獨(dú)立集支配集、點(diǎn)覆蓋集與點(diǎn)獨(dú)立集n邊覆蓋與匹配邊覆蓋與匹配n二部圖中的匹配二部圖中的匹配n點(diǎn)著色點(diǎn)著色n地圖著色與平面圖的點(diǎn)著色地圖著色與平面圖的點(diǎn)著色n邊著色邊著色5/26/2022 11:38 AM Discrete Math. , Chen Chen3支配集與支配數(shù)支配集與支

2、配數(shù)定義定義18.1 設(shè)設(shè)G=，V* V.(1) V*為為支配集支配集 vi V V*, vj V*，使得，使得(vi,vj) E (2) V*為為極小支配集極小支配集V*的真子集不是支配集的真子集不是支配集(3) 最小支配集最小支配集元素最少的支配集元素最少的支配集(4) 支配數(shù)支配數(shù) 0(G)最小支配集中的元素個(gè)數(shù)最小支配集中的元素個(gè)數(shù)5/26/2022 11:38 AM Discrete Math. , Chen Chen4最小支配集為極小支配集，但反之不真最小支配集為極小支配集，但反之不真.另外，極小支配集與最小支配集都可能不惟一另外，極小支配集與最小支配集都可能不惟一.又易知完全圖、

3、輪圖、星形圖的支配數(shù)均是又易知完全圖、輪圖、星形圖的支配數(shù)均是1. 圖中，圖中，(1),(2),(3)(彼得松圖彼得松圖)的支配數(shù)分別為的支配數(shù)分別為1，2，3. 請(qǐng)各找出一個(gè)最小支配集請(qǐng)各找出一個(gè)最小支配集. (1) (2) (3) 5/26/2022 11:38 AM Discrete Math. , Chen Chen5定義定義18.2 設(shè)設(shè)G=，V* V.(1) 點(diǎn)獨(dú)立集點(diǎn)獨(dú)立集V*V*中頂點(diǎn)彼此不相鄰中頂點(diǎn)彼此不相鄰(2) V*為為極大點(diǎn)獨(dú)立集極大點(diǎn)獨(dú)立集V*中再加入任何頂點(diǎn)就不是點(diǎn)中再加入任何頂點(diǎn)就不是點(diǎn)獨(dú)立集獨(dú)立集(3) 最大點(diǎn)獨(dú)立集最大點(diǎn)獨(dú)立集元素最多的點(diǎn)獨(dú)立集元素最多的點(diǎn)獨(dú)立

4、集(4) 點(diǎn)獨(dú)立數(shù)點(diǎn)獨(dú)立數(shù)最大點(diǎn)獨(dú)立集中的元素個(gè)數(shù)，記為最大點(diǎn)獨(dú)立集中的元素個(gè)數(shù)，記為 0 在圖中，點(diǎn)獨(dú)立數(shù)依次為在圖中，點(diǎn)獨(dú)立數(shù)依次為2, 2, 3. (1) (2) (3) 5/26/2022 11:38 AM Discrete Math. , Chen Chen6定理定理18.1 設(shè)設(shè)G=中無(wú)孤立點(diǎn)，則中無(wú)孤立點(diǎn)，則G的極大點(diǎn)獨(dú)立集都的極大點(diǎn)獨(dú)立集都是是極小支配集極小支配集. 證明線索：證明線索：(1) 設(shè)設(shè)V*為為G的極大點(diǎn)獨(dú)立集，證明它也是支配集的極大點(diǎn)獨(dú)立集，證明它也是支配集. v V V*，必，必 vV*，使，使(v,v ) E，否則，否則 v0 V V*不與不與V*中任何頂點(diǎn)相

5、鄰，則中任何頂點(diǎn)相鄰，則V* v0仍為點(diǎn)獨(dú)立集，這與仍為點(diǎn)獨(dú)立集，這與V*是是極大點(diǎn)獨(dú)立集矛盾極大點(diǎn)獨(dú)立集矛盾. (2) 證證V*是極小支配集是極小支配集. 只需證只需證V*的真子集不是支配集的真子集不是支配集.特別注意，特別注意，定理定理18.1其逆不真其逆不真. 5/26/2022 11:38 AM Discrete Math. , Chen Chen7定義定義18.3 設(shè)設(shè)G=, V* V.(1) V*是是點(diǎn)覆蓋集點(diǎn)覆蓋集 e E， v V*，使，使e與與v關(guān)聯(lián)關(guān)聯(lián)(2) V*是是極小點(diǎn)覆蓋集極小點(diǎn)覆蓋集V*的任何真子集都不是點(diǎn)覆蓋集的任何真子集都不是點(diǎn)覆蓋集(3) 最小點(diǎn)覆蓋集最小點(diǎn)覆

6、蓋集(或最小點(diǎn)覆蓋或最小點(diǎn)覆蓋)頂點(diǎn)數(shù)最少的點(diǎn)覆蓋集頂點(diǎn)數(shù)最少的點(diǎn)覆蓋集(4) 點(diǎn)覆蓋數(shù)點(diǎn)覆蓋數(shù) 0(G)最小點(diǎn)覆蓋的元素個(gè)數(shù)最小點(diǎn)覆蓋的元素個(gè)數(shù)圖中，點(diǎn)覆蓋數(shù)依次為圖中，點(diǎn)覆蓋數(shù)依次為3，4，7.5/26/2022 11:38 AM Discrete Math. , Chen Chen8定理定理18.2 設(shè)設(shè)G=無(wú)孤立點(diǎn)，無(wú)孤立點(diǎn)，V* V，則，則V*是點(diǎn)覆蓋當(dāng)且是點(diǎn)覆蓋當(dāng)且僅當(dāng)為點(diǎn)獨(dú)立集僅當(dāng)為點(diǎn)獨(dú)立集證證 必要性必要性. 若若 vi, vj 相鄰，即相鄰，即(vi,vj) E，則，則V*中頂點(diǎn)不能覆中頂點(diǎn)不能覆蓋蓋(vi,vj)，這是矛盾的，這是矛盾的.充分性充分性. 由于是點(diǎn)獨(dú)立集，因而

7、由于是點(diǎn)獨(dú)立集，因而 e E，e的兩個(gè)端點(diǎn)至少一的兩個(gè)端點(diǎn)至少一個(gè)在個(gè)在V*中中. 推論推論 設(shè)設(shè)G為為n階無(wú)孤立頂點(diǎn)圖，則階無(wú)孤立頂點(diǎn)圖，則V*是極小是極小(最小最小)點(diǎn)覆蓋當(dāng)點(diǎn)覆蓋當(dāng)且僅當(dāng)是極大（最大）點(diǎn)獨(dú)立集，從而有且僅當(dāng)是極大（最大）點(diǎn)獨(dú)立集，從而有 0+ 0=n5/26/2022 11:38 AM Discrete Math. , Chen Chen9邊覆蓋集與邊覆蓋數(shù)邊覆蓋集與邊覆蓋數(shù)定義定義18.4 設(shè)設(shè)G=，E* E，(1) E* 為為邊覆蓋集邊覆蓋集 v V， e E，使得，使得v與與e關(guān)聯(lián)關(guān)聯(lián)(2) E* 為為極小邊覆蓋極小邊覆蓋E* 的真子集不是邊覆蓋的真子集不是邊覆蓋(

8、3) 最小邊覆蓋最小邊覆蓋邊數(shù)最少的邊覆蓋邊數(shù)最少的邊覆蓋(4) 邊覆蓋數(shù)邊覆蓋數(shù) 1最小邊覆蓋中元素個(gè)數(shù)最小邊覆蓋中元素個(gè)數(shù) 圖中各圖的邊覆蓋數(shù)依次為圖中各圖的邊覆蓋數(shù)依次為3, 4, 5. 請(qǐng)各找出一個(gè)最小邊覆蓋請(qǐng)各找出一個(gè)最小邊覆蓋.5/26/2022 11:38 AM Discrete Math. , Chen Chen10定義定義18.5 設(shè)設(shè)G=, E* E，(1) 匹配匹配(邊獨(dú)立集邊獨(dú)立集)E*E*中各邊均不相鄰中各邊均不相鄰(2) 極大匹配極大匹配E*E*中不能再加其他邊了中不能再加其他邊了(3) 最大匹配最大匹配邊數(shù)最多的匹配邊數(shù)最多的匹配(4) 匹配數(shù)匹配數(shù)最大匹配中的邊

9、數(shù)，記為最大匹配中的邊數(shù)，記為 1 上圖中各圖的匹配數(shù)依次為上圖中各圖的匹配數(shù)依次為3, 3, 4. 5/26/2022 11:38 AM Discrete Math. , Chen Chen11定義定義18.6 設(shè)設(shè)M為為G中一個(gè)匹配中一個(gè)匹配.(1) vi 與與vj 被被M匹配匹配(vi,vj) M(2) v為為M飽和點(diǎn)飽和點(diǎn)有有M中邊與中邊與v關(guān)聯(lián)關(guān)聯(lián)(3) v為為M非飽和點(diǎn)非飽和點(diǎn)無(wú)無(wú)M中邊與中邊與v關(guān)聯(lián)關(guān)聯(lián)(4) M為為完美匹配完美匹配G中無(wú)中無(wú)M非飽和點(diǎn)非飽和點(diǎn)(5) M的的交錯(cuò)路徑交錯(cuò)路徑從從M與與E M中交替取邊構(gòu)成的中交替取邊構(gòu)成的G中路徑中路徑(6) M的的可增廣交錯(cuò)路徑可

10、增廣交錯(cuò)路徑起、終點(diǎn)都是起、終點(diǎn)都是M非飽和點(diǎn)的交非飽和點(diǎn)的交錯(cuò)路徑錯(cuò)路徑(7) M的的交錯(cuò)圈交錯(cuò)圈由由M與與E M中的邊交替出現(xiàn)構(gòu)成的中的邊交替出現(xiàn)構(gòu)成的G中圈中圈上圖中，只有第一個(gè)圖存在完美匹配上圖中，只有第一個(gè)圖存在完美匹配5/26/2022 11:38 AM Discrete Math. , Chen Chen12設(shè)紅色邊在匹配設(shè)紅色邊在匹配M中，綠色邊不在中，綠色邊不在M中，則圖中，則圖(1)中的兩條路中的兩條路徑均為可增廣的交錯(cuò)路徑；徑均為可增廣的交錯(cuò)路徑；(2)中的全不是可增廣的交錯(cuò)路中的全不是可增廣的交錯(cuò)路徑；徑；(3)中是一個(gè)交錯(cuò)圈中是一個(gè)交錯(cuò)圈. 不難看出，可增廣交錯(cuò)路徑中

11、，不在不難看出，可增廣交錯(cuò)路徑中，不在M中的邊比在中的邊比在M中的邊中的邊多一條多一條. 交錯(cuò)圈一定為偶圈交錯(cuò)圈一定為偶圈. (1) (2) (3)5/26/2022 11:38 AM Discrete Math. , Chen Chen13定理定理18.3 設(shè)設(shè)n階圖階圖G中無(wú)孤立頂點(diǎn)中無(wú)孤立頂點(diǎn).(1) 設(shè)設(shè)M為為G中一個(gè)最大匹配，對(duì)于中一個(gè)最大匹配，對(duì)于G中每個(gè)中每個(gè)M非飽和點(diǎn)均取非飽和點(diǎn)均取一條與其關(guān)聯(lián)的邊，組成邊集一條與其關(guān)聯(lián)的邊，組成邊集N，則，則W=M N為為G中最小邊覆中最小邊覆蓋蓋. (2) 設(shè)設(shè)W1為為G中一個(gè)最小邊覆蓋；若中一個(gè)最小邊覆蓋；若W1中存在相鄰的邊就移中存在相

12、鄰的邊就移去其中的一條，設(shè)移去的邊集為去其中的一條，設(shè)移去的邊集為N1，則，則M1=W1 N1為為G中一中一個(gè)最大匹配個(gè)最大匹配. (3) G中邊覆蓋數(shù)中邊覆蓋數(shù) 1與匹配數(shù)與匹配數(shù) 1滿足滿足 1+ 1=n. 證明見教材證明見教材. 5/26/2022 11:38 AM Discrete Math. , Chen Chen14推論推論 設(shè)設(shè)G是是n階無(wú)孤立頂點(diǎn)的圖階無(wú)孤立頂點(diǎn)的圖. M為為G中的匹配，中的匹配，W是是G中中的邊覆蓋，則的邊覆蓋，則 |M| |W|，等號(hào)成立時(shí)，等號(hào)成立時(shí)，M為為G中完美匹配，中完美匹配，W為為G中最小邊覆蓋中最小邊覆蓋. 圖中，紅邊為匹配圖中，紅邊為匹配M中的

13、邊中的邊. (1)中匹配是最大匹配中匹配是最大匹配. (2)中紅中紅邊與綠邊組成最小邊覆蓋邊與綠邊組成最小邊覆蓋W.反之，由反之，由(2)的最小邊覆蓋的最小邊覆蓋W產(chǎn)生產(chǎn)生(1)中的最大匹配中的最大匹配M.(1) (2)5/26/2022 11:38 AM Discrete Math. , Chen Chen15證明線索：證明線索：必要性必要性. 若含可增廣交錯(cuò)路徑，可生成比若含可增廣交錯(cuò)路徑，可生成比M更大的匹配更大的匹配.充分性充分性. 設(shè)設(shè)M和和M1分別為不含可增廣路徑的匹配和最大匹分別為不含可增廣路徑的匹配和最大匹配，只要證明配，只要證明 |M|=|M1| 即可即可. 由必要性知，由必

14、要性知，M1也不含可增也不含可增廣廣交錯(cuò)路徑交錯(cuò)路徑. 設(shè)設(shè)H = GM1 M，若，若H=，M=M1，結(jié)論為真，結(jié)論為真. 否否則則H. 此時(shí)，此時(shí)，H中的交錯(cuò)圈中的交錯(cuò)圈(若存在若存在)，其上，其上M與與M1的邊的邊數(shù)相等，且所有交錯(cuò)路徑上，數(shù)相等，且所有交錯(cuò)路徑上，M與與M1中的邊數(shù)也相等（因中的邊數(shù)也相等（因?yàn)闉镸與與M1均無(wú)可增廣路徑）均無(wú)可增廣路徑）. 定理定理18.4 M為為G中最大匹配當(dāng)且僅當(dāng)中最大匹配當(dāng)且僅當(dāng)G中不含中不含M的可增廣交的可增廣交錯(cuò)路徑錯(cuò)路徑.5/26/2022 11:38 AM Discrete Math. , Chen Chen16定義定義18.7 設(shè)設(shè)G=為

15、二部圖，為二部圖，|V1| |V2|，M是是G中中最大匹配，若最大匹配，若V1中頂點(diǎn)全是中頂點(diǎn)全是M飽和點(diǎn)，則稱飽和點(diǎn)，則稱M為為G中中完備匹完備匹配配. |V1|=|V2| 時(shí)完備匹配變成時(shí)完備匹配變成完美匹配完美匹配. 圖中，紅邊組成各圖的一個(gè)匹配，圖中，紅邊組成各圖的一個(gè)匹配，(1)中為完備匹配，中為完備匹配，(2)中匹中匹配不是完備的，配不是完備的，(2)中無(wú)完備匹配，中無(wú)完備匹配，(3中匹配是完備的，也是完中匹配是完備的，也是完美的美的. (1) (2) (3)5/26/2022 11:38 AM Discrete Math. , Chen Chen17定理定理18.5 （Hall定

16、理定理）設(shè)二部圖）設(shè)二部圖G=中，中，|V1| |V2|. G中存在從中存在從V1到到V2的完備匹配當(dāng)且僅當(dāng)?shù)耐陚淦ヅ洚?dāng)且僅當(dāng)V1中任意中任意k(k=1,2,|V1|)個(gè)頂點(diǎn)至少與個(gè)頂點(diǎn)至少與V2中的中的k個(gè)頂點(diǎn)相鄰個(gè)頂點(diǎn)相鄰.本定理中的條件常稱為本定理中的條件常稱為“相異性條件相異性條件”. 由由Hall定理立刻可知，上圖中定理立刻可知，上圖中(2)為什么沒有完備匹配為什么沒有完備匹配.定理定理18.6 設(shè)二部圖設(shè)二部圖G=中，中，V1中每個(gè)頂點(diǎn)至少關(guān)聯(lián)中每個(gè)頂點(diǎn)至少關(guān)聯(lián)t (t 1)條邊，而條邊，而V2中每個(gè)頂點(diǎn)至多關(guān)聯(lián)中每個(gè)頂點(diǎn)至多關(guān)聯(lián) t 條邊，則條邊，則G 中存在中存在V1到到V2的

17、完備匹配的完備匹配. 證明要點(diǎn)：滿足相異性條件證明要點(diǎn)：滿足相異性條件. 定理定理18.6中的條件稱為中的條件稱為 t（t 1）條件條件.5/26/2022 11:38 AM Discrete Math. , Chen Chen18某課題組要從某課題組要從a, b, c, d, e 5人中派人中派3人分別到上海、廣州、香人分別到上海、廣州、香港去開會(huì)港去開會(huì). 已知已知a只想去上海，只想去上海，b只想去廣州，只想去廣州，c, d, e都表示都表示想想去廣州或香港去廣州或香港. 問該課題組在滿足個(gè)人要求的條件下，共有問該課題組在滿足個(gè)人要求的條件下，共有幾種派遣方案？幾種派遣方案？ 解解 用二部

18、圖中的匹配理論解本題方便用二部圖中的匹配理論解本題方便.令令G=，其中，其中V1=s, g, x，s, g, x分別表示上海、廣分別表示上海、廣州和香港州和香港. V2=a, b, c, d, e, E=(u,v) | u V1, v V2, v想去想去u. G如圖所示如圖所示.G滿足相異性條件，因而可滿足相異性條件，因而可派遣，共有派遣，共有9種派遣方案種派遣方案(請(qǐng)請(qǐng)給出這給出這9種方案種方案). 5/26/2022 11:38 AM Discrete Math. , Chen Chen19定義定義17.9 (1) 圖圖G的一種的一種點(diǎn)著色點(diǎn)著色給圖給圖G的每個(gè)頂點(diǎn)涂上一種顏色，的每個(gè)頂點(diǎn)

19、涂上一種顏色，使相鄰頂點(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)-可著可著色的色的. 5/26/2022 11:38 AM Discrete Math. , Chen Chen20定理定理17.19 (G)=1當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G為零圖為零圖定理定理17.20 (Kn)=n 定理定理17.21 若若G為奇圈或奇階輪圖，則為奇圈或奇階輪圖，則 (G)=3，若，若G為偶階為偶階輪輪圖，則圖，則 (G)=4.定理

20、定理17.22 若若G的邊集非空，則的邊集非空，則 (G)=2當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G為二部圖為二部圖. 上述各圖中，色數(shù)分別為上述各圖中，色數(shù)分別為3，3，4，5，為什么？為什么？5/26/2022 11:38 AM Discrete Math. , Chen Chen21定理定理17.23 對(duì)于任意無(wú)向圖對(duì)于任意無(wú)向圖G，均有，均有 (G) (G)+1證明線索：對(duì)證明線索：對(duì)G的階數(shù)的階數(shù)n做歸納做歸納.定理定理17.24 若連通無(wú)向圖若連通無(wú)向圖G不是不是Kn,（n 3），也不是奇數(shù)階），也不是奇數(shù)階的圈，則的圈，則 (G) (G)定理定理17.24稱為布魯克斯定理稱為布魯克斯定理. 5/26

21、/2022 11:38 AM Discrete Math. , Chen Chen22定義定義17.10 (1) 地圖地圖連通無(wú)橋平面圖（嵌入）與所有的面連通無(wú)橋平面圖（嵌入）與所有的面(2) 國(guó)家國(guó)家地圖的面地圖的面(3) 兩個(gè)國(guó)家兩個(gè)國(guó)家相鄰相鄰它們的邊界至少有一條公共邊它們的邊界至少有一條公共邊在上圖的地圖中，有在上圖的地圖中，有5個(gè)國(guó)家，其中個(gè)國(guó)家，其中1與與2相鄰，相鄰，1與與4相鄰，相鄰，2,3,4均與均與5相鄰相鄰.5/26/2022 11:38 AM Discrete Math. , Chen Chen23定義定義17.11(1) 地圖地圖G的的面著色面著色對(duì)對(duì)G的每個(gè)國(guó)家涂上

22、一種顏色，相的每個(gè)國(guó)家涂上一種顏色，相鄰國(guó)家涂不同顏色鄰國(guó)家涂不同顏色(2) G是是k-面可著色的面可著色的能用能用k種顏色給種顏色給G的面著色的面著色(3) G的的面色數(shù)面色數(shù) *(G)=k最少用最少用k種顏色給種顏色給G的面著色的面著色. 地圖的面著色轉(zhuǎn)化成對(duì)偶圖的點(diǎn)著色地圖的面著色轉(zhuǎn)化成對(duì)偶圖的點(diǎn)著色定理定理17.25 地圖地圖G是是k-面可著色的當(dāng)且僅當(dāng)它的對(duì)偶圖面可著色的當(dāng)且僅當(dāng)它的對(duì)偶圖G*是是k-點(diǎn)可著色的點(diǎn)可著色的. 證明簡(jiǎn)單證明簡(jiǎn)單五色定理五色定理定理定理17.26 任何平面圖都是任何平面圖都是5-可著色的可著色的剩下的大問題：四色猜想是否為真剩下的大問題：四色猜想是否為真5

23、/26/2022 11:38 AM Discrete Math. , Chen Chen24定義定義17.12 (1) 對(duì)對(duì)G的邊著色的邊著色每條邊著一種顏色，相鄰的邊不同色每條邊著一種顏色，相鄰的邊不同色(2) G是是k-邊可著色的邊可著色的能用能用k種顏色給種顏色給G的邊著色的邊著色(3) G的邊色數(shù)的邊色數(shù) (G)最少用最少用k種顏色給種顏色給G的邊著色的邊著色定理定理17.27 (Vizing定理定理 )G為簡(jiǎn)單平面圖，則為簡(jiǎn)單平面圖，則 (G) (G) (G)+1. 定理定理17.28 偶圈邊色數(shù)為偶圈邊色數(shù)為2，奇圈邊色數(shù)為，奇圈邊色數(shù)為3.定理定理17.29 (Wn) = n 1

24、, n 4. 定理定理17.30 二部圖的邊色數(shù)等于最大度二部圖的邊色數(shù)等于最大度.定理定理17.31 n為奇數(shù)（為奇數(shù)（n 1）時(shí)，）時(shí)， (Kn)=n； n為偶數(shù)時(shí)，為偶數(shù)時(shí)， (Kn)=n 1. 5/26/2022 11:38 AM Discrete Math. , Chen Chen25主要內(nèi)容主要內(nèi)容n(點(diǎn)點(diǎn))支配支配集、點(diǎn)覆蓋集、點(diǎn)獨(dú)立集集、點(diǎn)覆蓋集、點(diǎn)獨(dú)立集n邊覆蓋集、匹配（邊獨(dú)立集）邊覆蓋集、匹配（邊獨(dú)立集）n二部圖中的完備匹配二部圖中的完備匹配n圖的點(diǎn)著色、邊著色、地圖著色圖的點(diǎn)著色、邊著色、地圖著色基本要求基本要求n深刻理解與支配集、點(diǎn)覆蓋集、邊覆蓋集、點(diǎn)獨(dú)立集、邊深刻理解

25、與支配集、點(diǎn)覆蓋集、邊覆蓋集、點(diǎn)獨(dú)立集、邊獨(dú)立集獨(dú)立集(匹配匹配)、點(diǎn)著色、邊著色、面著色、色數(shù)等、點(diǎn)著色、邊著色、面著色、色數(shù)等概念概念n會(huì)求階數(shù)會(huì)求階數(shù) n 較小或特殊圖的較小或特殊圖的 0, 0, 0, 1, 1n會(huì)用二部圖中匹配的理論解簡(jiǎn)單問題會(huì)用二部圖中匹配的理論解簡(jiǎn)單問題n理解并記住地圖面著色與它的對(duì)偶圖點(diǎn)著色之間的關(guān)系理解并記住地圖面著色與它的對(duì)偶圖點(diǎn)著色之間的關(guān)系n會(huì)用點(diǎn)色數(shù)及邊色數(shù)解決一些實(shí)際問題會(huì)用點(diǎn)色數(shù)及邊色數(shù)解決一些實(shí)際問題. 5/26/2022 11:38 AM Discrete Math. , Chen Chen26(1) G中有不是最小支配集的極小支配集嗎？求支配

26、數(shù)中有不是最小支配集的極小支配集嗎？求支配數(shù) 0(2) G中有不是最小點(diǎn)覆蓋集的極小點(diǎn)覆蓋集嗎？求點(diǎn)覆蓋中有不是最小點(diǎn)覆蓋集的極小點(diǎn)覆蓋集嗎？求點(diǎn)覆蓋數(shù)數(shù) 0 (3) G中有不是最大點(diǎn)獨(dú)立集的極大點(diǎn)獨(dú)立集嗎？求中有不是最大點(diǎn)獨(dú)立集的極大點(diǎn)獨(dú)立集嗎？求 0.(4) G中有完美匹配嗎？為什么？求匹配數(shù)中有完美匹配嗎？為什么？求匹配數(shù) 1(5) 求邊覆蓋數(shù)求邊覆蓋數(shù) 1 1無(wú)向圖無(wú)向圖G如下所示如下所示.5/26/2022 11:38 AM Discrete Math. , Chen Chen27(1) 共有共有8個(gè)極小支配集：個(gè)極小支配集：v1,v2, v1,v3, v1,v4, v1,v5, v

27、2,v3, v3,v4, v3,v5, v2,v4,v5. 只有最后一個(gè)不是最小的，只有最后一個(gè)不是最小的， 0=2(2) 共有共有2個(gè)極小點(diǎn)覆蓋集：個(gè)極小點(diǎn)覆蓋集：v1,v3, v2,v4,v5，前者是最小，前者是最小 的，的， 0=2(3) 共有共有2個(gè)極大點(diǎn)獨(dú)立集：個(gè)極大點(diǎn)獨(dú)立集：v1,v3, v2,v4,v5，后者是最大，后者是最大 的，的， 0=3(4) G不可能有完美匹配，因?yàn)樗碾A數(shù)不可能有完美匹配，因?yàn)樗碾A數(shù)n=5(奇數(shù)奇數(shù))， 1=2 (G的最大匹配為的最大匹配為2元集元集)(5) 由定理由定理18.3立刻可知立刻可知 1=35/26/2022 11:38 AM Discr

28、ete Math. , Chen Chen282. 彼得松圖如下圖所示：彼得松圖如下圖所示：在圖上給出一個(gè)最大點(diǎn)獨(dú)立集和一個(gè)最大匹配，從而求出在圖上給出一個(gè)最大點(diǎn)獨(dú)立集和一個(gè)最大匹配，從而求出 0, 1, 以及以及 0和和 1. 5/26/2022 11:38 AM Discrete Math. , Chen Chen29解 由觀察法在上圖由觀察法在上圖(1)中給出一個(gè)點(diǎn)獨(dú)立集，在中給出一個(gè)點(diǎn)獨(dú)立集，在(2)中給出了一中給出了一個(gè)最大匹配個(gè)最大匹配. 從而得出從而得出 0=4， 1=5. 由定理由定理18.2推論知推論知 0=6，由定理，由定理18.3可知可知 1=5. 5/26/2022 1

29、1:38 AM Discrete Math. , Chen Chen30解解 本題應(yīng)用定理本題應(yīng)用定理8.2的推論（的推論（ 0+ 0=n）與定理）與定理8.3中的中的(3)（ 1+ 1=n）較為方便）較為方便.(1) 由于在由于在Kn中，任何兩個(gè)頂點(diǎn)均相鄰，因而中，任何兩個(gè)頂點(diǎn)均相鄰，因而 0=1，故有，故有 0=n 1（ 0+ 0=n）.(2) n為偶數(shù)時(shí)，為偶數(shù)時(shí)，Kn中存在完美匹配，所以中存在完美匹配，所以 1= ，故，故當(dāng)當(dāng)n為奇數(shù)時(shí)，為奇數(shù)時(shí)，Kn中不可能有完美匹配，中不可能有完美匹配，Kn v（從（從Kn中任意刪中任意刪除頂點(diǎn)除頂點(diǎn)v）為）為Kn 1(n 1為偶數(shù)為偶數(shù))，于是，

30、于是Kn 1中存在完美匹配，中存在完美匹配， 但但Kn 1中的完美匹配為中的完美匹配為Kn中的最大匹配，故中的最大匹配，故Kn中的中的 ，于，于是是 3求無(wú)向完全圖求無(wú)向完全圖Kn（n 3）中的）中的 0, 1, 0, 1. 2n)(22111nnnn211n211n)(21111nn5/26/2022 11:38 AM Discrete Math. , Chen Chen31 由二部圖的定義及題中參數(shù)的定義，不難看出由二部圖的定義及題中參數(shù)的定義，不難看出 0= 1=r， 1= 0=s. 4求完全二部圖求完全二部圖Kr,s（1 r s）的）的 0, 1, 0, 1.5/26/2022 11:

31、38 AM Discrete Math. , Chen Chen325. 求圖的點(diǎn)色數(shù)求圖的點(diǎn)色數(shù) , 邊色數(shù)邊色數(shù) , 以及面色數(shù)以及面色數(shù) *. 解解 (1) 因?yàn)橐驗(yàn)镚中含奇圈，所以中含奇圈，所以3，由布魯克斯定理知由布魯克斯定理知 =4, 又容易證明不能用又容易證明不能用3種顏色涂色：種顏色涂色：由于由于a, b, c 彼此相鄰，因而至少用彼此相鄰，因而至少用3種顏色涂色，設(shè)用顏色種顏色涂色，設(shè)用顏色 , , 分分別給別給a, b, c 涂色涂色. 此時(shí)最少還用這此時(shí)最少還用這三種顏色給三種顏色給d, e, f 涂色，而且涂色，而且d, e, f也只能用顏色也只能用顏色 , 和和 ，這樣，這樣g只能只能用另一種顏色，比如用另一種顏色，比如 涂色，所涂色，所以以 =4. 5/26/2022 11:38 AM Discrete Ma