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

1、6/28/2022 3:19 PM Discrete Math. , Chen Chen1離散數(shù)學離散數(shù)學Discrete MathematicsDiscrete Mathematics6/28/2022 3:19 PM Discrete Math. , Chen Chen2主要內(nèi)容主要內(nèi)容n支配集、點覆蓋集與點獨立集支配集、點覆蓋集與點獨立集n邊覆蓋與匹配邊覆蓋與匹配n二部圖中的匹配二部圖中的匹配n點著色點著色n地圖著色與平面圖的點著色地圖著色與平面圖的點著色n邊著色邊著色6/28/2022 3:19 PM Discrete Math. , Chen Chen3支配集與支配數(shù)支配集與支配數(shù)定

2、義定義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)最小支配集中的元素個數(shù)最小支配集中的元素個數(shù)6/28/2022 3:19 PM Discrete Math. , Chen Chen4最小支配集為極小支配集，但反之不真最小支配集為極小支配集，但反之不真.另外，極小支配集與最小支配集都可能不惟一另外，極小支配集與最小支配集都可能不惟一.又易知完全圖、輪圖、星

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

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

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

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

7、因而 e E，e的兩個端點至少一的兩個端點至少一個在個在V*中中. 推論推論 設(shè)設(shè)G為為n階無孤立頂點圖，則階無孤立頂點圖，則V*是極小是極小(最小最小)點覆蓋當點覆蓋當且僅當是極大（最大）點獨立集，從而有且僅當是極大（最大）點獨立集，從而有 0+ 0=n6/28/2022 3:19 PM 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* 的真子集不是邊覆蓋的真子集不是邊覆蓋(3) 最小邊覆蓋最

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

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

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

11、錯路徑中，不在M中的邊比在中的邊比在M中的邊中的邊多一條多一條. 交錯圈一定為偶圈交錯圈一定為偶圈. (1) (2) (3)6/28/2022 3:19 PM Discrete Math. , Chen Chen13定理定理18.3 設(shè)設(shè)n階圖階圖G中無孤立頂點中無孤立頂點.(1) 設(shè)設(shè)M為為G中一個最大匹配，對于中一個最大匹配，對于G中每個中每個M非飽和點均取非飽和點均取一條與其關(guān)聯(lián)的邊，組成邊集一條與其關(guān)聯(lián)的邊，組成邊集N，則，則W=M N為為G中最小邊覆中最小邊覆蓋蓋. (2) 設(shè)設(shè)W1為為G中一個最小邊覆蓋；若中一個最小邊覆蓋；若W1中存在相鄰的邊就移中存在相鄰的邊就移去其中的一條，設(shè)

12、移去的邊集為去其中的一條，設(shè)移去的邊集為N1，則，則M1=W1 N1為為G中一中一個最大匹配個最大匹配. (3) G中邊覆蓋數(shù)中邊覆蓋數(shù) 1與匹配數(shù)與匹配數(shù) 1滿足滿足 1+ 1=n. 證明見教材證明見教材. 6/28/2022 3:19 PM Discrete Math. , Chen Chen14推論推論 設(shè)設(shè)G是是n階無孤立頂點的圖階無孤立頂點的圖. M為為G中的匹配，中的匹配，W是是G中中的邊覆蓋，則的邊覆蓋，則 |M| |W|，等號成立時，等號成立時，M為為G中完美匹配，中完美匹配，W為為G中最小邊覆蓋中最小邊覆蓋. 圖中，紅邊為匹配圖中，紅邊為匹配M中的邊中的邊. (1)中匹配是最

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

14、增廣廣交錯路徑交錯路徑. 設(shè)設(shè)H = GM1 M，若，若H=，M=M1，結(jié)論為真，結(jié)論為真. 否否則則H. 此時，此時，H中的交錯圈中的交錯圈(若存在若存在)，其上，其上M與與M1的邊的邊數(shù)相等，且所有交錯路徑上，數(shù)相等，且所有交錯路徑上，M與與M1中的邊數(shù)也相等（因中的邊數(shù)也相等（因為為M與與M1均無可增廣路徑）均無可增廣路徑）. 定理定理18.4 M為為G中最大匹配當且僅當中最大匹配當且僅當G中不含中不含M的可增廣交的可增廣交錯路徑錯路徑.6/28/2022 3:19 PM Discrete Math. , Chen Chen16定義定義18.7 設(shè)設(shè)G=為二部圖，為二部圖，|V1| |V

