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

數(shù)學(xué)建模之著色第1頁，課件共100頁，創(chuàng)作于2023年2月記為

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

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

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

dH(v)=1or2vV(H)第15頁，課件共100頁，創(chuàng)作于2023年2月從而H的每個分支都是一個圈或一條路，由M及N中的邊交錯組成。但∣M∣>∣M∣，H中一定存在一個分支是一條路P，且其起點和終點都是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頁，創(chuàng)作于2023年2月定理G是二分圖，G的最大度數(shù)p，則G內(nèi)存在p個無公共邊的匹配M1,M2,…,Mp,使得

且對1ip,證明由于G是二分圖，E(G)可以劃分成(G)個匹配第17頁，課件共100頁，創(chuàng)作于2023年2月故對于p,存在p個無公共邊的匹配使得對邊數(shù)之差大于1的匹配反復(fù)應(yīng)用上述引理，可得p個兩兩無公共邊的匹配M1,M2,…,Mp,滿足定理的條件.第18頁，課件共100頁，創(chuàng)作于2023年2月例4名教師，5個班級，教學(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頁，創(chuàng)作于2023年2月x1x2x3x4y1y2y3y4y5安排4個節(jié)課，可安排4個教室4個節(jié)課的課表。紅線：第1節(jié)蘭線：第2節(jié)綠線：第3節(jié)黑線：第4節(jié)第20頁，課件共100頁，創(chuàng)作于2023年2月x1x2x3x4y1y2y3y4y5紅線：第1節(jié)蘭線：第2節(jié)綠線：第3節(jié)黑線：第4節(jié)123456x1y1y1y3y4x2y2y4x3y3y4y2x4y4y5第21頁，課件共100頁，創(chuàng)作于2023年2月x1x2x3x4y1y2y3y4y5紅線：第1節(jié)蘭線：第2節(jié)綠線：第3節(jié)黑線：第4節(jié)123456x1y4y1y3y1x2y2y4x3y3y4y2x4y5y43個教室第22頁，課件共100頁，創(chuàng)作于2023年2月x1x2x3x4y1y2y3y4y5可安排2個教室6個節(jié)課的課表。第23頁，課件共100頁，創(chuàng)作于2023年2月x1x2x3x4y1y2y3y4y5紅線：第1節(jié)蘭線：第2節(jié)綠線：第3節(jié)黑線：第4節(jié)123456x1y4y1y3y1x2y2y4x3y3y4y2x4y5y43個教室第24頁，課件共100頁，創(chuàng)作于2023年2月x1x2x3x4y1y2y3y4y5紅線：第1節(jié)蘭線：第2節(jié)綠線：第3節(jié)黑線：第4節(jié)123456x1y4y1y3y1x2y2y4x3y3y4y2x4y5y42個教室？？？第25頁，課件共100頁，創(chuàng)作于2023年2月2.點著色

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

表示，色數(shù)為k的圖稱為k色圖。第26頁，課件共100頁，創(chuàng)作于2023年2月第27頁，課件共100頁，創(chuàng)作于2023年2月點色數(shù)的簡單性質(zhì)(G)=1G是零圖(Kn)=n(G)=2G是非零圖二部圖(Cn)=2,n偶數(shù)(Wn)=3,n奇數(shù)

3,n奇數(shù)4,n偶數(shù)第28頁，課件共100頁，創(chuàng)作于2023年2月(G)上界定理1(G)(G)+1證明vV(G),G(v)={u|(u,v)E(G)},

|G(v)|(G),

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

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

第29頁，課件共100頁，創(chuàng)作于2023年2月例

Petersen圖=3.解1:

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

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

又圖中有奇圈,3.

所以=3.

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

這個算法給出了一個較好的著色方法,但不是最有效的方法,即所用的顏色數(shù)不一定是最少的.第33頁，課件共100頁，創(chuàng)作于2023年2月最大度數(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的第一個顏色Cj1.若

j=n時,停;

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

為所求。第37頁，課件共100頁，創(chuàng)作于2023年2月特殊圖的色數(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ù)的回路。（此時G為二部圖）

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

(G)=max{(G1),

(G2)}第38頁，課件共100頁，創(chuàng)作于2023年2月定理1

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

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

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

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

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

任何簡單平面圖都是5-可著色的。第40頁，課件共100頁，創(chuàng)作于2023年2月色數(shù)

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

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

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

）得到的圖。則有：

c(G)=min(c(),c())例ijijijG第41頁，課件共100頁，創(chuàng)作于2023年2月例

如圖，求c(G)。c(K5)=5c(K4)=4c(K4)=4c(K3)=3第42頁，課件共100頁，創(chuàng)作于2023年2月定義:

對給定的圖G=(V,E)，PG(k)表示以k種顏給G進行正常著色的方案數(shù)目。兩種方案相同：同一個結(jié)點著同一種顏色?？梢杂媒Y(jié)點集到顏色集的函數(shù)表述。當k<

c(G)時,不可能進行正常著色,此時PG(k)=0。當kc(G)時，PG(k)>0。4色猜想：對平面圖G,PG(4)>0（存在4-著色方案）.例如，PK3(3)=6色多項式第43頁，課件共100頁，創(chuàng)作于2023年2月PK3(3)=6abcabcabcabcabcabc第44頁，課件共100頁，創(chuàng)作于2023年2月若干特殊圖的PG(k)1）零圖：G=(V,E)，n=|V|，|E|=0，PG(k)=kn2）樹：根節(jié)點在k種顏色中任取，非根節(jié)點選取與其父親節(jié)點不同的顏色。PG(k)=k(k-1)n-1圖G的色多項式為k(k-1)n-1，當且僅當G是具有n個頂點的樹。3）完全圖：PG(k)=k(k-1)(k-2)…(k-n+1)第45頁，課件共100頁，創(chuàng)作于2023年2月定理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頁，創(chuàng)作于2023年2月推論1

對任何圖G=(V,E)，n=|V|，e=|E|，PG(k)都是k的整系數(shù)n次多項式，且：①首項為kn；②次項為-ekn-1；③常數(shù)項為0；④各項系數(shù)的符號正-負交替。證明對圖G的邊數(shù)e進行歸納法證明.約定重邊變成單邊，不影響頂點的正常著色。e=0時，有PG(k)=kn,成立。假設(shè)en-1時，成立?？紤]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頁，創(chuàng)作于2023年2月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)具有多項式形式。色數(shù)多項式:上述函數(shù)PG(k)稱為圖G的色數(shù)多項式。第48頁，課件共100頁，創(chuàng)作于2023年2月減邊法:求給定圖G的色數(shù)多項式原理：定理3，PG(k)=PG-e(k)-PG*e(k)①在圖G中任取一邊e；②在圖G中去掉e，得新圖G-e

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

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

