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

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

設(shè)無(wú)向圖G=<V,E>,若能將V分成V1和V2

使得V1V2=V,V1V2=,且G中的每條邊的兩個(gè)端點(diǎn)都一個(gè)屬于V1,另一個(gè)屬于V2,則稱(chēng)G為二部圖,記為<V1,V2,E>,稱(chēng)V1和V2為互補(bǔ)頂點(diǎn)子集.又若G是簡(jiǎn)單圖,且V1中每個(gè)頂點(diǎn)均與V2中每個(gè)頂點(diǎn)都相鄰,則稱(chēng)G為完全二部圖,記為Kr,s,其中r=|V1|,s=|V2|.K23K334二部圖的判別法

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

例下述各圖都是二部圖

5二部圖的判別定理定理8.1無(wú)向圖G=<V,E>是二部圖當(dāng)且僅當(dāng)G中無(wú)奇長(zhǎng)度的回路證必要性.設(shè)G=<V1,V2,E>是二部圖,每條邊只能從V1到V2,或從V2到V1,故任何回路必為偶長(zhǎng)度.充分性.不妨設(shè)G至少有一條邊且連通.取任一頂點(diǎn)u,令

V1={v|vVd(v,u)為偶數(shù)},V2={v|vVd(v,u)為奇數(shù)}則V1V2=V,V1V2=.先證V1中任意兩點(diǎn)不相鄰.假設(shè)存在s,tV1,e=(s,t)E.設(shè)1,2分別是u到s,t的短程線,則1e

2是一條回路,其長(zhǎng)度為奇數(shù),與假設(shè)矛盾.同理可證V2中任意兩點(diǎn)不相鄰.

6實(shí)例非二部圖非二部圖7匹配

設(shè)G=<V,E>,匹配(邊獨(dú)立集):任2條邊均不相鄰的邊子集極大匹配:添加任一條邊后都不再是匹配的匹配最大匹配:邊數(shù)最多的匹配匹配數(shù):最大匹配中的邊數(shù),記為1

例下述3個(gè)圖的匹配數(shù)依次為3,3,4.8匹配(續(xù))設(shè)M為G中一個(gè)匹配vi與vj被M匹配:(vi,vj)Mv為M飽和點(diǎn):M中有邊與v關(guān)聯(lián)v為M非飽和點(diǎn):M中沒(méi)有邊與v關(guān)聯(lián)M為完美匹配:G的每個(gè)頂點(diǎn)都是M飽和點(diǎn)例關(guān)于M1,a,b,e,d是飽和點(diǎn)

f,c是非飽和點(diǎn)

M1不是完美匹配

M2是完美匹配M1M29二部圖中的匹配

定義設(shè)G=<V1,V2,E>為二部圖,|V1||V2|,M是G中最大匹配,若V1中頂點(diǎn)全是M飽和點(diǎn),則稱(chēng)M為G中V1到V2的完備匹配.當(dāng)|V1|=|V2|時(shí),完備匹配變成完美匹配.(1)(2)(3)例圖中紅邊組成各圖的一個(gè)匹配，(1)為完備的,但不是完美的;(2)不是完備的,其實(shí)(2)中無(wú)完備匹配;(3)是完美的.10Hall定理

