數(shù)學(xué)建模之著色

數(shù)學(xué)建模之著色第1頁，共100頁，2023年，2月20日，星期六記為

正常著色就是相鄰的邊用不同的顏色著，所用的最少顏色數(shù)就是邊色數(shù)。目前為止，還沒有一個(gè)好的算法求一般圖的邊色數(shù)。第2頁，共100頁，2023年，2月20日，星期六例設(shè)n個(gè)人中有些要進(jìn)行倆倆會(huì)談，每次會(huì)談需要一個(gè)單元時(shí)間。問最少要用多少單元時(shí)間才能安排完所有會(huì)談？第3頁，共100頁，2023年，2月20日，星期六例設(shè)n是正整數(shù)，且Ai(i=1,2,…,2n+1)是某集合B的子集,且設(shè)∣Ai∣=2n;(b)∣Ai∩Aj∣=1,1≤i<j≤2n+1;(c)B中每個(gè)元素至少屬于兩個(gè)子集Ai.問對(duì)怎樣的n，可以對(duì)B中每個(gè)元素貼一張寫有0或1的標(biāo)簽，使得每個(gè)Ai中恰有n個(gè)貼了0標(biāo)簽的元素?解

{A1,A2,…,A2n+1}為頂點(diǎn)集合，當(dāng)且僅當(dāng)Ai與Aj有共同元素bk時(shí)，在Ai與Aj之間連一條邊，此邊的兩個(gè)端點(diǎn)為Ai與Aj之間的元素bk.由(b)知，得到第4頁，共100頁，2023年，2月20日，星期六得到了一個(gè)完全圖K2n+1,由已知，B中每個(gè)元素都對(duì)應(yīng)K2n+1中的一條邊。約定標(biāo)0的元素著紅色，標(biāo)1的元素著綠色，連接兩紅元素的邊著紅色，連接兩綠元素的邊著綠色。問題轉(zhuǎn)化為完全圖K2n+1，的邊用紅、綠兩種顏色著色，使得每個(gè)頂Ai皆與n條紅邊相關(guān)聯(lián)。K2n+1共有n(2n+1)條邊，當(dāng)n為奇數(shù)時(shí)，無解.對(duì)于n為偶數(shù)時(shí)，用數(shù)學(xué)歸納法證明問題有解。假設(shè)n=2時(shí)，K2n+1=5,每個(gè)Ai有4個(gè)元素，這時(shí)有解。第5頁，共100頁，2023年，2月20日，星期六證明n=2(k+1)時(shí)成立.假設(shè)n=2k時(shí)問題有解。第6頁，共100頁，2023年，2月20日，星期六引理1

設(shè)G不是奇圈的連通圖，則G存在一個(gè)二邊著色，使兩種顏色在每個(gè)度數(shù)不小于2的頂點(diǎn)上表現(xiàn)。若與頂點(diǎn)v關(guān)聯(lián)的某邊染有顏色i，則稱顏色i在頂點(diǎn)v上表現(xiàn)。證明假設(shè)G是非平凡圖。G是Euler圖時(shí)。若G是偶圈，則G的正常2邊著色具有所要求的性質(zhì)。否則，G必有一個(gè)度數(shù)至少為4的點(diǎn)v0.設(shè)v0e1v1e2…env0是G的Euler環(huán)游，并且設(shè)E1={ei∣i是奇數(shù)}，E2={ei∣i是偶數(shù)}第7頁，共100頁，2023年，2月20日，星期六則G的二邊著色(E1，E2)具有所要求的性質(zhì)，因?yàn)镚的每個(gè)頂點(diǎn)都是v0e1v1e2…env0的內(nèi)點(diǎn)。(2)G不是Euler圖時(shí)，則添加一個(gè)新的頂點(diǎn)v0,并將它和G的每個(gè)奇數(shù)度的點(diǎn)連接起來，構(gòu)成一個(gè)新圖G*。顯然G*是Euler圖。設(shè)v0e1v1e2…en*v0是G*的Euler環(huán)游，并且類似地構(gòu)造E1,E2,易證二邊著色(E1∩E，E2∩E)具有所要求的性質(zhì).第8頁，共100頁，2023年，2月20日，星期六定義若C1,C2是對(duì)G的兩種k邊著色，且滿足其中c1(v)是C1著色時(shí)，頂點(diǎn)v關(guān)聯(lián)的邊中的顏色數(shù)，其中c2(v)是C2著色時(shí)，頂點(diǎn)v關(guān)聯(lián)的邊中的顏色數(shù),則稱C2是對(duì)C1的一種改善，不能改善的k邊著色稱為最佳k邊著色。第9頁，共100頁，2023年，2月20日，星期六引理2設(shè)C=(E1,E2,…,Ek)是G的一個(gè)最佳k邊著色。如果有一個(gè)頂v0，又存在兩種顏色i與j，使得i色在v0頂關(guān)聯(lián)的邊中不出現(xiàn)，而j色在v0頂關(guān)聯(lián)的邊中至少出現(xiàn)兩次，則由Ei∪Ej導(dǎo)出的子圖中含v0的連通分支是一個(gè)奇圈。證明設(shè)G[Ei∪Ej]中包含v0的連通分支為H.假設(shè)H不是奇圈，由引理1，則H存在一個(gè)二邊著色，使兩種顏色在每個(gè)度數(shù)不小于2的頂點(diǎn)上表現(xiàn)。以這種方式用顏色i與j重新給H著色，得到一個(gè)G的一個(gè)新的k邊著色用c‘(v)表示頂點(diǎn)v關(guān)聯(lián)的邊中的顏色數(shù),則有第10頁，共100頁，2023年，2月20日，星期六由于兩種顏色i和j都在u上表現(xiàn)，且有于是，這與C的選擇矛盾。由此推出H是奇圈。第11頁，共100頁，2023年，2月20日，星期六定理若G是二分圖，則證明：設(shè)G是具有的圖，且C=(E1,E2,…,E)是G的一個(gè)最佳k邊著色，并設(shè)u是滿足c(u)<d(u)的一個(gè)頂點(diǎn)。顯然u滿足引理2的假設(shè)。所以G包含一個(gè)奇圈，因而不是偶圖，矛盾。第12頁，共100頁，2023年，2月20日，星期六定理(Vizing1964)若G是簡單圖，則G的邊色數(shù)第13頁，共100頁，2023年，2月20日，星期六“課程表問題”：有m位教師x1,x2,…，xm和n個(gè)班級(jí)y1,y2,…，yn,老師xi為班級(jí)yj日授課pij學(xué)時(shí)，試按排一個(gè)授課表使學(xué)校上課的時(shí)間最少。令X={x1,x2,…，xm},Y={y1,y2,…，yn},頂xi與yj之間有pij條邊相連，形成一個(gè)有重邊的二分圖G.每一學(xué)時(shí)，每位老師最多為一個(gè)班級(jí)上課，每個(gè)班至多接受一個(gè)老師的授課，于是問題就是求又，可見，若沒有上課多于p節(jié)的老師，也沒有上課多于p節(jié)的班級(jí)，則可編出至多p節(jié)的課程表；如果只有指定的幾間教室可以用，全校一天最少只排幾節(jié)課？第14頁，共100頁，2023年，2月20日，星期六設(shè)共計(jì)l門課，編成每天p節(jié)課的課表，每節(jié)課平均要開l/p門課，至少用{l/p}間教室。定理設(shè)M與N是圖G的無公共邊的匹配，且∣M∣>∣N∣,則存在無公共邊的匹配M1和N1，使得證明令H=G[M△N]，則H中每個(gè)頂點(diǎn)至多與一條M的邊及一條N的邊相關(guān)聯(lián)，因此

