圖論平面圖與對(duì)偶圖

1、4.1 平面圖4.2 平面圖上的歐拉公式4.3 對(duì)偶圖4.1 平面圖平面上的圖(plane graph)：指的是畫在平面上的一個(gè)圖形，它的所有的邊都不相交（除頂點(diǎn)外）。平面圖(planar graph)：如果一個(gè)圖經(jīng)過重畫之后，可以畫成平面上的一個(gè)邊不相交的圖形，則該圖便稱為平面圖（可嵌入平面(embeding)）。Jordan curve：自身不相交的連續(xù)曲線。Jordan closed curve： Jordan curve 兩個(gè)端點(diǎn)重合。Jordan curve theorem：C為在平面上的Jordan closed curve，平面的其余部分被分成不相交的開集，分別稱為C的外部和內(nèi)部

2、，則連接內(nèi)部和外部點(diǎn)的任何連續(xù)曲線必與C相交。Th4.1：k5和k3.3不是平面圖。同胚(homeomorphism):1）如果兩個(gè)圖能夠從一個(gè)圖G出發(fā)，通過在G的邊上插入有限多個(gè)2次頂點(diǎn)得到，則稱這兩個(gè)圖是同胚。2）如果兩個(gè)圖是同構(gòu)的或通過反復(fù)插入或消去2次頂點(diǎn)后是同構(gòu)的，則稱這兩個(gè)圖是同胚。Th4.2：一個(gè)圖為平面圖當(dāng)且僅當(dāng)它不含與k5或k3.3同胚的子圖。Th4.3：一個(gè)圖為平面圖當(dāng)且僅當(dāng)它不含可以縮成k5或k3.3的子圖。交叉數(shù)：為G畫在平面上時(shí)，它的邊出現(xiàn)相交的最少可能的數(shù)目。記為：Cr(G)。4.2 平面圖上的歐拉公式平面上的一個(gè)點(diǎn)x不與相交的點(diǎn)：x既不是的頂點(diǎn)也不是的任何一條邊上

3、的點(diǎn)。的包含的面：為平面上所有可以從出發(fā)通過一條不與相交的Jordan曲線而能達(dá)到的點(diǎn)的集合。無(wú)窮面可嵌入曲面：如果一個(gè)圖能夠畫在一張曲面上，使得它的邊除了頂點(diǎn)外再無(wú)其它交點(diǎn)。Th:一個(gè)圖是可嵌入平面它是可嵌入球面。Th4.4：設(shè)是一個(gè)連通的平面上的圖，n，m和f分別表示圖的頂點(diǎn)數(shù)，邊數(shù)和面數(shù)，則n-m+f=2。Cor.5：設(shè)為具有n個(gè)頂點(diǎn)，m條邊，f個(gè)面和k個(gè)分圖的平面上的圖，則n-m+f=k+1。Cor.：為簡(jiǎn)單連通平面圖|V|=n（n2）和|E|=m）m3n-6；）如果G中不含三角形，則m 2n-4。Cor.7： k5和k3.3不是平面圖。Th4.8：每個(gè)簡(jiǎn)單平面圖均包含一個(gè)次數(shù)最多為5

4、的頂點(diǎn)。下面內(nèi)容見書：一個(gè)圖的厚度：Th4.94.3 對(duì)偶圖1. 對(duì)偶圖(dual graph)： 任意一個(gè)平面上的圖G，如果：1）在G 的每個(gè)面Fi中選定一個(gè)點(diǎn)vi*作為頂點(diǎn)；2）對(duì)應(yīng)于G的每條邊e，畫一條線e*，它只與e相交，而不與G的其它邊相交，并且連接位于e兩邊的面Fi中的頂點(diǎn)vi*作為邊。這樣構(gòu)成的圖稱為圖G的對(duì)偶圖，記為G*。Note:1）G中的每個(gè)懸點(diǎn)都產(chǎn)生G*的一個(gè)自環(huán)； 2）G中多于一條公共邊的面，便產(chǎn)生多重邊； 3）H G 但是H* G* 不一定； 4） G* 是連通的且為平面嵌入的。Lemma4.10：設(shè)G為n，m和f且為平面上的連通圖，其對(duì)偶圖G*有n*，m*和f* n*= f， m= m*和n =f*。Th4.11：設(shè)G為平面上的連通圖，則G* G。Th4.12：設(shè)G為平面上的連通圖且G* 為G的對(duì)偶圖，則G的邊集構(gòu)成G的一個(gè)圈對(duì)應(yīng)的G*的邊集構(gòu)成G*的一個(gè)