《離散數(shù)學(xué)》特殊圖-1

第8章一些特殊的圖8.1二部圖8.2歐拉圖8.3哈密頓圖8.4平面圖18.1二部圖

二部圖完全二部圖匹配極大匹配最大匹配匹配數(shù)完備匹配

2二部圖

定義

設(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)子集.若V1中每個(gè)頂點(diǎn)均與V2中每個(gè)頂點(diǎn)有且只有一條邊相關(guān)聯(lián),則稱二部圖G為完全二部圖,記為Kr,sr=|V1|,s=|V2|.注意:n階零圖（|E|＝0）為二部圖.3二部圖的判別法

定理無向圖G=<V,E>是二部圖當(dāng)且僅當(dāng)G中無奇數(shù)長度的回路（無奇圈）.

例：述各圖都是二部圖

4匹配

設(shè)G=<V,E>為無向圖,E*E匹配(邊獨(dú)立集):任2條均不相鄰的邊組成的邊子集任2條邊的端點(diǎn)都不一樣極大匹配:添加任一條邊后都不再是匹配的匹配最大匹配:邊數(shù)最多的極大匹配匹配數(shù):最大匹配中的邊數(shù),記為1

最大匹配的邊數(shù)不超過|V|的一半例3個(gè)圖的匹配數(shù)依次為3,3,4.5匹配(續(xù))設(shè)M為G中一個(gè)匹配，vV(G)v為M飽和點(diǎn):M中有邊與v關(guān)聯(lián)v為M非飽和點(diǎn):M中沒有邊與v關(guān)聯(lián)M為完美匹配:G的每個(gè)頂點(diǎn)都是M飽和點(diǎn)所有點(diǎn)都在匹配邊上完美匹配是最大匹配例關(guān)于M1,a,b,e,d是飽和點(diǎn)

f,c是非飽和點(diǎn)M1不是完美匹配M2是完美匹配M1M26二部圖中的匹配定義

設(shè)G=<V1,V2,E>為二部圖,M是G中最大匹配,若|M|＝min{|V1|，|V2|}，則稱M為G中的一個(gè)完備匹配V1或V2的任意節(jié)點(diǎn)都是M中邊的端點(diǎn)M是完備匹配，|V1||V2|則稱M為V1到V2的一個(gè)完備匹配.當(dāng)|V1|=|V2|時(shí),完備匹配變成完美匹配.兩部分一對一最大匹配一定存在，完備匹配不一定存在7二部圖中的匹配

(1)(2)(3)例圖中紅邊組成各圖的一個(gè)匹配，(1)為完備的,但不是完美的;(2)不是完備的,其實(shí)(2)中無完備匹配;(3)是完美的.8Hall定理

定理(Hall定理)設(shè)二部圖G=<V1,V2,E>中，|V1||V2|.G中存在從V1到V2的完備匹配當(dāng)且僅當(dāng)V1中任意k個(gè)頂點(diǎn)至少與V2中的k個(gè)頂點(diǎn)相鄰(k=1,2,…,|V1|).由Hall定理不難證明,上一頁圖(2)沒有完備匹配.定理設(shè)二部圖G=<V1,V2,E>中,V1中每個(gè)頂點(diǎn)至少關(guān)聯(lián)t條邊(t1),而V2中每個(gè)頂點(diǎn)至多關(guān)聯(lián)t條邊，則G中存在V1到V2的完備匹配.Hall定理中的條件稱為“相異性條件”,第二個(gè)定理中的條件稱為t條件.滿足t條件的二部圖一定滿足相異性條件.9一個(gè)應(yīng)用實(shí)例例某課題組要從a,b,c,d,e5人中派3人分別到上海、廣州、香港去開會.已知a只想去上海，b只想去廣州，c,d,e都表示想去廣州或香港.問該課題組在滿足個(gè)人要求的條件下，共有幾種派遣方案？解令G=<V1,V2,E>,其中V1={s,g,x},V2={a,b,c,d,e},

E={(u,v)|uV1,vV2,v想去u},其中s,g,x分別表示上海、廣州和香港.G如圖所示.G滿足相異性條件，因而可給出派遣方案，共有9種派遣方案(請給出這9種方案).10上圖是二部圖，滿足t條件（t＝2），存在V1到V2的完備匹配118.2歐拉圖－－一筆畫問題歐拉通路歐拉回路歐拉圖半歐拉圖