dH(v)=1or2vV(H)第15頁，共100頁，2023年，2月20日，星期六從而H的每個(gè)分支都是一個(gè)圈或一條路，由M及N中的邊交錯(cuò)組成。但∣M∣>∣M∣，H中一定存在一個(gè)分支是一條路P，且其起點(diǎn)和終點(diǎn)都是M飽和的。令

P=v0e1v1,…e2n+1v2n+1,v0

e1

v1,e2

v2…e2n+1

v2n+1取M1=(M-{e1,e3,…,e2n+1})∪

{e2,e4,…,e2n}

N1=(N-

{e2,e4,…,e2n})∪{e1,e3,…,e2n+1}.第16頁，共100頁，2023年，2月20日，星期六定理G是二分圖，G的最大度數(shù)p，則G內(nèi)存在p個(gè)無公共邊的匹配M1,M2,…,Mp,使得

且對(duì)1ip,證明由于G是二分圖，E(G)可以劃分成(G)個(gè)匹配第17頁，共100頁，2023年，2月20日，星期六故對(duì)于p,存在p個(gè)無公共邊的匹配使得對(duì)邊數(shù)之差大于1的匹配反復(fù)應(yīng)用上述引理，可得p個(gè)兩兩無公共邊的匹配M1,M2,…,Mp,滿足定理的條件.第18頁，共100頁，2023年，2月20日，星期六例4名教師，5個(gè)班級(jí)，教學(xué)要求如下：試排出4間教室，3間教室和2間教室的課程表。解以X={x1,x2,x3,x4},Y={y1,y2,y3,y4,y5},做一二分圖G,xi與yj之間連aij條邊相連.于是(G)=4,E(G)=11.第19頁，共100頁，2023年，2月20日，星期六x1x2x3x4y1y2y3y4y5安排4個(gè)節(jié)課，可安排4個(gè)教室4個(gè)節(jié)課的課表。紅線：第1節(jié)蘭線：第2節(jié)綠線：第3節(jié)黑線：第4節(jié)第20頁，共100頁，2023年，2月20日，星期六x1x2x3x4y1y2y3y4y5紅線：第1節(jié)蘭線：第2節(jié)綠線：第3節(jié)黑線：第4節(jié)123456x1y1y1y3y4x2y2y4x3y3y4y2x4y4y5第21頁，共100頁，2023年，2月20日，星期六x1x2x3x4y1y2y3y4y5紅線：第1節(jié)蘭線：第2節(jié)綠線：第3節(jié)黑線：第4節(jié)123456x1y4y1y3y1x2y2y4x3y3y4y2x4y5y43個(gè)教室第22頁，共100頁，2023年，2月20日，星期六x1x2x3x4y1y2y3y4y5可安排2個(gè)教室6個(gè)節(jié)課的課表。第23頁，共100頁，2023年，2月20日，星期六x1x2x3x4y1y2y3y4y5紅線：第1節(jié)蘭線：第2節(jié)綠線：第3節(jié)黑線：第4節(jié)123456x1y4y1y3y1x2y2y4x3y3y4y2x4y5y43個(gè)教室第24頁，共100頁，2023年，2月20日，星期六x1x2x3x4y1y2y3y4y5紅線：第1節(jié)蘭線：第2節(jié)綠線：第3節(jié)黑線：第4節(jié)123456x1y4y1y3y1x2y2y4x3y3y4y2x4y5y42個(gè)教室？？？第25頁，共100頁，2023年，2月20日，星期六2.點(diǎn)著色

