離散數學DiscreteMathematics7/23/2023

1DiscreteMath.,ChenChen第十八章支配集、覆蓋集、

獨立集、匹配與著色主要內容支配集、點覆蓋集與點獨立集邊覆蓋與匹配二部圖中的匹配點著色地圖著色與平面圖的點著色邊著色7/23/2023

2DiscreteMath.,ChenChen18.1支配集、點覆蓋集

與點獨立集支配集與支配數定義18.1

設G=<V,E>，V*V.(1)V*為支配集——viVV*,vjV*，使得(vi,vj)E

(2)V*為極小支配集——V*的真子集不是支配集(3)最小支配集——元素最少的支配集(4)支配數0(G)——最小支配集中的元素個數7/23/2023

3DiscreteMath.,ChenChen極小與最小支配集之間的關系最小支配集為極小支配集，但反之不真.另外，極小支配集與最小支配集都可能不惟一.又易知完全圖、輪圖、星形圖的支配數均是1.圖中，(1),(2),(3)(彼得松圖)的支配數分別為1，2，3.請各找出一個最小支配集.

(1)(2)(3)

7/23/2023

4DiscreteMath.,ChenChen點獨立集與點獨立數定義18.2

設G=<V,E>，V*V.(1)點獨立集V*——V*中頂點彼此不相鄰(2)V*為極大點獨立集——V*中再加入任何頂點就不是點獨立集(3)最大點獨立集——元素最多的點獨立集(4)點獨立數——最大點獨立集中的元素個數，記為0

在圖中，點獨立數依次為2,2,3.

(1)(2)(3)

7/23/2023

5DiscreteMath.,ChenChen極大獨立集與極小支配集定理18.1

設G=<V,E>中無孤立點，則G的極大點獨立集都是極小支配集.證明線索：(1)設V*為G的極大點獨立集，證明它也是支配集.vVV*，必vV*，使(v,v)E，否則v0

VV*不與V*中任何頂點相鄰，則V*{v0}仍為點獨立集，這與V*是極大點獨立集矛盾.(2)證V*是極小支配集.只需證V*的真子集不是支配集.特別注意，定理18.1其逆不真.

7/23/2023

6DiscreteMath.,ChenChen點覆蓋集與點覆蓋數定義18.3

設G=<V,E>,V*V.(1)V*是點覆蓋集——eE，vV*，使e與v關聯(2)V*是極小點覆蓋集——V*的任何真子集都不是點覆蓋集(3)最小點覆蓋集(或最小點覆蓋)——頂點數最少的點覆蓋集(4)點覆蓋數——0(G)——最小點覆蓋的元素個數圖中，點覆蓋數依次為3，4，7.7/23/2023

7DiscreteMath.,ChenChen點覆蓋集與點獨立集的關系定理18.2

設G=<V,E>無孤立點，V*V，則V*是點覆蓋當且僅當為點獨立集證必要性.若vi,vj相鄰，即(vi,vj)E，則V*中頂點不能覆蓋(vi,vj)，這是矛盾的.充分性.由于是點獨立集，因而eE，e的兩個端點至少一個在V*中.推論設G為n階無孤立頂點圖，則V*是極小(最小)點覆蓋當且僅當是極大（最大）點獨立集，從而有

0+0=n7/23/2023

8DiscreteMath.,ChenChen18.2

邊覆蓋集與匹配邊覆蓋集與邊覆蓋數定義18.4

設G=<V,E>，E*E，(1)E*為邊覆蓋集——vV，eE，使得v與e關聯(2)E*為極小邊覆蓋——E*的真子集不是邊覆蓋(3)最小邊覆蓋——邊數最少的邊覆蓋(4)邊覆蓋數1——最小邊覆蓋中元素個數

圖中各圖的邊覆蓋數依次為3,4,5.請各找出一個最小邊覆蓋.7/23/2023

