二部圖與完全二部圖詳解

（優(yōu)選）二部圖與完全二部圖課件計算機數(shù)學1目前一頁\總數(shù)二十三頁\編于十八點二部圖

定義設無向圖G=<V,E>,若能將V劃分成V1和V2(V1V2=V,V1V2=),使得G中的每條邊的兩個端點都一個屬于V1,另一個屬于V2,則稱G為二部圖,記為<V1,V2,E>,稱V1和V2為互補頂點子集.又若G是簡單圖,且V1中每個頂點都與V2中每個頂點相鄰,則稱G為完全二部圖,記為Kr,s,其中r=|V1|,s=|V2|.

注意:n階零圖為二部圖.2目前二頁\總數(shù)二十三頁\編于十八點二部圖的判別法

定理無向圖G=<V,E>是二部圖當且僅當G中無奇圈

例下述各圖都是二部圖

3目前三頁\總數(shù)二十三頁\編于十八點

歐拉圖歷史上的哥尼斯堡七橋問題是著名的圖論問題。

問題是這樣的：18世紀的東普魯士有個哥尼斯堡城，在橫貫全城的普雷格爾河兩岸和兩個島之間架設了7座橋，它們把河的兩岸和兩個島連接起來（如圖1）。每逢假日，城中居民進行環(huán)城游玩，人們對此提出了一個“遍游”問題，即能否有這樣一種走法，使得從某地出發(fā)通過且只通過每座橋一次后又回到原地呢？4目前四頁\總數(shù)二十三頁\編于十八點我們將圖1中的哥尼斯堡城的4塊陸地部分分別標以A，B，Ｃ，D，將陸地設想為圖的結點，而把橋畫成相應的連接邊，這樣圖1可簡化成圖2。于是七橋“遍游”問題等價于在圖2中，從某一結點出發(fā)找到一條回路，通過它的每條邊一次且僅一次，并回到原來的結點。5目前五頁\總數(shù)二十三頁\編于十八點

定義1

給定無孤立結點的圖G，若存在一條經(jīng)過G中每邊一次且僅一次的回路，則該回路為歐拉回路。具有歐拉回路的圖稱為歐拉圖。例如，給出如圖3所示的兩個圖，容易看出，(a)是歐拉圖，而(b)不是歐拉圖。6目前六頁\總數(shù)二十三頁\編于十八點

下圖中，(a)圖的每個結點的度數(shù)都為４，所以它是歐拉圖；(b)圖不是歐拉圖。但我們繼續(xù)考察(b)圖可以發(fā)現(xiàn)，該圖中有一條路v2v3v4v5v2v1v5，它經(jīng)過(b)圖中的每條邊一次且僅一次，我們把這樣的路稱為歐拉路。定理1連通圖G是歐拉圖的充要條件是G的所有結點的度數(shù)都是偶數(shù)。7目前七頁\總數(shù)二十三頁\編于十八點

定義2

通過圖G的每條邊一次且僅一次的路稱為圖G的歐拉路。

對于歐拉路有下面的判定方法。

定理2

連通圖G具有一條連接結點vi和vj的歐拉路當且僅當vi和vj是G中僅有的兩個奇數(shù)度結點。8目前八頁\總數(shù)二十三頁\編于十八點我國民間很早就流傳一種“一筆畫”游戲。由定理1和定理2知，有兩種情況可以一筆畫。

1)如果圖中所有結點是偶數(shù)度結點，則可以任選一點作為始點一筆畫完；

2)如果圖中只有兩個奇度結點，則可以選擇其中一個奇度結點作為始點也可一筆畫完。9目前九頁\總數(shù)二十三頁\編于十八點【例】下圖是一幢房子的平面圖形，前門進入一個客廳，由客廳通向4個房間。如果要求每扇門只能進出一次，現(xiàn)在你由前門進去，能否通過所有的門走遍所有的房間和客廳，然后從后門走出。10目前十頁\總數(shù)二十三頁\編于十八點解:將4個房間和一個客廳及前門外和后門外作為結點，若兩結點有邊相連就表示該兩結點所表示的位置有一扇門相通。由此得圖(b)。由于圖中有4個結點是奇度結點，故由定理7.4.2知本題無解。11目前十一頁\總數(shù)二十三頁\編于十八點

定理3

一個連通有向圖具有（有向）歐拉回路的充要條件是圖中每個結點的入度等于出度。一個連通有向圖具有有向歐拉路的充要條件是最多除兩個結點外的每個結點的入度等于出度，但在這兩個結點中，一個結點的入度比出度大1，另一個結點的入度比出度少1。類似于無向圖的結論，對有向圖有以下結果。12目前十二頁\總數(shù)二十三頁\編于十八點平面圖和平面嵌入定義如果能將圖G除頂點外邊不相交地畫在平面上,則稱G是平面圖.這個畫出的無邊相交的圖稱作G的平面嵌入.沒有平面嵌入的圖稱作非平面圖.