著色:如果使用n種顏色把圖G的每個(gè)頂點(diǎn)都分配一種顏色，且使得相鄰頂點(diǎn)異色，則稱此為對(duì)G的頂點(diǎn)正常n著色。G的頂點(diǎn)正常著色中所需顏色數(shù)的最小值稱為G的頂色數(shù)，簡稱色數(shù)。用c(G)

表示，色數(shù)為k的圖稱為k色圖。第26頁，共100頁，2023年，2月20日，星期六第27頁，共100頁，2023年，2月20日，星期六點(diǎn)色數(shù)的簡單性質(zhì)(G)=1G是零圖(Kn)=n(G)=2G是非零圖二部圖(Cn)=2,n偶數(shù)(Wn)=3,n奇數(shù)

3,n奇數(shù)4,n偶數(shù)第28頁，共100頁，2023年，2月20日，星期六(G)上界定理1(G)(G)+1證明vV(G),G(v)={u|(u,v)E(G)},

|G(v)|(G),

給G(v)中頂點(diǎn)著色至多需要(G)種顏色,所以至少還剩一種顏色可用來給v著色.定理2(Brooks):若G連通、非完全圖Kn

(n3)、非奇圈,則(G)(G).說明:n=1G=K1,n=2:連通G=K2

第29頁，共100頁，2023年，2月20日，星期六例

Petersen圖=3.解1:

由Brooks定理,=3.又圖中有奇圈,3.所以=3.解2:

存在如下3-著色,=3.

又圖中有奇圈,3.

所以=3.

第30頁，共100頁，2023年，2月20日，星期六例c(K6)=6c(W6)=4c(W5)=3c(S6)=2c(C6)=2c(C5)=3第31頁，共100頁，2023年，2月20日，星期六應(yīng)用：安全裝箱問題，考試安排問題，信道分配問題等。以每種貨物為一頂點(diǎn)，僅當(dāng)兩種貨物放在一個(gè)箱子里不安全時(shí)，在兩種貨物對(duì)應(yīng)的頂點(diǎn)之間連一邊，構(gòu)成圖G。如果求得(G),對(duì)G用(G)種顏色著色，同色的頂點(diǎn)對(duì)應(yīng)的貨物放在同一箱子中，所需箱子的最小數(shù)目為(G)。第32頁，共100頁，2023年，2月20日，星期六下面給出一種近似算法--最大度數(shù)優(yōu)先的Welsh-Powell算法.

這個(gè)算法給出了一個(gè)較好的著色方法,但不是最有效的方法,即所用的顏色數(shù)不一定是最少的.第33頁，共100頁，2023年，2月20日，星期六最大度數(shù)優(yōu)先的Welsh-Powell算法

設(shè)G=(V,E),V={v1,v2,…,vn},且不妨假設(shè)d(v1)≥d(v2)≥…≥d(vn).c1,c2,…,cn為n種不同的顏色.①令有序集Ci={c1,c2,…,ci},i=1,2,…,n.j=1.轉(zhuǎn)向②.②給vj著Cj的第一個(gè)顏色Cj1.若

j=n時(shí),停;

否則,轉(zhuǎn)向③.③k＞j,若vk和vj相鄰,令Ck=Ck\{Cj1}.j=j+1,轉(zhuǎn)向②.第34頁，共100頁，2023年，2月20日，星期六信道分配問題：在無線傳輸中，發(fā)射臺(tái)所用頻率從小到大編號(hào)，稱為信道。用同一信號(hào)的兩個(gè)臺(tái)的距離不得小于一個(gè)常數(shù)d，問各臺(tái)至少需要幾個(gè)不同的信道？以發(fā)射臺(tái)為頂點(diǎn)，僅當(dāng)發(fā)射臺(tái)間的距離小于d時(shí)，在兩發(fā)射臺(tái)對(duì)應(yīng)的頂點(diǎn)之間連一邊，構(gòu)成圖G。(G)為所求。第35頁，共100頁，2023年，2月20日，星期六應(yīng)用：藥品存儲(chǔ)問題，考試安排問題，信道分配問題等。以每種藥品為一頂點(diǎn)，僅當(dāng)兩種藥品放在一間房子里不安全時(shí)，在兩種藥品對(duì)應(yīng)的頂點(diǎn)之間連一邊，構(gòu)成圖G。如果求得(G),對(duì)G用(G)種顏色著色，同色的頂點(diǎn)對(duì)應(yīng)的藥品放在同一間房子中，所需房間的最小數(shù)目為(G)。第36頁，共100頁，2023年，2月20日，星期六信道分配問題：在無線傳輸中，發(fā)射臺(tái)所用頻率從小到大編號(hào)，稱為信道。用同一信號(hào)的兩個(gè)臺(tái)的距離不得小于一個(gè)常數(shù)d，問各臺(tái)至少需要幾個(gè)不同的信道？以發(fā)射臺(tái)為頂點(diǎn)，僅當(dāng)發(fā)射臺(tái)間的距離小于d時(shí)，在兩發(fā)射臺(tái)對(duì)應(yīng)的頂點(diǎn)之間連一邊，構(gòu)成圖G。(G)