9DiscreteMath.,ChenChen匹配(邊獨立集)與匹配數(邊獨立數)定義18.5

設G=<V,E>,E*E，(1)匹配(邊獨立集)E*——E*中各邊均不相鄰(2)極大匹配E*——E*中不能再加其他邊了(3)最大匹配——邊數最多的匹配(4)匹配數——最大匹配中的邊數，記為1上圖中各圖的匹配數依次為3,3,4.

7/23/2023

10DiscreteMath.,ChenChen關于匹配中的其他概念定義18.6

設M為G中一個匹配.(1)vi與vj

被M匹配——(vi,vj)M(2)v為M飽和點——有M中邊與v關聯(3)v為M非飽和點——無M中邊與v關聯(4)M為完美匹配——G中無M非飽和點(5)M的交錯路徑——從M與EM中交替取邊構成的G中路徑(6)M的可增廣交錯路徑——起、終點都是M非飽和點的交錯路徑(7)M的交錯圈——由M與EM中的邊交替出現構成的G中圈上圖中，只有第一個圖存在完美匹配7/23/2023

11DiscreteMath.,ChenChen可增廣路徑及交錯圈設紅色邊在匹配M中，綠色邊不在M中，則圖(1)中的兩條路徑均為可增廣的交錯路徑；(2)中的全不是可增廣的交錯路徑；(3)中是一個交錯圈.不難看出，可增廣交錯路徑中，不在M中的邊比在M中的邊多一條.交錯圈一定為偶圈.

(1)(2)(3)7/23/2023

12DiscreteMath.,ChenChen最大匹配與最小邊覆蓋之間關系定理18.3

設n階圖G中無孤立頂點.(1)設M為G中一個最大匹配，對于G中每個M非飽和點均取一條與其關聯的邊，組成邊集N，則W=MN為G中最小邊覆蓋.(2)設W1為G中一個最小邊覆蓋；若W1中存在相鄰的邊就移去其中的一條，設移去的邊集為N1，則M1=W1N1為G中一個最大匹配.(3)G中邊覆蓋數1與匹配數1滿足1+1=n.證明見教材.7/23/2023

13DiscreteMath.,ChenChen推論推論設G是n階無孤立頂點的圖.M為G中的匹配，W是G中的邊覆蓋，則|M||W|，等號成立時，M為G中完美匹配，W為G中最小邊覆蓋.圖中，紅邊為匹配M中的邊.(1)中匹配是最大匹配.(2)中紅邊與綠邊組成最小邊覆蓋W.反之，由(2)的最小邊覆蓋W產生(1)中的最大匹配M.(1)(2)7/23/2023

14DiscreteMath.,ChenChen最大匹配判別定理證明線索：必要性.若含可增廣交錯路徑，可生成比M更大的匹配.充分性.設M和M1分別為不含可增廣路徑的匹配和最大匹配，只要證明|M|=|M1|即可.由必要性知，M1也不含可增廣交錯路徑.設H=G[M1M]，若H=，M=M1，結論為真.否則H.此時，H中的交錯圈(若存在)，其上M與M1的邊數相等，且所有交錯路徑上，M與M1中的邊數也相等（因為M與M1均無可增廣路徑）.

定理18.4

M為G中最大匹配當且僅當G中不含M的可增廣交錯路徑.7/23/2023

15DiscreteMath.,ChenChen18.3

二部圖中的匹配定義18.7