求給定圖G的色數(shù)多項式原理：定理3，PG(k)=PG-e(k)-PG*e(k)①在圖G中任取兩個不相鄰頂點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ù)多項式。加邊法比較適合于求稠密圖的色數(shù)多項式。第51頁，課件共100頁，創(chuàng)作于2023年2月G的色數(shù)多項式是k(k-1)n-1

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

PT1(k)=k(k-1)n-2對于T1的每一種正常k著色，v0在T中著色時有k-1種選擇，因此PT(k)=(k-1)k(k-1)n-2=k(k-1)n-1.第52頁，課件共100頁，創(chuàng)作于2023年2月能否判斷一個多項式為某一個圖的色數(shù)多項式？說明k4-3k3+k2不是色數(shù)多項式。該多項式滿足推論的條件，設(shè)它是圖G的色多項式。則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頁，創(chuàng)作于2023年2月例如圖，求其色數(shù)多項式。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頁，創(chuàng)作于2023年2月4獨立集、支配集和覆蓋集同色頂點構(gòu)成的頂點集：頂點互不相鄰

紅色頂點集構(gòu)成一個獨立集。第55頁，課件共100頁，創(chuàng)作于2023年2月獨立集：

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

{b,d},{b,f},{a,c},{b,d,f},…acbdef4.1獨立集第56頁，課件共100頁，創(chuàng)作于2023年2月

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

G的一個獨立集Ii

稱為G的一個最大獨立集若|Ii|=

。第57頁，課件共100頁，創(chuàng)作于2023年2月例求最大獨立集問題是NP完全的。獨立集：{b,d},{b,f},{a,c},{b,d,f},…極大獨立集：{a,c},{b,e},{b,d,f}最大獨立集：{b,d,f}

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

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

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

A是簡單無向圖G=(V,E)的鄰接矩陣，則總可以經(jīng)過若干次平移變換，將A化為標準型，從而得到G的一個極大獨立集.acbdef第62頁，課件共100頁，創(chuàng)作于2023年2月acbdef第63頁，課件共100頁，創(chuàng)作于2023年2月acbdef第64頁，課件共100頁，創(chuàng)作于2023年2月G的所有極大獨立集的求法：借助布爾變量的運算求G的所有極大獨立集。已知簡單無向圖G=(V,E),V={v1,v2,…,vn},約定：

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

vj.做布爾表達式：第65頁，課件共100頁，創(chuàng)作于2023年2月中每一項vi∧

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

定義

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

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

{a,b,c,e},{a,b,c,d,e},{a,c,e},…極小點覆蓋、點覆蓋數(shù)、最小點覆蓋。4.2點覆蓋第72頁，課件共100頁，創(chuàng)作于2023年2月極小點覆蓋：

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

稱為G的一個最小點覆蓋若|Ci|=

。第73頁，課件共100頁，創(chuàng)作于2023年2月例點覆蓋：{a,b,c,d,e},{a,b,c,e},{a,c,e},…極小點覆蓋：{a,c,e},{b,d,e,f},{a,c,d,f}最小點覆蓋：{a,c,e}

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

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

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

G的一個支配集Ai

稱為G的一個最小支配集若|Ai|=

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

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

；③若S為G的一個獨立集，則V-S為G的一個支配集。第83頁，課件共100頁，創(chuàng)作于2023年2月定理2設(shè)圖G=(V,E)無孤立點，CV，則C為G的一個點覆蓋

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

+=n。第84頁，課件共100頁，創(chuàng)作于2023年2月支配集與獨立集的應(yīng)用（1）中心臺站的選址

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

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

Dm∩Dn=，

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

｝。baedfc若選一個中心臺站，則選fhmtpoj;若選兩個，則選{a,e}或{a,f}.極小支配集：第86頁，課件共100頁，創(chuàng)作于2023年2月（2）獨立集在信息論中的應(yīng)用

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

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

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

第91頁，課件共100頁，創(chuàng)作于2023年2月

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

團：設(shè)圖G=(V,E)，WV