為所求。第37頁，共100頁，2023年，2月20日，星期六特殊圖的色數(shù)①零圖：(G)=1②完全圖Kn：(G)=n③G是一條回路：(G)=2若|V|是偶數(shù)

(G)=3若|V|是奇數(shù)④G是一棵非平凡樹：(G)=2⑤

(G)=2的充要條件是:(a)|E|1；(b)G中不存在邊數(shù)為奇數(shù)的回路。（此時(shí)G為二部圖）

⑥若G1、G2為G的兩個(gè)連通分支，則

(G)=max{(G1),

(G2)}第38頁，共100頁，2023年，2月20日，星期六定理1

對(duì)G=(V,E)，=max{deg(vi)|viV}，則

(G)+1。定理2(Brooks)設(shè)G=(V,E)是簡單連通圖，但不是完全圖，不是奇數(shù)長度圈，=max{deg(vi)|viV}3，則

(G),即G是-可著色的。定理給出了色數(shù)的一個(gè)上限，但很不精確。Brooks定理也說明只存在兩類滿足(G)=+1的圖。例二部圖可2著色，但是可以相當(dāng)大。第39頁，共100頁，2023年，2月20日，星期六[Hajós猜想]

若G是n色圖，則G包含Kn的一個(gè)同胚圖。n=1,2顯然，n=3,4已證，其他未決。[四色猜想]

任何平面圖都是4-可著色的。由于存在著不可3-著色的平面圖K4，4色問題若可證明，將是平面圖色數(shù)問題的最佳結(jié)果。[五色定理]

任何簡單平面圖都是5-可著色的。第40頁，共100頁，2023年，2月20日，星期六色數(shù)

G=(V,E)為簡單圖，vi,vj

為其中不相鄰頂點(diǎn)。為在G中添加邊(vi,vj)得到的圖，為在G中合并vi,vj

，其他頂點(diǎn)與其關(guān)系不變，并合并多重邊（稱為收縮vi,vj

）得到的圖。則有：

c(G)=min(c(),c())例ijijijG第41頁，共100頁，2023年，2月20日，星期六例

如圖，求c(G)。c(K5)=5c(K4)=4c(K4)=4c(K3)=3第42頁，共100頁，2023年，2月20日，星期六定義:

對(duì)給定的圖G=(V,E)，PG(k)表示以k種顏給G進(jìn)行正常著色的方案數(shù)目。兩種方案相同：同一個(gè)結(jié)點(diǎn)著同一種顏色。可以用結(jié)點(diǎn)集到顏色集的函數(shù)表述。當(dāng)k<

c(G)時(shí),不可能進(jìn)行正常著色,此時(shí)PG(k)=0。當(dāng)kc(G)時(shí)，PG(k)>0。4色猜想：對(duì)平面圖G,PG(4)>0（存在4-著色方案）.例如，PK3(3)=6色多項(xiàng)式第43頁，共100頁，2023年，2月20日，星期六PK3(3)=6abcabcabcabcabcabc第44頁，共100頁，2023年，2月20日，星期六若干特殊圖的PG(k)1）零圖：G=(V,E)，n=|V|，|E|=0，PG(k)=kn2）樹：根節(jié)點(diǎn)在k種顏色中任取，非根節(jié)點(diǎn)選取與其父親節(jié)點(diǎn)不同的顏色。PG(k)=k(k-1)n-1圖G的色多項(xiàng)式為k(k-1)n-1，當(dāng)且僅當(dāng)G是具有n個(gè)頂點(diǎn)的樹。3）完全圖：PG(k)=k(k-1)(k-2)…(k-n+1)第45頁，共100頁，2023年，2月20日，星期六定理3

設(shè)簡單圖G，e=vivj

為G的一條邊，記G-e為從G中去掉e后得到的圖；G*e為從收縮邊e后得到的圖，并記PG*e(k)和PG-e(k)分別為G*e和G-e的k染色方案數(shù)，則

PG(k)=PG-e(k)-PG*e(k)。(1)vivj同色；(2)vivj異色第46頁，共100頁，2023年，2月20日，星期六推論1

對(duì)任何圖G=(V,E)，n=|V|，e=|E|，PG(k)都是k的整系數(shù)n次多項(xiàng)式，且：①首項(xiàng)為kn；②次項(xiàng)為-ekn-1；③常數(shù)項(xiàng)為0；④各項(xiàng)系數(shù)的符號(hào)正-負(fù)交替。證明對(duì)圖G的邊數(shù)e進(jìn)行歸納法證明.約定重邊變成單邊，不影響頂點(diǎn)的正常著色。e=0時(shí)，有PG(k)=kn,成立。假設(shè)en-1時(shí)，成立。考慮e=n的情形.則G-e的邊數(shù)為n-1,G*e等于或小于n-1，由歸納法假設(shè)，PG-e(k)=kn-(e-1)kn-1+an-2kn-2-an-3kn-3+…+(-1)n-1a1k第47頁，共100頁，2023年，2月20日，星期六PG*e(k)=kn-1-e′kn-2+bn-3kn-3-bn-4kn-4+…+(-1)n-2b1k其中e′是簡單圖G*e的邊數(shù)，ai,bi0.由公式PG(k)=PG-e(k)-PG*e(k)PG(k)=kn-(e-1)kn-1+an-2kn-2-an-3kn-3+…+(-1)n-1a1k-[kn-1-e′kn-2+bn-3kn-3-bn-4kn-4+…+(-1)n-2b1k]=kn-ekn-1+(an-2+e′)kn-2-(an-3+bn-3)kn-3+…+(-1)n-1(a1+b1)k推論1證明了函數(shù)PG(k)具有多項(xiàng)式形式。色數(shù)多項(xiàng)式:上述函數(shù)PG(k)稱為圖G的色數(shù)多項(xiàng)式。第48頁，共100頁，2023年，2月20日，星期六減邊法:求給定圖G的色數(shù)多項(xiàng)式原理：定理3，PG(k)=PG-e(k)-PG*e(k)①在圖G中任取一邊e；②在圖G中去掉e，得新圖G-e

