第八章 幾種特殊的圖

1、第八章 幾種特殊的圖8.1二部圖 無向圖G = <V，E>稱為二部圖，如果有非空集合X，Y使XY = V，XY = Æ，且對每一eÎE，e = (x, y)，xÎX，yÎY。此時常用<X，Y，E>表示二部圖G。若對X中任一x及Y中任一y恰有一邊(x, y)ÎE，, 則稱G為完全二部圖。當|X| = m，|Y| = n時，完全二部圖G記為Km,n。 圖8.1中（a），（b）為二部圖，（c）為完全二部圖K3,3，(d), (e)不是二部圖。 二部圖的下列特征性是重要的。 至少有兩個頂點的無向圖G為二部圖的充分必要條件是G不存

2、在奇數(shù)長度的回路。證明：必要性。設圖G為二部圖，記G=<V1,V2,E>,設v1,v2,v3,vk,v1是一個回路，不妨設v1V1,由二部圖的定義知，vk是偶數(shù)，路經(jīng)長度為偶數(shù)，所以，G不存在奇數(shù)長度的回路。充分性：（1）先設G是連通的，v1是任意一個頂點。記 V1=x|v1到x的路經(jīng)的長度是偶數(shù)V2=x|v1到x的路經(jīng)的長度是奇數(shù)下證V1,V2是V的分類，且每一條邊一個端點在V1另一個端點在V2中。匹配 設G = <V,E>為無向圖，E*ÍE。稱E*為G的一個匹配，如果E*中任何兩條邊都沒有公共端點。如果E*中再增加一條邊就不是匹配了，則稱E*為極大匹配。邊

3、數(shù)最多的匹配稱為最大匹配。最大匹配中的元素（邊）數(shù)叫匹配數(shù)，記為。 設若v與M中的某一條邊關聯(lián)，則稱v是M的飽和點，若G中每個頂點都是M的飽和點，則稱M是G的完美匹配。 圖8.2中各圖的粗線表示匹配中的邊（簡稱匹配邊）。（b）中匹配是最大的。         （a） （b） 注意：最大匹配總是存在但未必唯一。此外，完美匹配必定是最大的，但反之則不然。為討論最大匹配的求法及完全匹配的存在條件，需要下列術語。 設G = <V1，V2，E>是一個二部圖，M為G的一個最大匹配，若，則稱M為G的一個完備匹配。此時若，則稱V1到V2的

4、完備匹配，如果這時,M為G的完美匹配，(hall定理) 設G = <V1，V2，E>是一個二部圖，G中存在V1到V2的完備匹配的充要條件是V1中任意k（k=1,2, ）個頂點至少鄰接V2的k個頂點。 設G = <V1，V2，E>是一個二部圖，如果（1）V1中的每個頂點至少關聯(lián)t(t>0)條邊；（2）V2中的每個頂點至多關聯(lián)t(t>0)條邊，則G中存在V1到V2的完備匹配。8.2歐拉圖 給定圖G=<V，E>，通過G中的每一條邊一次且恰好一次的通路(回路)，稱為歐拉通路(歐拉回路)。存在歐拉通路的圖稱為半歐拉圖，存在歐拉回路的圖稱為歐拉圖。哥尼斯堡七

5、橋問題: 這是否是一個歐拉圖?一筆畫問題。 設G是無向連通圖，則G是半歐拉圖G中只有零個或兩個奇數(shù)度頂點。 設G是無向連通圖，則G是歐拉圖G中沒有奇數(shù)度頂點。連通有向圖G=<V，E>存在歐拉路徑G中除兩個頂點之外其余每個結點的入度等于出度，且這兩個頂點中一個頂點出度比入度大1，另一個頂點的入度比出度大1。連通有向圖G=<V，E>是歐拉圖G中每個結點的入度等于出度。K5是歐拉圖。例8.2.4 下列圖形能否一筆畫成?8.3哈密爾頓圖哈密爾頓周游世界問題：1856年，著名的愛爾蘭數(shù)學家Hamilton設計了一個游戲：給定世界上20個城市，用一個代表地球的十二面體的20個頂點分