12哥尼斯堡七橋問題

歐拉圖是能一筆畫出的邊不重復(fù)的回路.13歐拉圖

歐拉通路:經(jīng)過圖中每條邊一次且僅一次，并且行遍圖中每個(gè)頂點(diǎn)的通路.歐拉回路:經(jīng)過圖中每條邊一次且僅一次，并且行遍圖中每個(gè)頂點(diǎn)的回路歐拉圖:有歐拉回路的圖.幾點(diǎn)說明：上述定義對無向圖和有向圖都適用.規(guī)定平凡圖為歐拉圖.歐拉通路是簡單通路,歐拉回路是簡單回路.環(huán)不影響圖的歐拉性.14一筆畫問題筆不離開紙，每邊只能畫一次，不允許重復(fù)，將圖畫出，稱該圖能一筆畫。如終點(diǎn)回到起點(diǎn)，則等價(jià)于該圖存在歐拉回路如終點(diǎn)不是起點(diǎn)，則等價(jià)于該圖僅存在歐拉通路如該圖不能一筆畫，則等價(jià)于該圖不存在歐拉通路和歐拉回路。15ABCDABDCBFCEHADG圖a不是一筆畫，它不是歐拉圖，也不存在歐拉通路；圖b能完成起點(diǎn)和終點(diǎn)不同的一筆畫，存在歐拉通路ACFEBCDGFH，但不存在歐拉回路，不是歐拉圖；圖c能完成起點(diǎn)與終點(diǎn)相同的的一筆畫，存在歐拉回路，它是歐拉圖。16歐拉圖(續(xù))例圖中,(1),(4)為歐拉圖;(2),(5)為歐拉通路;(3)，(6)既不是歐拉圖,也不是歐拉通路.在(3),(6)中各至少加幾條邊才能成為歐拉圖?17歐拉圖的判別法

定理無向圖G為歐拉圖當(dāng)且僅當(dāng)G連通且無奇度頂點(diǎn).無向圖G是歐拉通路當(dāng)且僅當(dāng)G連通且恰有兩個(gè)奇度頂點(diǎn).定理有向圖D是歐拉圖當(dāng)且僅當(dāng)D連通且每個(gè)頂點(diǎn)的入度都等于出度.有向圖D具有歐拉通路當(dāng)且僅當(dāng)D連通且恰有兩個(gè)奇度頂點(diǎn),其中一個(gè)入度比出度大1,另一個(gè)出度比入度大1,其余頂點(diǎn)的入度等于出度.18實(shí)例例1哥尼斯堡七橋問題例2下面兩個(gè)圖都是歐拉圖.從A點(diǎn)出發(fā),如何一次成功地走出一條歐拉回路來？19中國郵路問題：問題：一個(gè)郵遞員從郵局出發(fā),走遍所有街道,把郵件送到每個(gè)收件人手中,最后回到郵局,要怎樣走,使全程路線最短。轉(zhuǎn)化為圖論問題：以街道為邊,以街道交叉點(diǎn)為結(jié)點(diǎn),以街道的長度為邊上的權(quán),在權(quán)圖G=<v,E,W>上,找出一個(gè)經(jīng)過所有邊至少一次的回路,并使得該回路的權(quán)和達(dá)到最小。說明：該回路未必是Euler回路,邊允許重復(fù)。管梅谷提出了這個(gè)問題,并指出如果圖G有m條邊,則所求回路至少是m條邊,最多不超過2m條邊,并且每邊在回路中至多出現(xiàn)兩次。208.3哈密頓圖－點(diǎn)不重復(fù)哈密頓通路哈密頓回路哈密頓圖半哈密頓圖

21哈密頓周游世界問題

22哈密頓圖的定義哈密頓通路:經(jīng)過圖中所有頂點(diǎn)一次且僅一次的通路.哈密頓回路:經(jīng)過圖中所有頂點(diǎn)一次且僅一次的回路.哈密頓圖:具有哈密頓回路的圖.幾點(diǎn)說明：平凡圖是哈密頓圖.哈密頓通路是初級通路，哈密頓回路是初級回路.環(huán)與平行邊不影響圖的哈密頓性.23實(shí)例例圖中,(1),(2)是哈密頓圖;(3)是哈密頓通路.(4)既不是哈密頓圖,也不是哈密頓通路，為什么？24無向哈密頓圖的一個(gè)必要條件