15、2|，M是是G中中最大匹配，若最大匹配，若V1中頂點全是中頂點全是M飽和點，則稱飽和點，則稱M為為G中中完備匹完備匹配配. |V1|=|V2| 時完備匹配變成時完備匹配變成完美匹配完美匹配. 圖中，紅邊組成各圖的一個匹配，圖中，紅邊組成各圖的一個匹配，(1)中為完備匹配，中為完備匹配，(2)中匹中匹配不是完備的，配不是完備的，(2)中無完備匹配，中無完備匹配，(3中匹配是完備的，也是完中匹配是完備的，也是完美的美的. (1) (2) (3)6/28/2022 3:19 PM Discrete Math. , Chen Chen17定理定理18.5 （Hall定理定理）設(shè)二部圖）設(shè)二部圖G=中，

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

17、足相異性條件證明要點：滿足相異性條件. 定理定理18.6中的條件稱為中的條件稱為 t（t 1）條件條件.6/28/2022 3:19 PM Discrete Math. , Chen Chen18某課題組要從某課題組要從a, b, c, d, e 5人中派人中派3人分別到上海、廣州、香人分別到上海、廣州、香港去開會港去開會. 已知已知a只想去上海，只想去上海，b只想去廣州，只想去廣州，c, d, e都表示都表示想想去廣州或香港去廣州或香港. 問該課題組在滿足個人要求的條件下，共有問該課題組在滿足個人要求的條件下，共有幾種派遣方案？幾種派遣方案？ 解解 用二部圖中的匹配理論解本題方便用二部圖中的

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種派遣方案種派遣方案(請請給出這給出這9種方案種方案). 6/28/2022 3:19 PM Discrete Math. , Chen Chen19定義定義17.9 (1) 圖圖G的一種的一種點著色點著色給圖給圖G的每個頂點涂上一種顏色，的每個頂點涂上一種顏色，使相鄰頂點具有不同顏色使

19、相鄰頂點具有不同顏色(2) 對對G進行進行k著色著色（G是是k-可著色的）可著色的）能用能用k種顏色給種顏色給G的頂點著色的頂點著色(3) G的的色數(shù)色數(shù) (G)=kG是是k-可著色的，但不是可著色的，但不是(k 1)-可著可著色的色的. 6/28/2022 3:19 PM Discrete Math. , Chen Chen20定理定理17.19 (G)=1當且僅當當且僅當G為零圖為零圖定理定理17.20 (Kn)=n 定理定理17.21 若若G為奇圈或奇階輪圖，則為奇圈或奇階輪圖，則 (G)=3，若，若G為偶階為偶階輪輪圖，則圖，則 (G)=4.定理定理17.22 若若G的邊集非空，則的邊

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

21、e Math. , Chen Chen22定義定義17.10 (1) 地圖地圖連通無橋平面圖（嵌入）與所有的面連通無橋平面圖（嵌入）與所有的面(2) 國家國家地圖的面地圖的面(3) 兩個國家兩個國家相鄰相鄰它們的邊界至少有一條公共邊它們的邊界至少有一條公共邊在上圖的地圖中，有在上圖的地圖中，有5個國家，其中個國家，其中1與與2相鄰，相鄰，1與與4相鄰，相鄰，2,3,4均與均與5相鄰相鄰.6/28/2022 3:19 PM Discrete Math. , Chen Chen23定義定義17.11(1) 地圖地圖G的的面著色面著色對對G的每個國家涂上一種顏色，相的每個國家涂上一種顏色，相鄰國家涂

22、不同顏色鄰國家涂不同顏色(2) G是是k-面可著色的面可著色的能用能用k種顏色給種顏色給G的面著色的面著色(3) G的的面色數(shù)面色數(shù) *(G)=k最少用最少用k種顏色給種顏色給G的面著色的面著色. 地圖的面著色轉(zhuǎn)化成對偶圖的點著色地圖的面著色轉(zhuǎn)化成對偶圖的點著色定理定理17.25 地圖地圖G是是k-面可著色的當且僅當它的對偶圖面可著色的當且僅當它的對偶圖G*是是k-點可著色的點可著色的. 證明簡單證明簡單五色定理五色定理定理定理17.26 任何平面圖都是任何平面圖都是5-可著色的可著色的剩下的大問題：四色猜想是否為真剩下的大問題：四色猜想是否為真6/28/2022 3:19 PM Discre

23、te Math. , Chen Chen24定義定義17.12 (1) 對對G的邊著色的邊著色每條邊著一種顏色，相鄰的邊不同色每條邊著一種顏色，相鄰的邊不同色(2) G是是k-邊可著色的邊可著色的能用能用k種顏色給種顏色給G的邊著色的邊著色(3) G的邊色數(shù)的邊色數(shù) (G)最少用最少用k種顏色給種顏色給G的邊著色的邊著色定理定理17.27 (Vizing定理定理 )G為簡單平面圖，則為簡單平面圖，則 (G) (G) (G)+1. 定理定理17.28 偶圈邊色數(shù)為偶圈邊色數(shù)為2，奇圈邊色數(shù)為，奇圈邊色數(shù)為3.定理定理17.29 (Wn) = n 1, n 4. 定理定理17.30 二部圖的邊色數(shù)

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

25、立集(匹配匹配)、點著色、邊著色、面著色、色數(shù)等、點著色、邊著色、面著色、色數(shù)等概念概念n會求階數(shù)會求階數(shù) n 較小或特殊圖的較小或特殊圖的 0, 0, 0, 1, 1n會用二部圖中匹配的理論解簡單問題會用二部圖中匹配的理論解簡單問題n理解并記住地圖面著色與它的對偶圖點著色之間的關(guān)系理解并記住地圖面著色與它的對偶圖點著色之間的關(guān)系n會用點色數(shù)及邊色數(shù)解決一些實際問題會用點色數(shù)及邊色數(shù)解決一些實際問題. 6/28/2022 3:19 PM Discrete Math. , Chen Chen26(1) G中有不是最小支配集的極小支配集嗎？求支配數(shù)中有不是最小支配集的極小支配集嗎？求支配數(shù) 0(2

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

27、5. 只有最后一個不是最小的，只有最后一個不是最小的， 0=2(2) 共有共有2個極小點覆蓋集：個極小點覆蓋集：v1,v3, v2,v4,v5，前者是最小，前者是最小 的，的， 0=2(3) 共有共有2個極大點獨立集：個極大點獨立集：v1,v3, v2,v4,v5，后者是最大，后者是最大 的，的， 0=3(4) G不可能有完美匹配，因為它的階數(shù)不可能有完美匹配，因為它的階數(shù)n=5(奇數(shù)奇數(shù))， 1=2 (G的最大匹配為的最大匹配為2元集元集)(5) 由定理由定理18.3立刻可知立刻可知 1=36/28/2022 3:19 PM Discrete Math. , Chen Chen282. 彼得

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

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

30、的完美匹配為中的完美匹配為Kn中的最大匹配，故中的最大匹配，故Kn中的中的 ，于，于是是 3求無向完全圖求無向完全圖Kn（n 3）中的）中的 0, 1, 0, 1. 2n)(22111nnnn211n211n)(21111nn6/28/2022 3:19 PM Discrete Math. , Chen Chen31 由二部圖的定義及題中參數(shù)的定義，不難看出由二部圖的定義及題中參數(shù)的定義，不難看出 0= 1=r， 1= 0=s. 4求完全二部圖求完全二部圖Kr,s（1 r s）的）的 0, 1, 0, 1.6/28/2022 3:20 PM Discrete Math. , Chen Chen

31、325. 求圖的點色數(shù)求圖的點色數(shù) , 邊色數(shù)邊色數(shù) , 以及面色數(shù)以及面色數(shù) *. 解解 (1) 因為因為G中含奇圈，所以中含奇圈，所以3，由布魯克斯定理知由布魯克斯定理知 =4, 又容易證明不能用又容易證明不能用3種顏色涂色：種顏色涂色：由于由于a, b, c 彼此相鄰，因而至少用彼此相鄰，因而至少用3種顏色涂色，設(shè)用顏色種顏色涂色，設(shè)用顏色 , , 分分別給別給a, b, c 涂色涂色. 此時最少還用這此時最少還用這三種顏色給三種顏色給d, e, f 涂色，而且涂色，而且d, e, f也只能用顏色也只能用顏色 , 和和 ，這樣，這樣g只能只能用另一種顏色，比如用另一種顏色，比如 涂色，所涂色，所以以 =4. 6/28/2022 3:20 PM Discrete Ma