在圖G中收縮e的兩端點(diǎn)，得新圖G*e，由上述公式有

PG(k)=PG-e(k)-PG*e(k)③繼續(xù)分解G-e和G*e，直到最后全部為零圖。④利用n階零圖的P(k)=kn構(gòu)造圖G的色數(shù)多項(xiàng)式。第49頁，共100頁，2023年，2月20日，星期六例如圖，求其色數(shù)多項(xiàng)式。減邊法比較適合于求稀疏圖的色數(shù)多項(xiàng)式。P（,k）=P（,k）-P（,k）=[P(,k）-P（,k）]-[P(,k）-P（,k）]=(k3-k2)-(k2-k)=k3-2k2+k第50頁，共100頁，2023年，2月20日，星期六加邊法:

求給定圖G的色數(shù)多項(xiàng)式原理：定理3，PG(k)=PG-e(k)-PG*e(k)①在圖G中任取兩個(gè)不相鄰頂點(diǎn)u,v；②在圖G中加上(u,v)，得新圖G+e，在圖G中收縮(u,v)，得新圖G*e，由上述討論有

PG(k)=PG+e(k)+PG*e(k)③繼續(xù)分解G+e和G*e，直到最后全部為完全圖。④利用n階完全圖的P(k)=k(k-1)(k-2)…(k-n+1)

構(gòu)造圖G的色數(shù)多項(xiàng)式。加邊法比較適合于求稠密圖的色數(shù)多項(xiàng)式。第51頁，共100頁，2023年，2月20日，星期六G的色數(shù)多項(xiàng)式是k(k-1)n-1

G是n個(gè)頂點(diǎn)的樹.頂點(diǎn)是n的樹T的色數(shù)多項(xiàng)式是k(k-1)n-1.對(duì)頂點(diǎn)數(shù)n進(jìn)行歸納證明。當(dāng)n=1,2時(shí)，成立。假設(shè)nn-1時(shí)，成立，考慮n=n的情形。此時(shí)，考慮T的一個(gè)葉點(diǎn)v0,記T1=T-{v0},則由歸納假設(shè)，

PT1(k)=k(k-1)n-2對(duì)于T1的每一種正常k著色，v0在T中著色時(shí)有k-1種選擇，因此PT(k)=(k-1)k(k-1)n-2=k(k-1)n-1.第52頁，共100頁，2023年，2月20日，星期六能否判斷一個(gè)多項(xiàng)式為某一個(gè)圖的色數(shù)多項(xiàng)式？說明k4-3k3+k2不是色數(shù)多項(xiàng)式。該多項(xiàng)式滿足推論的條件，設(shè)它是圖G的色多項(xiàng)式。則V(G)=4,E(G)=3.

若G是連通的，G是樹，于是

PG(k)=k(k-1)3=k4-3k3+k2-k.若G不連通，則G只能如圖所示，于是

PG(k)=kk(k-1)(k-2)=k4-3k3+2k2.第53頁，共100頁，2023年，2月20日，星期六例如圖，求其色數(shù)多項(xiàng)式。32=k(k-1)(k-2)(k-3)(k-4)+3k(k-1)(k-2)(k-3)+2k(k-1)(k-2)=k(k-1)(k-2)(k2-4k+5)第54頁，共100頁，2023年，2月20日，星期六4獨(dú)立集、支配集和覆蓋集同色頂點(diǎn)構(gòu)成的頂點(diǎn)集：頂點(diǎn)互不相鄰

紅色頂點(diǎn)集構(gòu)成一個(gè)獨(dú)立集。第55頁，共100頁，2023年，2月20日，星期六獨(dú)立集：

圖G=(V,E)，IV，若I中任意兩個(gè)頂點(diǎn)都不相鄰，則稱I為G的一個(gè)獨(dú)立集.例獨(dú)立集：

{b,d},{b,f},{a,c},{b,d,f},…acbdef4.1獨(dú)立集第56頁，共100頁，2023年，2月20日，星期六

極大獨(dú)立集：如果I為G的一個(gè)獨(dú)立集，且uV-I,I{u}不是G的獨(dú)立集，則稱I為G的一個(gè)極大獨(dú)立集。設(shè)G的所有獨(dú)立集為I1、I2、…、Ik，記稱為G的獨(dú)立數(shù)。最大獨(dú)立集：

G的一個(gè)獨(dú)立集Ii

稱為G的一個(gè)最大獨(dú)立集若|Ii|=

。第57頁，共100頁，2023年，2月20日，星期六例求最大獨(dú)立集問題是NP完全的。獨(dú)立集：{b,d},{b,f},{a,c},{b,d,f},…極大獨(dú)立集：{a,c},{b,e},{b,d,f}最大獨(dú)立集：{b,d,f}

=3acbdef第58頁，共100頁，2023年，2月20日，星期六定義設(shè)G=(V,E)是簡單無向圖，同時(shí)將G的鄰接矩陣的第i行與第j行，第i列與第j列互換，稱為一次平移變換。平移變換不影響圖的結(jié)點(diǎn)之間的連接關(guān)系，僅僅改變了i,j編號(hào)。也就是說，鄰接矩陣的平移變換對(duì)應(yīng)于圖中結(jié)點(diǎn)的一個(gè)重新編號(hào)。定理1

設(shè)G=(V,E)是具有n個(gè)結(jié)點(diǎn)的簡單無向圖，A是其鄰接矩陣，且A具有如下形式：

(1)極大獨(dú)立集的求法：第59頁，共100頁，2023年，2月20日，星期六其中令若，則其已確定一極大獨(dú)立集其中vt(1ti)與下三角矩陣的第t行對(duì)應(yīng)。第60頁，共100頁，2023年，2月20日，星期六證明則必有一個(gè)元素為1，不妨設(shè)由矩陣A可知，akj=0,1k,ji，即結(jié)點(diǎn)考慮A21,因互不相鄰。說明vj與vk相鄰。即中任何一個(gè)結(jié)點(diǎn)都與I={v1,v2,…,vi}相鄰。I={v1,v2,…,vi}是極大一獨(dú)立集.第61頁，共100頁，2023年，2月20日，星期六形如(1)，滿足定理?xiàng)l件的鄰接矩陣稱為標(biāo)準(zhǔn)型.定理2

A是簡單無向圖G=(V,E)的鄰接矩陣，則總可以經(jīng)過若干次平移變換，將A化為標(biāo)準(zhǔn)型，從而得到G的一個(gè)極大獨(dú)立集.acbdef第62頁，共100頁，2023年，2月20日，星期六acbdef第63頁，共100頁，2023年，2月20日，星期六acbdef第64頁，共100頁，2023年，2月20日，星期六G的所有極大獨(dú)立集的求法：借助布爾變量的運(yùn)算求G的所有極大獨(dú)立集。已知簡單無向圖G=(V,E),V={v1,v2,…,vn},約定：

G的每個(gè)點(diǎn)vi作為一個(gè)布爾變量；“∧”,“∨”表示“與”運(yùn)算和“或”運(yùn)算，即布爾積與布爾和。布爾運(yùn)算性質(zhì)與集合的運(yùn)算性質(zhì)類似。圖G的過點(diǎn)vi,vj的邊對(duì)應(yīng)一布爾積vi∧

vj.做布爾表達(dá)式：第65頁，共100頁，2023年，2月20日，星期六中每一項(xiàng)vi∧

vj對(duì)應(yīng)G的一條邊，表示對(duì)所有邊求布爾和。利用德摩根定律有，設(shè)與都是v1,v2,…,vn的表達(dá)式。因獨(dú)立集不包含任何一邊的兩個(gè)端點(diǎn)，在獨(dú)立集上取值為0；反之若=0，則對(duì)應(yīng)的點(diǎn)集為獨(dú)立集。在獨(dú)立集上取值為1；反之若點(diǎn)集為獨(dú)立集。則對(duì)應(yīng)的考慮所有的點(diǎn)集合，即為第66頁，共100頁，2023年，2月20日，星期六所有的極大獨(dú)立集。v6v5v4v1v2v3第67頁，共100頁，2023年，2月20日，星期六v6v5v4v1v2v3極大獨(dú)立集第68頁，共100頁，2023年，2月20日，星期六利用極大獨(dú)立集可以得到一個(gè)正常點(diǎn)著色的算法：

定義

若將圖G=(V,E)的頂點(diǎn)集合V劃分成k個(gè)子集合：V1,V2,…,Vk，即且，Vi是的極大獨(dú)立集，i=1,2,…k.其中V0=,將Vi中的頂點(diǎn)染上i色，則稱這種上色是對(duì)圖G的一種k點(diǎn)規(guī)范著色。規(guī)范著色是正常著色。下面證明圖G可以k點(diǎn)正常點(diǎn)著色則存在k點(diǎn)規(guī)范著色。第69頁，共100頁，2023年，2月20日，星期六證明設(shè)G有正常著色C=(V1,V2,…,Vk),即且C是k點(diǎn)規(guī)范著色.若V1是極大獨(dú)立，則將V1中的點(diǎn)上1色。不然，V1是G的一個(gè)獨(dú)立集，從V-V1中調(diào)一些點(diǎn)放入V1中，總可以將V1擴(kuò)成G的極大獨(dú)立集,這是定理如果圖G是可以k點(diǎn)正常點(diǎn)著色的，則G存在k點(diǎn)規(guī)范著色。,Vi中的頂點(diǎn)染上i色,調(diào)整Vi，分別變?yōu)榈?0頁，共100頁，2023年，2月20日，星期六對(duì)圖G-V1重復(fù)上面的過程，最后便得到規(guī)范k點(diǎn)著色。v1v3v2v4v5V1={v5}是G的極大獨(dú)立集.V2={v2,v4}是G-V1的極大獨(dú)立集.V3={v1,v3}是G-V1-V2的極大獨(dú)立集.V=V1∪V2∪V3,得到一規(guī)范著色。用第一種顏色為圖上色時(shí)，盡可能多的將一些無色頂上色，直至不能再多為止，一直保持鄰頂不同色；接著…第71頁，共100頁，2023年，2月20日，星期六點(diǎn)覆蓋:

