圖論平面圖與圖的著色

,單擊此處編輯母版標(biāo)題樣式,*,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,第四章 平面圖與圖的著色,4.1 平面圖,4.2 極大平面圖,4.3,非平面圖,4.4,圖的平面性檢測,4.5,對偶圖,4.6,色素與色素多項式,4.1 平面圖,平面圖,：,指的是畫在平面上的一個圖形，它的所有的邊都不相交（除頂點外）。,可,(,嵌入,),平面圖,：,如果一個圖經(jīng)過重畫之后，可以畫成平面上的一個邊不相交的圖形，則該圖便稱為平面圖（可嵌入平面(,embeding)）。,G,的一個面或域：,G,是一個平面圖，由它的若干條邊所構(gòu)成的一個區(qū)域內(nèi)如果不含任何結(jié)點及邊，稱該區(qū)域為一個面或域。,無窮面,Th4.1.1,：設(shè)是一個連通的平面圖，,n，m,和,d,分別表示圖的頂點數(shù)，邊數(shù)和面數(shù)，則,n-m+d=2。,Cor4.1.1：,設(shè)為具有,n,個頂點，,m,條邊，,f,個面和,k,個分圖的平面上的圖，則,n-m+f=k+1。,Th4.1.2,：設(shè)平面連通圖,G,沒有割邊，且每個域的邊界至少是,t,，則,mt(n-2)/(t-2),4.2 極大平面圖,Def4.2.1,：設(shè),G,是,n3,的簡單平面圖，如果在任意兩個不相鄰的結(jié)點之間加入一條邊，就會破壞圖的平面性，則該,G,為極大平面圖。,極大平面圖的性質(zhì)：,1.G,是連通的；,2.G,不存在割邊；,3.G,的每個域的邊界都是,3,。,Th4.2.1,極大平面圖,G,中,: m=3n-6 d=2n-4,Cor4.2.1,簡單平面圖滿足,m3n-6 d2n-4,Th4.2.2,：簡單平面圖,G,中存在度小于,6,的結(jié)點。,4.3,非平面圖,Th4.3.1 k,5,和,k,3.3,不是平面圖。,Def4.3.1,如果兩個圖能夠從一個圖,G,出發(fā)，通過在,G,的邊上插入有限多個2次頂點得到，則稱這兩個圖是同胚。,Th4.2：,一個圖為平面圖當(dāng)且僅當(dāng)它不含與,k5,或,k3.3,同胚的子圖。,4.4,圖的平面性檢測,預(yù)處理見書,P73,塊：如果,G,中存在割點,v,，這時可把圖,G,從割點處分離，構(gòu)成若干個不含割點的連通子圖，稱為塊。,片：設(shè),H,是,G,的子圖，,e1,，,e2,E(G)-E(H),，若存在一條路徑,W,，使得：,1,）,W,的首尾兩條邊分別是,e1,，,e2,；,2,）,W,的內(nèi)點和,V(H),不相交，則說,e1e2,。,在,下的每個等價類的誘導(dǎo)子圖稱為,G,中,H,的片。,DMP,算法見書,4.5,對偶圖,對偶圖(,dual graph)：,任意一個平面圖,G，,如果：1）在,G,的每個面,Fi,中選定一個點,vi*,作為頂點；,2）對應(yīng)于,G,的每條邊,e，,畫一條線,e*，,它只與,e,相交，而不與,G,的其它邊相交，并且連接位于,e,兩邊的面,Fi,中的頂點,vi*,作為邊。,這樣構(gòu)成的圖稱為圖,G,的對偶圖，記為,G*。,Note:1）G,中的每個懸點都產(chǎn)生,G*,的一個自環(huán)；,2）,G,中多于一條公共邊的面，便產(chǎn)生多重邊；,3）,H, G,但是,H*, G*,不一定；,4）,G*,是連通的且為可平面嵌入的。,Th4.5.1：,設(shè),G,為,n，m,和,f,且為平面上的連通圖，其對偶圖,G*,有,n*，m*,和,f*,n*= d， m= m*,和,n,=,d*。,Th4.5.2：,設(shè),G,為連通平面圖，則,G*G。,Th4.5.3：,設(shè),G,有對偶圖,G,為平面圖。,地圖：不含橋的連通平面上的圖。,地圖為,k,可面著色的：如果它的每個面都可以用,k,種顏色之一去著色，使得任何兩個相鄰的面(即有公共邊的面)都有不同的顏色。,Th4.5.4,每個平面圖都是5可面著色的。,Th4.5.5,：,如果每個3正規(guī)的地圖是4可面著色的，則4色定理成立。,4.6,色素與色素多項式,Def 4.6.1:G,為,k,可著色的：設(shè),G,是一個無自環(huán)圖，如果對它的每個頂點可以用,k,種顏色之一著色，使得沒有兩個相鄰的頂點有相同的顏色，則稱,G,是,k,可著色的。,Def 4.6.2:G,為,k,色圖(,k Chromatic)：,設(shè),G,是一個無自環(huán)圖，如果,G,為,k,可著色的，但不是,k-1,可著色的，則稱,G,為,k,色圖或稱,G,的色數(shù)(,chromatic number),為,k，,記為：,X(G)。,Def 4.6.3:G,是,k,可邊著色的：如果圖,G,的所有的邊皆可用,k,種顏色著色，使得任何兩條相鄰的邊均具有不同的顏色，則稱,G,是,k,邊著色的。,Def 4.6.4:k,為,G,的邊色數(shù),：,如果,G,為,k,可邊著色的，但不是,k-1,可邊著色的，則稱,k,為,G,的邊色數(shù),，,記為：,X(G)。,特別圖的色素：,1,、,G,為空圖,X(G,）,= 1,2,、,G,為,kn,完全圖，則,X(G,）,= n,3,、,G,為,kn-e,圖，則,X(G,）,= n-1,4,、,G,為二部圖，則,X(G,）,= 2,5,、,G,為,2n,點的回路，則,X(G,）,= 2,6,、,G,為,2n+1,點的回路，則,X(G,）,= 3,7,、,G,為,n,（,2,）點的樹，則,X(G,）,= 2,Th4.6.1:,一個非空圖：,X(G,）,= 2,G,無奇回路,Th4.6.2:,平面連通圖,G,的域可,2,面著色,G,為歐拉圖。,Th4.6.3:,對于任意圖,G,，,X(G,）,d,o,+1( d,o,=max(d(v,i,),Def 4.6.5:,設(shè),i,，,j,是簡單圖,G,不相鄰的兩個結(jié)點。令,=,（ ， ）（,=V-i,j+ij,，,=E-(k,i)|(k,i) E-(k,j)|(k,j)E+(k,ij)|(k,i)E,或,(k,j)E),Th4.6.4:,設(shè),i,，,j,是簡單圖,G,不相鄰的兩個結(jié)點，則,X(G,）,= min X( ), X( ),。,Def4.6.6: f(G,t),表示,G,的不同的,k,著色,(,兩次不同著色，是指至少一個點的著色不同,),數(shù)目。,Th4.6.5:,設(shè),i,，,j,是簡單圖,G,不相鄰的兩個結(jié)點，則,f(G,t,）,= f( ,t)+f( , t ),。,作業(yè)：,P87 1, 2, 3 , 4 1) ,6 1),7,