例如下圖中(1)~(4)是平面圖,(2)是(1)的平面嵌入，(4)是(3)的平面嵌入.(5)是非平面圖.目前十三頁\總數(shù)二十三頁\編于十八點平面圖和平面嵌入(續(xù))今后稱一個圖是平面圖,可以是指定義中的平面圖,又可以是指平面嵌入,視當時的情況而定.當討論的問題與圖的畫法有關時,是指平面嵌入.K5和K3,3是非平面圖設GG,若G為平面圖,則G也是平面圖;若G為非平面圖,則G也是非平面圖.Kn(n5),K3,n(n3)都是非平面圖.平行邊與環(huán)不影響圖的平面性.K5K3,3目前十四頁\總數(shù)二十三頁\編于十八點平面圖的面與次數(shù)設G是一個平面嵌入G的面:由G的邊將平面劃分成的每一個區(qū)域無限面(外部面):面積無限的面,用R0表示有限面(內部面):面積有限的面,用R1,R2,…,Rk表示面Ri的邊界:包圍Ri的所有邊構成的回路組面Ri的次數(shù):Ri邊界的長度，用deg(Ri)表示說明:構成一個面的邊界的回路組可能是初級回路,簡單回路,也可能是復雜回路,還可能是非連通的回路之并.定理

平面圖各面的次數(shù)之和等于邊數(shù)的2倍.目前十五頁\總數(shù)二十三頁\編于十八點平面圖的面與次數(shù)(續(xù))例1右圖有4個面,deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8.請寫各面的邊界.例2左邊2個圖是同一個平面圖的平面嵌入.R1在(1)中是外部面,在(2)中是內部面;R2在(1)中是內部面,在(2)中是外部面.其實,在平面嵌入中可把任何面作為外部面.目前十六頁\總數(shù)二十三頁\編于十八點歐拉公式定理11(歐拉公式)設G為n階m條邊r個面的連通平面圖，則nm+r=2.證對邊數(shù)m做歸納證明.m=0,G為平凡圖,結論為真.設m=k(k0)結論為真,m=k+1時分情況討論如下:(1)G中無圈,則G必有一個度數(shù)為1的頂點v,刪除v及它關聯(lián)的邊,記作G.G連通,有n-1個頂點,k條邊和r個面.由歸納假設,(n-1)-k+r=2,即n-(k+1)+r=2,得證m=k+1時結論成立.(2)否則,刪除一個圈上的一條邊,記作G.G連通,有n個頂點,k條邊和r-1個面.由歸納假設,n-k+(r-1)=2,即n-(k+1)+r=2,得證m=k+1時結論也成立.證畢.目前十七頁\總數(shù)二十三頁\編于十八點哈密爾頓圖

與歐拉回路類似的是哈密爾頓回路問題。它是1859年哈密爾頓首先提出的一個關于12面體的數(shù)學游戲：能否在下頁圖中找到一個回路，使它含有圖中所有結點一次且僅一次？若把每個結點看成一座城市，連接兩個結點的邊看成是交通線，那么這個問題就變成能否找到一條旅行路線，使得沿著該旅行路線經(jīng)過每座城市恰好一次，再回到原來的出發(fā)地呢？為此，這個問題也被稱作周游世界問題。18目前十八頁\總數(shù)二十三頁\編于十八點12面體游戲示圖

對右圖

，圖中粗線給出了這樣的回路。

定義4

給定圖G，若有一條路通過G中每個結點恰好一次，則這樣的路稱為哈密爾頓路；若有一個圈，通過G中每個結點恰好一次(起點兩次)，這樣的圈稱為哈密爾頓回路（或哈密爾頓圈）。具有哈密爾頓回路的圖稱為哈密爾頓圖。19目前十九頁\總數(shù)二十三頁\編于十八點盡管哈密爾頓回路與歐拉回路問題在形式上極為相似，但是到目前為止還不知道一個圖為哈密爾頓圖的充要條件，尋找該充要條件仍是圖論中尚未解決的主要問題之一。下面先給出一個簡單而有用的必要條件。定理1設圖G＝〈V,E〉是哈密爾頓圖，則對于V的每個非空子集S，均有W（G－S）≤|S|成立，其中W（G－S）是圖G－S的連通分支數(shù)。20目前二十頁\總數(shù)二十三頁\編于十八點21目前二十一頁\總數(shù)二十三頁\編于十八點判斷哈密爾頓圖的充分條件很多，我們僅介紹一個。定理2

設G＝〈V,E〉是有n個結點的簡單圖，

1）如果任一對不相鄰結點u，v∈V，均有

deg(u)＋deg(v)≥n－1，則在G中存在一條哈密爾頓路；

2）如果任一對不相鄰結點u，v∈V，均有

deg(u)＋deg(v)≥n，則G是哈密爾頓圖。22目前二十二頁\總數(shù)二十三頁\編于十八點【例3】某地有５個風景點。若每個景點均有兩條道路與其他景點相通，問是否可經(jīng)過每個景點恰