圖G=(V,E)，KV，若G的任何一條邊都與K中頂點(diǎn)關(guān)聯(lián)，則稱K為G的一個(gè)點(diǎn)覆蓋（集）。例acbdef點(diǎn)覆蓋：

{a,b,c,e},{a,b,c,d,e},{a,c,e},…極小點(diǎn)覆蓋、點(diǎn)覆蓋數(shù)、最小點(diǎn)覆蓋。4.2點(diǎn)覆蓋第72頁，共100頁，2023年，2月20日，星期六極小點(diǎn)覆蓋：

K是G的一個(gè)極小點(diǎn)覆蓋K為G的一個(gè)點(diǎn)覆蓋且K1K，K1不是G的點(diǎn)覆蓋。點(diǎn)覆蓋數(shù)：設(shè)G的所有點(diǎn)覆蓋為C1、C2、…、Cl，記稱為G的點(diǎn)覆蓋數(shù)。最小點(diǎn)覆蓋：G的一個(gè)點(diǎn)覆蓋Ci

稱為G的一個(gè)最小點(diǎn)覆蓋若|Ci|=

。第73頁，共100頁，2023年，2月20日，星期六例點(diǎn)覆蓋：{a,b,c,d,e},{a,b,c,e},{a,c,e},…極小點(diǎn)覆蓋：{a,c,e},{b,d,e,f},{a,c,d,f}最小點(diǎn)覆蓋：{a,c,e}