設G=<V1,V2,E>為二部圖，|V1||V2|，M是G中最大匹配，若V1中頂點全是M飽和點，則稱M為G中完備匹配.|V1|=|V2|時完備匹配變成完美匹配.圖中，紅邊組成各圖的一個匹配，(1)中為完備匹配，(2)中匹配不是完備的，(2)中無完備匹配，(3中匹配是完備的，也是完美的.

(1)(2)(3)7/23/2023

16DiscreteMath.,ChenChenHall定理定理18.5

（Hall定理）設二部圖G=<V1,V2,E>中，|V1||V2|.G中存在從V1到V2的完備匹配當且僅當V1中任意k(k=1,2,…,|V1|)個頂點至少與V2中的k個頂點相鄰.本定理中的條件常稱為“相異性條件”.由Hall定理立刻可知，上圖中(2)為什么沒有完備匹配.定理18.6

設二部圖G=<V1,V2,E>中，V1中每個頂點至少關聯t(t1)條邊，而V2中每個頂點至多關聯t條邊，則G中存在V1到V2的完備匹配.證明要點：滿足相異性條件.定理18.6中的條件稱為t（t1）條件.7/23/2023

17DiscreteMath.,ChenChen一個應用實例某課題組要從a,b,c,d,e5人中派3人分別到上海、廣州、香港去開會.已知a只想去上海，b只想去廣州，c,d,e都表示想去廣州或香港.問該課題組在滿足個人要求的條件下，共有幾種派遣方案？解用二部圖中的匹配理論解本題方便.令G=<V1,V2,E>，其中V1={s,g,x}，s,g,x分別表示上海、廣州和香港.V2={a,b,c,d,e},E={(u,v)|uV1,vV2,v想去u}.G如圖所示.G滿足相異性條件，因而可派遣，共有9種派遣方案(請給出這9種方案).

7/23/2023

18DiscreteMath.,ChenChen18.4

點著色定義17.9(1)圖G的一種點著色——給圖G的每個頂點涂上一種顏色，使相鄰頂點具有不同顏色(2)對G進行k著色（G是k-可著色的）——能用k種顏色給G的頂點著色(3)G的色數(G)=k——G是k-可著色的，但不是(k1)-可著色的.7/23/2023

19DiscreteMath.,ChenChen關于頂點著色的幾個簡單結果定理17.19

(G)=1當且僅當G為零圖定理17.20

(Kn)=n

定理17.21

若G為奇圈或奇階輪圖，則(G)=3，若G為偶階輪圖，則(G)=4.定理17.22

若G的邊集非空，則(G)=2當且僅當G為二部圖.上述各圖中，色數分別為3，3，4，5，為什么？7/23/2023

20DiscreteMath.,ChenChen色數的上界定理17.23

對于任意無向圖G，均有(G)

(G)+1證明線索：對G的階數n做歸納.定理17.24

若連通無向圖G不是Kn,（n3），也不是奇數階的圈，則

(G)

(G)定理17.24稱為布魯克斯定理.7/23/2023

21DiscreteMath.,ChenChen18.5

地圖著色與平面圖的點著色定義17.10

(1)地圖——連通無橋平面圖（嵌入）與所有的面(2)國家——地圖的面(3)兩個國家相鄰——它們的邊界至少有一條公共邊在上圖的地圖中，有5個國家，其中1與2相鄰，1與4相鄰，2,3,4均與5相鄰.7/23/2023

22DiscreteMath.,ChenChen地圖的面著色定義17.11(1)地圖G的面著色——對G的每個國家涂上一種顏色，相鄰國家涂不同顏色(2)G是k-面可著色的——能用k種顏色給G的面著色(3)G的面色數*(G)=k——最少用k種顏色給G的面著色.地圖的面著色轉化成對偶圖的點著色定理17.25

地圖G是k-面可著色的當且僅當它的對偶圖G*是k-點可著色的.證明簡單五色定理定理17.26

任何平面圖都是5-可著色的剩下的大問題：四色猜想是否為真7/23/2023

23DiscreteMath.,ChenChen18.6

邊著色(無環無向圖)定義17.12(1)對G的邊著色——每條邊著一種顏色，相鄰的邊不同色(2)G是k-邊可著色的——能用k種顏色給G的邊著色(3)G的邊色數(G)——最少用k種顏色給G的邊著色定理17.27(Vizing定理

)G為簡單平面圖，則

(G)

(G)

(G)+1.定理17.28

偶圈邊色數為2，奇圈邊色數為3.定理17.29

(Wn)=n1,n4.定理17.30

二部圖的邊色數等于最大度.定理17.31

n為奇數（n1）時，(Kn)=n；

n為偶數時，(Kn)=n1.7/23/2023

24DiscreteMath.,ChenChen第十八章習題課主要內容(點)支配集、點覆蓋集、點獨立集邊覆蓋集、匹配（邊獨立集）二部圖中的完備匹配圖的點著色、邊著色、地圖著色基本要求深刻理解與支配集、點覆蓋集、邊覆蓋集、點獨立集、邊獨立集(匹配)、點著色、邊著色、面著色、色數等概念會求階數n較小或特殊圖的0,0,0,1,1會用二部圖中匹配的理論解簡單問題理解并記住地圖面著色與它的對偶圖點著色之間的關系會用點色數及邊色數解決一些實際問題.7/23/2023

25DiscreteMath.,ChenChen練習1(1)G中有不是最小支配集的極小支配集嗎？求支配數0(2)G中有不是最小點覆蓋集的極小點覆蓋集嗎？求點覆蓋數

0

(3)G中有不是最大點獨立集的極大點獨立集嗎？求0.(4)G中有完美匹配嗎？為什么？求匹配數1(5)求邊覆蓋數11．無向圖G如下所示.7/23/2023

26DiscreteMath.,ChenChen解答(1)共有8個極小支配集：{v1,v2},{v1,v3},{v1,v4},{v1,v5},{v2,v3},{v3,v4},{v3,v5},{v2,v4,v5}.只有最后一個不是最小的，0=2(2)共有2個極小點覆蓋集：{v1,v3},{v2,v4,v5}，前者是最小的，0=2(3)共有2個極大點獨立集：{v1,v3},{v2,v4,v5}，后者是最大的，0=3(4)G不可能有完美匹配，因為它的階數n=5(奇數)，1=2(G的最大匹配為2元集)(5)由定理18.3立刻可知1=37/23/2023

27DiscreteMath.,ChenChen練習22.彼得松圖如下圖所示：在圖上給出一個最大點獨立集和一個最大匹配，從而求出0,1,以及0和1.

7/23/2023

28DiscreteMath.,ChenChen解

由觀察法在上圖(1)中給出一個點獨立集，在(2)中給出了一個最大匹配.從而得出0=4，1=5.由定理18.2推論知0=6，由定理18.3可知1=5.解答7/23/2023

29DiscreteMath.,ChenChen練習3解本題應用定理8.2的推論（0+0=n）與定理8.3中的(3)（1+1=n）較為方便.(1)由于在Kn中，任何兩個頂點均相鄰，因而0=1，故有0=n1（0+0=n）.(2)n為偶數時，Kn中存在完美匹配，所以1=，故當n為奇數時，Kn中不可能有完美匹配，Knv（從Kn中任意刪除頂點v）為Kn1(n1為偶數)，于是Kn1中存在完美匹配，但Kn1中的完美匹配為Kn中的最大匹配，故Kn中的，于是3．求無向完全圖Kn（n3）中的0,1,0,1.

7/23/2023

30DiscreteMath.,ChenChen練習4由二部圖的定義及題中參數的定義，不難看出

0=1=r，1=0=s.4．求完全二部圖Kr,s（1rs）的0,1,0,1.7/23/2023

31DiscreteMath.,ChenChen練習55.

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

32DiscreteMath.,ChenChen(2)由維津（Vizing）定理可知=4或5，但可用4種顏色給邊涂色，如圖所示.練習57/23/2023

33DiscreteMath.,ChenChen圖20

圖19

(3)易知圖的對偶圖為圖(1)所示，容易證明它的點色數為4，所以圖17的面色數*=4，見圖(2)所示.(1)(2)練習57/23/2023

34Discre