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

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

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

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

例下述各圖都是二部圖

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

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

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

定義1

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

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

定義2

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

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

定理2

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

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

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

定理3

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

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

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

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

對右圖

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

定義4

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

設(shè)G＝〈V,E〉是有n個(gè)結(jié)點(diǎn)的簡單圖，

1）如果任一對不相鄰結(jié)點(diǎn)u，v∈V，均有

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

2）如果任一對不相鄰結(jié)點(diǎn)u，v∈V，均有

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