=3acbdef第74頁，共100頁，2023年，2月20日，星期六4.3獨(dú)立集與覆蓋集的關(guān)系獨(dú)立集與覆蓋集在一個(gè)圖中具有互補(bǔ)性。(1)I為G=(V,E)的獨(dú)立集V-I是G的覆蓋集。(2)I為G=(V,E)的極大獨(dú)立集V-I是G的極小覆蓋集。(3)+=V.若I是G的獨(dú)立集，即I中任何兩個(gè)頂點(diǎn)在G中都不相鄰，因此E中每條邊至少有一個(gè)端點(diǎn)在V-I中，即V-I是G的覆蓋集；反之，若V-I是G的一個(gè)覆蓋，即每條邊至少在V-I中，則I中沒有相鄰的頂點(diǎn)，I是G的獨(dú)立集。第75頁，共100頁，2023年，2月20日，星期六極小覆蓋一種求法求覆蓋集：vV，或者v蓋住與v關(guān)聯(lián)的所有邊，或者是其鄰點(diǎn)蓋住與v關(guān)聯(lián)的邊，可以寫成第76頁，共100頁，2023年，2月20日，星期六極小覆蓋集可由下面的式子給出：展開式中每一項(xiàng)是一個(gè)極小覆蓋集。acbdef極小覆蓋集：{a,c,e},{b,d,e,f},{a,c,d,f}。求極大獨(dú)立集或極小覆蓋集是NP難的。第77頁，共100頁，2023年，2月20日，星期六acbdef極小覆蓋集還可以利用前面求極大獨(dú)立集的方法求；同樣求極大獨(dú)立集也可以用上面的方法求得。極小覆蓋集：{a,c,e},{b,d,e,f},{a,c,d,f}。極大獨(dú)立集：{b,d,f},{a,c},{b,e}。第78頁，共100頁，2023年，2月20日，星期六支配集：

圖G=(V,E)，KV，若G的任何頂點(diǎn)或?qū)儆贙，或至少與K中一點(diǎn)鄰接，則稱K為G的一個(gè)支配集。例支配集：

{a,c},{b,e},{b,d,f},{a,b,c},{a,b,c,d,e,f},…acbdef4.4支配集第79頁，共100頁，2023年，2月20日，星期六極小支配集：K為G的一個(gè)極小支配集K為G的一個(gè)支配集且K1K，K1不是G的支配集。支配數(shù)：設(shè)G的所有支配集為A1、A2、…、Ak，記稱為G的支配數(shù)。最小支配集：

G的一個(gè)支配集Ai

稱為G的一個(gè)最小支配集若|Ai|=

。acbdef如圖,極小支配集：{a,c},{b,e},{c,f},{b,d,f}。最小支配集：{a,c},{b,e},{c,f}。

=2第80頁，共100頁，2023年，2月20日，星期六上式展開，每一項(xiàng)是一個(gè)極小支配集。baedfc第81頁，共100頁，2023年，2月20日，星期六高斯提出5皇后和8皇后問題最少幾個(gè)“后”放在哪些方格中，才能吃掉對(duì)方任何一個(gè)格子上的子兒？最多幾個(gè)“后”放在哪些方格中，使得任意“后”吃不掉其他的“后”？第82頁，共100頁，2023年，2月20日，星期六4.5獨(dú)立集、支配集和點(diǎn)覆蓋的關(guān)系定理1設(shè)G=(V,E)無孤立點(diǎn)，則：①G的一個(gè)極大獨(dú)立集必是G的一個(gè)極小支配集；②