定理

設(shè)無向圖G=<V,E>是哈密頓圖,則對于任意V1V且V1,均有p(GV1)|V1|.證設(shè)C為G中一條哈密頓回路,有p(CV1)|V1|.又因?yàn)镃G,故p(GV1)

p(CV1)|V1|.幾點(diǎn)說明定理中的條件是哈密頓圖的必要條件,但不是充分條件.可利用該定理判斷某些圖不是哈密頓圖.

由定理可知,二部圖Kr,s當(dāng)sr+1時(shí)不是哈密頓圖.當(dāng)r2時(shí),二部圖Kr,r是哈密頓圖,而二部圖Kr,r+1是哈密頓通路.25理解：滿足上述條件的土不一定是哈密頓圖如彼得森圖，去掉一個(gè)點(diǎn)，連通分支數(shù)不發(fā)生變化，仍然為1，滿足條件，但不是哈密頓圖；26實(shí)例例設(shè)G為n階無向連通簡單圖,若G中有割點(diǎn)或橋,則G不是哈密頓圖.證(1)設(shè)v為割點(diǎn),則p(Gv)2>|{v}|=1.根據(jù)定理,G不是哈密頓圖.

(2)若G是K2(K2有橋),它顯然不是哈密頓圖.除K2外,其他的有橋連通圖均有割點(diǎn).由(1),得證G不是哈密頓圖.27無向哈密頓圖的一個(gè)充分條件

定理

設(shè)G是n階(n3)無向簡單圖,若任意兩個(gè)不相鄰的頂點(diǎn)的度數(shù)之和大于等于n1,則G中存在哈密頓通路.當(dāng)n3時(shí),若任意兩個(gè)不相鄰的頂點(diǎn)的度數(shù)之和大于等于n,則G中存在哈密頓回路,從而G為哈密頓圖.28哈密頓通路(回路)的存在性(續(xù))定理中的條件是存在哈密頓通路(回路)的充分條件,但不是必要條件.例如,設(shè)G為長度為n1(n4)的路徑,它不滿足定理中哈密頓通路的條件,但它顯然存在哈密頓通路.設(shè)G是長為n的圈,它不滿足定理中哈密頓回路的條件,但它顯然是哈密頓圖.29由定理,當(dāng)n3時(shí),Kn均為哈密頓圖.判斷某圖是否為哈密頓圖至今還是一個(gè)難題定理8.8：設(shè)有向圖D=<V,E>,|V|=n2如果所有的有向邊均用無向邊代替,所得無向圖中含有生成子圖kn，則該有向圖中存在哈密爾頓通路。推論:|V|3的有向(無向)完全圖為哈密爾頓圖。30哈密頓圖與歐拉圖H＋EEH非H非E31判斷是否是哈密頓圖的可行方法觀察出一條哈密頓回路例如右圖(周游世界問題)中紅邊給出一條哈密頓回路,故它是哈密頓圖.注意,此圖不滿足定理的條件.滿足充分條件例如當(dāng)n3時(shí),Kn中任何兩個(gè)不同的頂點(diǎn)u,v,均有d(u)+d(v)=2(n1)

n,所以Kn為哈密頓圖.32判斷是否是哈密頓圖的可行方法(續(xù))例1/4國際象棋盤(44方格)上的跳馬問題:馬是否能恰好經(jīng)過每一個(gè)方格一次后回到原處?解每個(gè)方格看作一個(gè)頂點(diǎn),2個(gè)頂點(diǎn)之間有邊當(dāng)且僅當(dāng)馬可以從一個(gè)方格跳到另一個(gè)方格,得到16階圖G,如左圖紅邊所示.取V1={a,b,c,d},則p(GV1)=6>|V1|,見右圖.由定理,圖中無哈密頓回路,故問題無解.不滿足必要條件33應(yīng)用實(shí)例例某次國際會議8人參加，已知每人至少與其余7人中的4人有共同語言，問服務(wù)員能否將他們安排在同一張圓桌就座，使得每個(gè)人都能與兩邊的人交談？解圖是描述事物之間關(guān)系的最好的手段之一.作無向圖G=<V,E>,其中V={v|v為與會者}，E={(u,v)|u,vV,u與v有共同語言,且uv}.G為簡單圖.根據(jù)條件,vV,d(v)4.于是，u,vV,有d(u)+