圖論平面圖與圖的著色

上傳人:功*** 文檔編號:248166614 上傳時間:2024-10-22 格式:PPT 頁數(shù):14 大?。?75.50KB
收藏 版權申訴 舉報 下載
圖論平面圖與圖的著色_第1頁
第1頁 / 共14頁
圖論平面圖與圖的著色_第2頁
第2頁 / 共14頁
圖論平面圖與圖的著色_第3頁
第3頁 / 共14頁

下載文檔到電腦,查找使用更方便

10 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《圖論平面圖與圖的著色》由會員分享,可在線閱讀,更多相關《圖論平面圖與圖的著色(14頁珍藏版)》請在裝配圖網上搜索。

1、,單擊此處編輯母版標題樣式,*,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,第四章 平面圖與圖的著色,4.1 平面圖,4.2 極大平面圖,4.3,非平面圖,4.4,圖的平面性檢測,4.5,對偶圖,4.6,色素與色素多項式,4.1 平面圖,平面圖,:,指的是畫在平面上的一個圖形,它的所有的邊都不相交(除頂點外)。,可,(,嵌入,),平面圖,:,如果一個圖經過重畫之后,可以畫成平面上的一個邊不相交的圖形,則該圖便稱為平面圖(可嵌入平面(,embeding))。,G,的一個面或域:,G,是一個平面圖,由它的若干條邊所構成的一個區(qū)域內如果不含任何結點及邊,稱該區(qū)域為一個面或域。,無窮面,

2、Th4.1.1,:設是一個連通的平面圖,,n,m,和,d,分別表示圖的頂點數(shù),邊數(shù)和面數(shù),則,n-m+d=2。,Cor4.1.1:,設為具有,n,個頂點,,m,條邊,,f,個面和,k,個分圖的平面上的圖,則,n-m+f=k+1。,Th4.1.2,:設平面連通圖,G,沒有割邊,且每個域的邊界至少是,t,,則,mt(n-2)/(t-2),4.2 極大平面圖,Def4.2.1,:設,G,是,n3,的簡單平面圖,如果在任意兩個不相鄰的結點之間加入一條邊,就會破壞圖的平面性,則該,G,為極大平面圖。,極大平面圖的性質:,1.G,是連通的;,2.G,不存在割邊;,3.G,的每個域的邊界都是,3,。,Th4

3、.2.1,極大平面圖,G,中,: m=3n-6 d=2n-4,Cor4.2.1,簡單平面圖滿足,m3n-6 d2n-4,Th4.2.2,:簡單平面圖,G,中存在度小于,6,的結點。,4.3,非平面圖,Th4.3.1 k,5,和,k,3.3,不是平面圖。,Def4.3.1,如果兩個圖能夠從一個圖,G,出發(fā),通過在,G,的邊上插入有限多個2次頂點得到,則稱這兩個圖是同胚。,Th4.2:,一個圖為平面圖當且僅當它不含與,k5,或,k3.3,同胚的子圖。,4.4,圖的平面性檢測,預處理見書,P73,塊:如果,G,中存在割點,v,,這時可把圖,G,從割點處分離,構成若干個不含割點的連通子圖,稱為塊。,片

4、:設,H,是,G,的子圖,,e1,,,e2,E(G)-E(H),,若存在一條路徑,W,,使得:,1,),W,的首尾兩條邊分別是,e1,,,e2,;,2,),W,的內點和,V(H),不相交,則說,e1e2,。,在,下的每個等價類的誘導子圖稱為,G,中,H,的片。,DMP,算法見書,4.5,對偶圖,對偶圖(,dual graph):,任意一個平面圖,G,,如果:1)在,G,的每個面,Fi,中選定一個點,vi*,作為頂點;,2)對應于,G,的每條邊,e,,畫一條線,e*,,它只與,e,相交,而不與,G,的其它邊相交,并且連接位于,e,兩邊的面,Fi,中的頂點,vi*,作為邊。,這樣構成的圖稱為圖,G

5、,的對偶圖,記為,G*。,Note:1)G,中的每個懸點都產生,G*,的一個自環(huán);,2),G,中多于一條公共邊的面,便產生多重邊;,3),H, G,但是,H*, G*,不一定;,4),G*,是連通的且為可平面嵌入的。,Th4.5.1:,設,G,為,n,m,和,f,且為平面上的連通圖,其對偶圖,G*,有,n*,m*,和,f*,n*= d, m= m*,和,n,=,d*。,Th4.5.2:,設,G,為連通平面圖,則,G*G。,Th4.5.3:,設,G,有對偶圖,G,為平面圖。,地圖:不含橋的連通平面上的圖。,地圖為,k,可面著色的:如果它的每個面都可以用,k,種顏色之一去著色,使得任何兩個相鄰的面

6、(即有公共邊的面)都有不同的顏色。,Th4.5.4,每個平面圖都是5可面著色的。,Th4.5.5,:,如果每個3正規(guī)的地圖是4可面著色的,則4色定理成立。,4.6,色素與色素多項式,Def 4.6.1:G,為,k,可著色的:設,G,是一個無自環(huán)圖,如果對它的每個頂點可以用,k,種顏色之一著色,使得沒有兩個相鄰的頂點有相同的顏色,則稱,G,是,k,可著色的。,Def 4.6.2:G,為,k,色圖(,k Chromatic):,設,G,是一個無自環(huán)圖,如果,G,為,k,可著色的,但不是,k-1,可著色的,則稱,G,為,k,色圖或稱,G,的色數(shù)(,chromatic number),為,k,,記為:

7、,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

8、,、,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:,設,i,,,j,是簡單圖,G,不相鄰的兩個結點。令,=,( , )(,=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:,設,i,,,j,是簡單圖,G,不相鄰的兩個結點,則,X(G,),= min X( ), X( ),。,Def4.6.6: f(G,t),表示,G,的不同的,k,著色,(,兩次不同著色,是指至少一個點的著色不同,),數(shù)目。,Th4.6.5:,設,i,,,j,是簡單圖,G,不相鄰的兩個結點,則,f(G,t,),= f( ,t)+f( , t ),。,作業(yè):,P87 1, 2, 3 , 4 1) ,6 1),7,

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 裝配圖網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

相關資源

更多
正為您匹配相似的精品文檔

相關搜索

關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網版權所有   聯(lián)系電話:18123376007

備案號:ICP2024067431-1 川公網安備51140202000466號


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對上載內容本身不做任何修改或編輯。若文檔所含內容侵犯了您的版權或隱私,請立即通知裝配圖網,我們立即給予刪除!