第四章平面圖與圖著色

4.1平面圖定義4.1.1若能把圖G畫在一種平面上，使任何兩條邊都不相交,就稱G可嵌入平面，或稱G是可平面圖.可平面圖在平面一種嵌入稱為平面圖.假如G是可平面圖,那么它任何導(dǎo)出子圖也是可平面圖.第1頁(yè)平面圖定義4.1.2設(shè)G是一種平面圖,由它若干條邊所組成一種區(qū)域內(nèi)假如不含任何結(jié)點(diǎn)及邊，就稱該區(qū)域?yàn)镚一種面或域.包圍這個(gè)域諸邊稱為該域邊界.為了討論方便,我們把平面圖G外邊無限區(qū)域稱為無限域,其他域都叫做內(nèi)部域.假如兩個(gè)域有共同邊界，就說它們是相鄰,不然是不相鄰.假如e不是割邊,它一定是某兩個(gè)域共同邊界.第2頁(yè)平面圖定理4.1.1設(shè)G是平面連通圖,則G域數(shù)目是d=m–n+2.證明:G是連通圖,有支撐樹T,它包括n-1條邊，不產(chǎn)生回路,因此對(duì)T來說只有一種無限域.由于G是平面圖,每加入一條余樹邊,它一定不與其他邊相交,也就是說一定是跨在某個(gè)域內(nèi)部,把該區(qū)域提成兩部分.這樣,加入Gm-n+1條余樹邊,就生成了m-n+2個(gè)域.第3頁(yè)平面圖推論4.1.1若平面圖G有k個(gè)連通支,則n–m+d=k–1.推論4.1.2對(duì)一般平面圖G,恒有n–m+d>=2.第4頁(yè)平面圖定理4.1.2設(shè)平面連通圖G沒有割邊,且每個(gè)域邊界數(shù)最少是t,則m<=t*(n-2)/(t–2)證明:設(shè)G有d個(gè)區(qū)域,每個(gè)域邊界樹最少是t,且每條邊都與兩個(gè)不一樣域相鄰.因此td<=2m.代入歐拉公式:(2m/t)>=m-n+2,即,m<=t*(n-2)/(t–2).第5頁(yè)4.3非平面圖假如圖G不能嵌入平面,滿足任意兩邊只能在結(jié)點(diǎn)處相交,那么G就稱為非平面圖這樣,按平面性質(zhì)進(jìn)行劃分,圖G分為兩大類:可平面圖和非平面圖.第6頁(yè)非平面圖定理4.3.1是非平面圖.證明:在中,n=5,m=10.假如它是可平面圖,應(yīng)當(dāng)有m<=3n-6.而此時(shí)3n-6=9,矛盾.定理4.3.2是非平面圖.證明:假定是可平面圖,由于n=6,m=9.由歐拉公式,d=5.但G中沒有子圖,因此4d<=2m,亦即20<=18,矛盾.第7頁(yè)非平面圖商定和分別記為和圖.定義4.3.1在和圖上任意任意增加某些度為2結(jié)點(diǎn)之后得到圖象為型和型圖,統(tǒng)稱為K型圖.定理4.3.3G是可平面圖充要條件是G不存在K型圖.第8頁(yè)4.5對(duì)偶圖定義4.5.1滿足如下條件圖G*稱為G對(duì)偶圖.G中每個(gè)確定域內(nèi)設(shè)置一種結(jié)點(diǎn).對(duì)域和共同邊界,有一條邊,并與相交一次.若處于域之內(nèi),則有一自環(huán)與相交一次.

第9頁(yè)對(duì)偶圖性質(zhì)4.5.1假如G是平面圖,G一定有對(duì)偶圖G*,并且G*是唯一.由D過程即可得證.性質(zhì)4.5.2G*是連通圖.在平面G里,每個(gè)域f都存在相鄰域,并且對(duì)G任何部分域來說，都存在與它們之中某個(gè)域相鄰域.這樣由對(duì)偶圖定義可知G*連通.第10頁(yè)對(duì)偶圖性質(zhì)4.5.3若G是平面連通圖,那么性質(zhì)4.5.4平面連通圖G與其對(duì)偶圖G*結(jié)點(diǎn),邊和域之間存在如下對(duì)應(yīng)關(guān)系:m=m*,n=d*,d=n*.第11頁(yè)對(duì)偶圖性質(zhì)4.5.5若G是平面連通圖一種初級(jí)回路,S*是G*中與C各邊 對(duì)應(yīng)集合,那么S*是G*一種割集.證明：Ｃ把Ｇ域提成兩部分，因此把G*結(jié)點(diǎn)提成不連通兩部分，由性質(zhì)4.5.2，G*兩部分是分別連通，因此那么S*是G*一種割集．