定理(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定理不難證明,上一頁(yè)圖(2)沒(méi)有完備匹配.定理設(shè)二部圖G=<V1,V2,E>中,如果存在t1,使得V1中每個(gè)頂點(diǎn)至少關(guān)聯(lián)t條邊,而V2中每個(gè)頂點(diǎn)至多關(guān)聯(lián)t條邊，則G中存在V1到V2的完備匹配.Hall定理中的條件稱(chēng)為“相異性條件”,第二個(gè)定理中的條件稱(chēng)為t條件.滿足t條件的二部圖一定滿足相異性條件.11實(shí)例例1

某中學(xué)有3個(gè)課外活動(dòng)小組:數(shù)學(xué)組,計(jì)算機(jī)組和生物組.有趙,錢(qián),孫,李,周5名學(xué)生,問(wèn)分別在下述3種情況下,能否選出3人各任一個(gè)組的組長(zhǎng)?(1)趙,錢(qián)為數(shù)學(xué)組成員,趙,孫,李為計(jì)算機(jī)組成員,孫,李,周為生物組成員.(2)趙為數(shù)學(xué)組成員,錢(qián),孫,李為計(jì)算機(jī)組成員,錢(qián),孫,李,周為生物組成員.(3)趙為數(shù)學(xué)組和計(jì)算機(jī)組成員,錢(qián),孫,李,周為生物組成員.12實(shí)例(續(xù))解(1),(2)有多種方案,(3)不可能(1)數(shù)計(jì)生趙錢(qián)孫李周(2)數(shù)計(jì)生趙錢(qián)孫李周(3)數(shù)計(jì)生趙錢(qián)孫李周13一個(gè)應(yīng)用實(shí)例例某課題組要從a,b,c,d,e5人中派3人分別到上海、廣州、香港去開(kāi)會(huì).已知a只想去上海，b只想去廣州，c,d,e都表示想去廣州或香港.問(wèn)該課題組在滿足個(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種派遣方案(請(qǐng)給出這9種方案).148.2歐拉圖歐拉通路歐拉回路歐拉圖半歐拉圖15哥尼斯堡七橋問(wèn)題

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

歐拉通路:圖中行遍所有頂點(diǎn)且恰好經(jīng)過(guò)每條邊一次的通路.歐拉回路:圖中行遍所有頂點(diǎn)且恰好經(jīng)過(guò)每條邊一次的回路.歐拉圖:有歐拉回路的圖.半歐拉圖:有歐拉通路而無(wú)歐拉回路的圖.幾點(diǎn)說(shuō)明：上述定義對(duì)無(wú)向圖和有向圖都適用.規(guī)定平凡圖為歐拉圖.歐拉通路是簡(jiǎn)單通路,歐拉回路是簡(jiǎn)單回路.環(huán)不影響圖的歐拉性.17歐拉圖(續(xù))例圖中,(1),(4)為歐拉圖;(2),(5)為半歐拉圖;(3)，(6)既不是歐拉圖,也不是半歐拉圖.

在(3),(6)中各至少加幾條邊才能成為歐拉圖?18歐拉圖的判別法

定理無(wú)向圖G為歐拉圖當(dāng)且僅當(dāng)G連通且無(wú)奇度頂點(diǎn).

無(wú)向圖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)的入度等于出度.19實(shí)例例1哥尼斯堡七橋問(wèn)題例2下面兩個(gè)圖都是歐拉圖.從A點(diǎn)出發(fā),如何一次成功地走出一條歐拉回路來(lái)？20實(shí)例無(wú)歐拉通路歐拉圖歐拉圖有歐拉通路非歐拉圖有歐拉通路非歐拉圖無(wú)歐拉通路21實(shí)例歐拉圖無(wú)歐拉通路無(wú)歐拉通路有歐拉通路無(wú)歐拉回路無(wú)歐拉通路有歐拉通路無(wú)歐拉回路228.3哈密頓圖哈密頓通路哈密頓回路哈密頓圖半哈密頓圖23哈密頓周游世界問(wèn)題

24哈密頓回路與哈密頓通路哈密頓通路:經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的通路.哈密頓回路:經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的回路.哈密頓圖:具有哈密頓回路的圖.半哈密頓圖:具有哈密頓通路而無(wú)哈密頓回路的圖.說(shuō)明：哈密頓通路是初級(jí)通路哈密頓回路是初級(jí)回路有哈密頓通路不一定有哈密頓回路環(huán)與平行邊不影響圖的哈密頓性25哈密頓圖的必要條件定理8.6若無(wú)向圖G=<V,E>是哈密頓圖,則對(duì)于V的任意非空真子集V1均有p(GV1)|V1|.證設(shè)C為G中一條哈密頓回路,有p(CV1)|V1|.又因?yàn)镃G,故p(GV1)

p(CV1)|V1|.例如當(dāng)r≠s時(shí),Kr,s不是哈密頓圖推論有割點(diǎn)的圖不是哈密頓圖26實(shí)例例2

證明下述各圖不是哈密頓圖:(a)(b)(c)(c)中存在哈密頓通路27實(shí)例例3

證明右圖不是哈密頓圖證假設(shè)存在一條哈密頓回路,a,f,g是2度頂點(diǎn),邊(a,c),(f,c)和(g,c)必在這條哈密頓回路上,從而點(diǎn)c出現(xiàn)3次,矛盾.abcdefg此外,該圖滿足定理6.10的條件,這表明此條件是必要、而不充分的.又,該圖有哈密頓通路.28存在哈密頓回路(通路)的充分條件定理8.7設(shè)G是n(n3)階無(wú)向簡(jiǎn)單圖,若任意兩個(gè)不相鄰的頂點(diǎn)的度數(shù)之和大于等于n1,則G中存在哈密頓通路;若任意兩個(gè)不相鄰的頂點(diǎn)的度數(shù)之和大于等于n,則G中存在哈密頓回路,即G為哈密頓圖.推論設(shè)G是n(n3)階無(wú)向簡(jiǎn)單圖,若δ(G)n/2,則G是哈密頓圖當(dāng)n3時(shí),Kn是哈密頓圖;當(dāng)r=s2時(shí),Kr,s是哈密頓圖.定理8.8設(shè)D是n(n2)階有向圖,若略去所有邊的方向后所得無(wú)向圖中含子圖Kn,則D中有哈密頓通路.29應(yīng)用例4

有7個(gè)人,A會(huì)講英