6、別代表這20個城市。從某一個頂點出發(fā)，沿著十二面體的棱，經(jīng)過每個頂點恰好一次，最后回到出發(fā)點。設無向圖通過G中的每個頂點一次且恰好一次的通路(回路)，稱為哈密爾頓通路(哈密爾頓回路)。存在哈密爾頓通路的圖稱為半哈密爾頓圖。存在哈密爾頓回路的圖稱為哈密爾頓圖。圖形是哈密爾頓圖嗎？無向完全圖Kn(n3)是哈密爾頓圖。哈密爾頓圖問題盡管在形式上與歐拉圖問題極其相似，但至今還未得到關于哈密爾頓圖的簡明的充要條件，這屬于圖論中尚未解決的難題之一。下面分別介紹判定哈密爾頓圖的一個充分條件和一個必要條件。設G=<V，E>是哈密爾頓圖，V1是V的任一非空真子集，則p(G- V1)| V1|其中p(

7、G- V1)是從G中刪去V1中的頂點及以G中所有以V1中的頂點為端點的邊所得圖的連通分支數(shù)。 證明：可用有名的彼得森圖說明上述條件僅為必要條件而不是充分條件。設無向簡單圖G=<V，E>，若任兩個不相鄰的結點u，vV， deg(u)+deg(v)n-1，則G是半哈密爾頓圖。設無向簡單圖G=<V，E>，n3，若任兩個不相鄰的結點u，vV， deg(u)+deg(v)n，則G是哈密爾頓圖。某地有5個風景點，若每個風景區(qū)均有兩條道路與其它景點相通，問游客可否經(jīng)過每個景點恰好一次游完5個景點?8.4平面圖設一個無向圖G=<V，E>。若能把它畫在平面上，且除V中的頂點之

8、外，任意兩條邊均不相交，則稱該圖為平面圖。畫出的沒有邊相交的圖叫G的平面嵌入（平圖）。平面圖的例子。A B C D E有些圖表面上看上去有邊交叉，但經(jīng)過改畫后，就可使邊不交叉，則這樣的圖實際上是平面圖。但有些圖，無論怎樣改畫都避免不了邊的交叉，這樣的圖就是非平面圖。兩個典型的非平面圖: （庫拉圖斯基圖）。判別平面圖的一種直觀方法:(1)若一個圖無基本回路，則它是一個平面圖; 否則從有基本回路的圖找出一個長度盡可能大且邊不相交的基本回路;(2)將圖中那些交叉的邊，適當放置在已選定的基本回路內(nèi)側或外側。若最后能避免邊的交叉，則該圖是平面圖，否則它是非平面圖。設G是一個(連通)平面圖，若由G的若干條

9、邊組成的回路所界定的區(qū)域內(nèi)不含G的任何邊和頂點，則稱這樣的區(qū)域為G的一個（有限）面。面積無限的面叫無限面。包圍這個面f的各條邊所構成的回路，稱為該面的邊界，它的長度稱為面f的次數(shù)，記為deg(f)。用F表示G中所有面的集合。求下列平面圖的面、面的次數(shù)。 a b c d e f若G=<V，E>是平面圖，則deg (f)=2|E|。設G=<V，E，F(xiàn)>是連通平面圖，則n-m+f=2。設G=<V，E，F(xiàn)>是連通平面圖，|V|=n，|E|=m，每個面的次數(shù)至少為l(l3)，則m(n-2)。設G=<V，E，F(xiàn)>是連通的簡單平面圖，|V|=n，|E|=m，且n 3，則m 3n-6。設G=<V，E，F(xiàn)>是連通的簡單平面圖，|V|=n，|E|=m，則G中至少有一個頂點的度數(shù)不超過5。若圖G1與G2同構或圖G2可由圖G1中的一些邊上適當插入度為2 的結點或涂抹掉2度的結點合并相鄰邊后得到，則稱G1與G2同胚。若圖G中相鄰頂點u,v的初等收縮為（1）刪除邊(u,v),(2)用W代替(u,v),(3)W關聯(lián)u,v關聯(lián)的一切邊（除（u,v）. 一個圖G是平面圖óG中不含同胚于K3，3或K5的子圖。一個圖G是平