圖論平面圖與對偶圖

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

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

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

4、的頂點。下面內(nèi)容見書：一個圖的厚度：Th4.94.3 對偶圖1. 對偶圖(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* 是連通的且為平面嵌入的。Lemma4.10：設(shè)G為n，m和f且為平面上的連通圖，其對偶圖G*有n*，m*和f* n*= f， m= m*和n =f*。Th4.11：設(shè)G為平面上的連通圖，則G* G。Th4.12：設(shè)G為平面上的連通圖且G* 為G的對偶圖，則G的邊集構(gòu)成G的一個圈對應(yīng)的G*的邊集構(gòu)成G*的一個