第12頁(yè)對(duì)偶圖定理4.5.1G有對(duì)偶圖充要條件是G為平面圖.證明:充足性直接由4.5.1得證.先證必要性:即非平面圖沒有對(duì)偶圖.由庫(kù)拉圖斯基定理，非平面圖一定具有和型子圖；而，型子圖是和圖中增加

定理4.5.2每一種平面圖G都是5-可著色.第13頁(yè)對(duì)偶圖定理4.5.3假如平面圖G有哈密頓回路,則四色猜想成立.定理4.5.4若任何一種3-正則平面圖域可四著色,則任何一種平面域也能夠四著色.第14頁(yè)4.6色數(shù)與色數(shù)多項(xiàng)式定義4.6.1給定圖G,滿足相鄰點(diǎn)結(jié)點(diǎn)著以不一樣顏色最少顏色數(shù)為G色數(shù),記為γ(G).定義4.6.2給定圖G,滿足相鄰邊著以不一樣顏色最少顏色數(shù)目稱為G邊色數(shù),記為β(G).第15頁(yè)色數(shù)與色數(shù)多項(xiàng)式定理4.6.1一種非空?qǐng)D,γ(G)=2,當(dāng)且僅當(dāng)它沒有奇回路.證明：充足性：在Ｇ中確定一種林，其每個(gè)連通子圖都是樹Ｔ，．由于每個(gè)回路都是偶回路．因此加入每一條余樹邊都不會(huì)使結(jié)點(diǎn)著色發(fā)生變化，因此．必要性：假如Ｇ中有奇回路，則．矛盾．第16頁(yè)色數(shù)與色數(shù)多項(xiàng)式定理4.6.2對(duì)于任意一種圖G,其中證明：對(duì)Ｇ結(jié)點(diǎn)進(jìn)行歸納，n＝１時(shí)成立．設(shè)n＝k－１時(shí)成立，當(dāng)n＝k時(shí)，從Ｇ中任意移去一點(diǎn)得，．于是，其中是結(jié)點(diǎn)最大度，由于，因此．即種顏色能夠?qū)Y(jié)點(diǎn)著色，放回結(jié)點(diǎn)恢復(fù)成Ｇ，由于，因此比有一種與鄰點(diǎn)都不一樣顏色可對(duì)著色．第17頁(yè)色數(shù)與色數(shù)多項(xiàng)式定理4.6.3對(duì)于任意一種圖G.

γ(G)<=1+maxδ(G’)其中δ(G’)是G導(dǎo)出子圖G’中結(jié)點(diǎn)最小度,極大是對(duì)所有G’而言.第18頁(yè)色數(shù)與色數(shù)多項(xiàng)式定義4.6.3設(shè)i,j是簡(jiǎn)單圖G不相鄰兩個(gè)結(jié)點(diǎn).令也是一種簡(jiǎn)單圖,其結(jié)點(diǎn)集邊集第19頁(yè)色數(shù)與色數(shù)多項(xiàng)式定理4.6.4設(shè)i,j是簡(jiǎn)單圖G不相鄰結(jié)點(diǎn),則證明：對(duì)Ｇ中結(jié)點(diǎn)任何著色，i和j或者將著以同色，或者異色．設(shè)i，j著以異色情況下Ｇ最少著色數(shù)為，i，j著以同色情況下最少著色數(shù)是．這樣，顯然式中因此定理得證第20頁(yè)色數(shù)與色數(shù)多項(xiàng)式定理4.6.5定理4.6.6

第21頁(yè)色數(shù)與色數(shù)多項(xiàng)式定理