；③若S為G的一個(gè)獨(dú)立集，則V-S為G的一個(gè)支配集。第83頁，共100頁，2023年，2月20日，星期六定理2設(shè)圖G=(V,E)無孤立點(diǎn)，CV，則C為G的一個(gè)點(diǎn)覆蓋

V-C為G的一個(gè)獨(dú)立集。推論1G如上所述，CV，則C為G的一個(gè)極小覆蓋V-C是G的一個(gè)極大獨(dú)立集。推論2G如上所述，n=|V|，則

+=n。第84頁，共100頁，2023年，2月20日，星期六支配集與獨(dú)立集的應(yīng)用（1）中心臺(tái)站的選址

在v1,v2,...,vn這n個(gè)城鎮(zhèn)之間建立一個(gè)通信網(wǎng)絡(luò)。現(xiàn)從這幾個(gè)城鎮(zhèn)中選定幾座城鎮(zhèn)，在那里建立中心臺(tái)站，要求它們與其它各城鎮(zhèn)相鄰，同時(shí)，為減少造價(jià)，要使中心臺(tái)站數(shù)目最少，有時(shí)還會(huì)提其它要求，例如在造價(jià)最低的條件下，需要造兩套（或更多套）的中心臺(tái)站，以備一套出故障時(shí)，可以及時(shí)啟用另一套臺(tái)站。第85頁，共100頁，2023年，2月20日，星期六數(shù)學(xué)模型：以城鎮(zhèn)為頂點(diǎn)，僅當(dāng)兩城之間有直通通信線路時(shí)，相應(yīng)的兩頂點(diǎn)連一邊形成一個(gè)圖，此圖的最小支配集即為所求。

若建兩套，則從所有極小支配集D1,D2,...,Dd中選取Dm與Dn，使得

Dm∩Dn=，

|Dm∪Dn|=min{|Di|+|Dj||1i,jd,Di∩Dj=

｝。baedfc若選一個(gè)中心臺(tái)站，則選phx1tt1;若選兩個(gè)，則選{a,e}或{a,f}.極小支配集：第86頁，共100頁，2023年，2月20日，星期六（2）獨(dú)立集在信息論中的應(yīng)用

設(shè)信息傳送的基本信號(hào)集為S={s1,s2,...sn}。可以把信號(hào)si設(shè)想成漢字或拉丁字母。統(tǒng)計(jì)規(guī)律表明哪些信號(hào)與哪些信號(hào)易于發(fā)生錯(cuò)亂是已知的。例如，輸入si，i=1,2,...,5,輸出應(yīng)該是si*,i=1,2,...,5,但由于干擾發(fā)生了錯(cuò)亂，s1可能和s2錯(cuò)亂，s1還可能和s5錯(cuò)亂等，例如已知錯(cuò)亂可能性如下圖所示。

構(gòu)造一個(gè)無向圖G,以S為頂點(diǎn)集合，僅當(dāng)si與sj易于混亂時(shí)，在點(diǎn)si與sj之間連一邊。求G的最大獨(dú)立集即可作為無誤基本信號(hào)集S1。第87頁，共100頁，2023年，2月20日，星期六s1s2s3s4s5s1*s2*s3*s4*s5*s5s1s2s3s4混亂的可能性圖G最大獨(dú)立集：每一個(gè)都可作為無誤基本信號(hào)集S1。第88頁，共100頁，2023年，2月20日，星期六作一圖G，使得如果用兩信號(hào)組成一個(gè)詞向外傳輸信息，也有一個(gè)如何排除干擾的問題，為此，考慮一種圖的積的概念。已知兩圖G1，G2，其頂點(diǎn)集合為：第89頁，共100頁，2023年，2月20日，星期六在G中頂點(diǎn)的鄰集為：則稱G為G1與G2之積，記成

G＝G1×G2＝G2×G1。例如，取，則如下圖：第90頁，共100頁，2023年，2月20日，星期六K3K1K6在上面的例子中，若用{s1,s2,...,s5}中的兩個(gè)信號(hào)組成詞向外輸出，最多能用哪幾個(gè)詞不致于發(fā)生錯(cuò)亂呢？這只需考慮圈C=s1s2s3s4s5s1的平方C×C＝C2中的最大獨(dú)立集中的各頂對(duì)應(yīng)的詞。相似地可用Gn=G×G×...×G(n個(gè))中的最大獨(dú)立集來確定由n個(gè)信號(hào)組成的詞進(jìn)行信息傳送而不致發(fā)生錯(cuò)亂。

第91頁，共100頁，2023年，2月20日，星期六

任給一群人，其中有k個(gè)人彼此認(rèn)識(shí)，有l(wèi)個(gè)人彼此不認(rèn)識(shí)，這種人群至少幾人？這個(gè)答案記成r(k,l)，稱為Ramsey(拉姆薩)數(shù)。Ramsey證明了r(3,3)=6.4.6團(tuán)與Ramsey定理人作為頂點(diǎn)，當(dāng)且僅當(dāng)兩個(gè)人認(rèn)識(shí)時(shí)連紅邊，不認(rèn)識(shí)連綠邊。r(3,3)>5r(3,3)≤6第92頁，共100頁，2023年，2月20日，星期六

團(tuán)：設(shè)圖G=(V,E)，