電子科大圖論上課及復(fù)習(xí)總結(jié)楊春7

Email:yc517922@126.com

圖論及其應(yīng)用任課教師：楊春數(shù)學(xué)科學(xué)學(xué)院1第五章匹配與因子分解主要內(nèi)容一、偶圖的匹配問(wèn)題二、圖的因子分解三、匈牙利算法與最優(yōu)匹配算法教學(xué)時(shí)數(shù)安排6學(xué)時(shí)講授本章內(nèi)容2本次課主要內(nèi)容(一)、圖的匹配與貝爾熱定理(二)、偶圖的匹配與覆蓋(三)、托特定理偶圖的匹配問(wèn)題3

1、圖的匹配相關(guān)概念

(1)、匹配M---如果M是圖G的邊子集(不含環(huán)），且M中的任意兩條邊沒(méi)有共同頂點(diǎn)，則稱(chēng)M是G的一個(gè)匹配或?qū)蜻叒?dú)立集。(一)、圖的匹配與貝爾熱定理如果G中頂點(diǎn)v是G的匹配M中某條邊的端點(diǎn)，稱(chēng)它為M飽和點(diǎn)，否則為M非飽和點(diǎn)。v1

v7v6Gv8v2v3v5v4

M1=｛v6v7｝

M2=｛v6v7,v1v8｝

M3=｛v6v7,v1v8,v3v4｝

M1,M2,M3等都是G的匹配。4

(2)、最大匹配M---如果M是圖G的包含邊數(shù)最多的匹配，稱(chēng)M是G的一個(gè)最大匹配。特別是，若最大匹配飽和了G的所有頂點(diǎn)，稱(chēng)它為G的一個(gè)完美匹配。G的一個(gè)最大匹配G的一個(gè)完美匹配注：一個(gè)圖G不一定存在完美匹配。5

(3)、M交錯(cuò)路---如果M是圖G的匹配，G中一條由M中的邊和非M中的邊交錯(cuò)形成的路，稱(chēng)為G中的一條M交錯(cuò)路。特別地，若M交錯(cuò)路的起點(diǎn)與終點(diǎn)是M非飽和點(diǎn)，稱(chēng)這種M交錯(cuò)路為M可擴(kuò)路。在下圖中：v1

v7v6Gv8v2v3v5v4設(shè)M=｛v7v8,v3v4｝，則：路v6v7v8v3v4與v1v7v8v2都是M交錯(cuò)路。其中后者是M可擴(kuò)路。6

2、貝爾熱定理定理1(貝爾熱，1957)G的匹配M是最大匹配，當(dāng)且僅當(dāng)G不包含M可擴(kuò)路。證明：“必要性”若G包含一條M可擴(kuò)路P,則可令該可擴(kuò)路為：顯然，P中M中的邊比非M中的邊少一條。于是作新的匹配M1,它當(dāng)中的邊由P中非M中邊組成。M1中邊比M中多一條，這與M是G的最大匹配矛盾?！俺浞中浴比舨蝗唬O(shè)M1是G的一個(gè)最大匹配，則|M1|>|M|。7令H=M1ΔM。容易知道：G[H]的每個(gè)分支或者是由M1與M中邊交替組成的偶圈，或者是由M1與M中邊交替組成的路。在每個(gè)偶圈中，M1與M中邊數(shù)相等；但因|M1|>|M|，所以，至少有一條路P，其起點(diǎn)和終點(diǎn)都是M非飽和點(diǎn)，于是，它是G的一條M可擴(kuò)路。這與條件矛盾。注：貝爾熱定理給我們提供了擴(kuò)充G的匹配的思路。貝爾熱(1926---2002)法國(guó)著名數(shù)學(xué)家。他的《無(wú)限圖理論及其應(yīng)用》(1958)是繼哥尼之后的圖論歷史上的第二本圖論專(zhuān)著。他不僅在圖論領(lǐng)域做出了許多貢獻(xiàn)，而且四處奔波傳播圖論，推動(dòng)了圖論的普及和發(fā)展。

1993年，他獲得組合與圖論領(lǐng)域頒發(fā)的歐拉獎(jiǎng)?wù)隆?貝爾熱在博弈論、拓?fù)鋵W(xué)領(lǐng)域里也有杰出貢獻(xiàn)。在博弈領(lǐng)域，他引入了Nash均衡之外的另一種均衡系統(tǒng)。Nash的生活被改編成電影《美麗的心靈》，獲02年奧斯卡金像獎(jiǎng)。貝爾熱對(duì)中國(guó)的手工藝很感興趣。他也是一位象棋高手，還創(chuàng)作過(guò)小說(shuō)《誰(shuí)殺害了Densmore公爵》。(二)、偶圖的匹配與覆蓋在日常生活，工程技術(shù)中，常常遇到求偶圖的匹配問(wèn)題。下面看一個(gè)例子：

1、問(wèn)題的提出9有7名研究生A,B,C,D,E,F,G畢業(yè)尋找工作。就業(yè)處提供的公開(kāi)職位是：會(huì)計(jì)師(a),咨詢(xún)師(b),編輯(c),程序員(d),記者(e),秘書(shū)(f)和教師(g)。每名學(xué)生申請(qǐng)的職位如下：

A:b,c;B:a,b,d,f,g;C:b,e;D:b,c,e;

E:a,c,d,f;F:c,e;G:d,e,f,g;問(wèn)：學(xué)生能找到理想工作嗎？解：如果令X=｛A,B,C,D,E,F,G｝,Y=｛a,b,c,d,e,f,g｝,X中頂點(diǎn)與Y中頂點(diǎn)連線當(dāng)且僅當(dāng)學(xué)生申請(qǐng)了該工作。于是，得到反映學(xué)生和職位之間的狀態(tài)圖：10問(wèn)題轉(zhuǎn)化為求飽和X每個(gè)頂點(diǎn)的一個(gè)匹配！

A:b,c;B:a,b,d,f,g;C:b,e;D:b,c,e;

E:a,c,d,f;F:c,e;G:d,e,f,g;FEDCBAGabcdefg需要解決的問(wèn)題是:(1)匹配是否存在？(2)如何求出匹配？

2、偶圖匹配存在性判定----Hall定理11FEDCBAGabcdefg定理2(Hall定理）設(shè)G=(X,Y)是偶圖，則G存在飽和X每個(gè)頂點(diǎn)的匹配的充要條件是：例1，在下面偶圖中，是否存在飽和X=｛A,B,C,D,E,F,G｝的每個(gè)頂點(diǎn)的匹配？12FEDCBAGabcdefg解:(1)當(dāng)S取X中單元點(diǎn)時(shí)，容易驗(yàn)證：|N(S)|>|S|

(2)當(dāng)S取X中二元點(diǎn)集時(shí)，容易驗(yàn)證：|N(S)|≧|S|

(3)當(dāng)S取X中三元點(diǎn)集時(shí)，容易驗(yàn)證：|N(S)|≧|S|

(4)當(dāng)S取X中四元點(diǎn)集時(shí)，若取S=｛A,C,D,F｝,則有3=|N(S)|<|S|=4

所以，不存在飽和X每個(gè)頂點(diǎn)的匹配。

下面我們證明Hall定理。13

證明：“必要性”

如果G存在飽和X每個(gè)頂點(diǎn)的匹配，由匹配的定義，X的每個(gè)頂點(diǎn)在Y中至少有一個(gè)鄰接點(diǎn)，所以:

“充分性”

如果G是滿(mǎn)足條件(*)的偶圖,但是不存在飽和X每個(gè)頂點(diǎn)的匹配。

令M*是G的一個(gè)最大匹配，但是不飽和X的頂點(diǎn)u.u示意圖G14又令Z是通過(guò)M*與點(diǎn)u相連形成的所有M*交錯(cuò)路上的點(diǎn)集。因M*是最大匹配，所以u(píng)是所有交錯(cuò)路上唯一的一個(gè)未飽和點(diǎn)。令S=X∩Z,T=Z∩Y顯然，S-｛u｝中點(diǎn)與T中點(diǎn)在M*下配對(duì)，即：

|T|=|S|-1<|S|即：|N(S)|=|T|=|S|-1<|S|，與條件矛盾。uTS注:(1)G=(X,Y)存在飽和X每個(gè)頂點(diǎn)的匹配也常說(shuō)成存在由X到Y(jié)的匹配。15(2若)振Ha島ll定理襯也可旬表述撕為：茶設(shè)G=匙(X暖,Y鄰)是偶聰圖，俊如果稀存在X的一襪個(gè)子梅集S,使得|N棍(S隨)|優(yōu)<連|虧S|，那黨么G中不衫存在半由X到Y(jié)的匹閣配。(3獎(jiǎng))背Ha杜ll定理燈也稱(chēng)步為“瞧婚姻規(guī)定理覽”，驕表述姜如下穗：“婚歉姻定餅理”鋼：躺在一摘個(gè)由r個(gè)女并人和s個(gè)男雅人構(gòu)盈成的濁人群兇中，1≦r待≦s。在債熟識(shí)僅的男左女之誘間可猴能出籃現(xiàn)r對(duì)婚絨姻的均充分錢(qián)必要亮條件界是，抗對(duì)每忌個(gè)整毒數(shù)k(曉1≦升k≦振r)碎,任意k個(gè)女樸人共珍認(rèn)識(shí)礙至少k個(gè)男床人。(4局)宵Ha駝ll定理塑是在義偶圖豆中求美最大陵匹配濱算法害的理趣論基言礎(chǔ)，肌即匈刻牙利抗算法脊基礎(chǔ)壘。(5導(dǎo))偷Ha愛(ài)ll滔(趙19最04鋸--柄-1械98冷2)英國(guó)辛人，20世紀(jì)咽最偉搞大的槽數(shù)學(xué)嶄家之續(xù)一。蛛主要座功績(jī)泡是在為代數(shù)告學(xué)領(lǐng)鹽域。攏在劍項(xiàng)橋大宗學(xué)工深作期腐間，強(qiáng)主要朽研究添群論岸，19趕32年發(fā)窗表的磚關(guān)于洪素?cái)?shù)奏冪階梳群論摘文是甜他最游有名16的工蜂作。術(shù)匹配冬定理漆是他19枕35年在櫻劍橋情大學(xué)番做講憶師時(shí)論發(fā)表統(tǒng)的結(jié)未果。Ha漠ll是一羽名雅貿(mào)致的剖學(xué)者晝，對(duì)灶學(xué)生蠻特別辯友好毛，當(dāng)鋒他覺(jué)西得有男必要爪批評(píng)深學(xué)生司時(shí)，耀他都較會(huì)以惰一種爺十分眠溫和宵的方咱式建緊議他稈們改可正。推論捏：若G是k遲(k廉>0龍)正則脂偶圖浸，則G存在宵完美級(jí)匹配窄。證明捎：一愚方面格，由咽于G是k逼(k世>0紀(jì))正則娘偶圖,所以k|X|=k|裁Y|,于是制得|X晚|漠=帥|Y區(qū)|；另一殊方面斃，對(duì)妄于X的任臟一非庸空子捧集S,設(shè)E1與E2分別合是與S和N(滑S)關(guān)聯(lián)詠的邊摘集，圓顯然誰(shuí)有：驢即：由Ha嫌ll定理錫，存鎮(zhèn)在由X到Y(jié)的匹白配.又|X忠|亡=酷|Y搏|，所涉以G存在魄完美古匹配落。17例2普(1炊)證明暮：每研個(gè)k方體紀(jì)都有共完美除匹配(k大于昨等于2)(2稱(chēng))求K2n和Kn,暑n中不焦同的陜完美際匹配踐的個(gè)贈(zèng)數(shù)。(1毀)證明粗一：跑證明毀每個(gè)k方體西都是k正則躲偶圖劑。事實(shí)廣上，鹽由k方體滲的構(gòu)質(zhì)造：k方體賴(lài)有2k個(gè)頂撞點(diǎn)，寧每個(gè)言頂點(diǎn)朝可以宴用長(zhǎng)亦度為k的二通進(jìn)制愛(ài)碼來(lái)披表示亡，兩國(guó)個(gè)頂卵點(diǎn)連病線當(dāng)宗且僅父當(dāng)代于表兩指?jìng)€(gè)頂動(dòng)點(diǎn)的喪二進(jìn)賴(lài)制碼抄只有獄一位約坐標(biāo)脆不同拜。如果兇我們逐劃分k方體裝的2k個(gè)頂勉點(diǎn)，裙把坐縱標(biāo)之啦和為孝偶數(shù)杯的頂單點(diǎn)歸貸入X，否桿則歸典入Y。顯抬然，X中頂癥點(diǎn)互旨不鄰凍接，Y中頂量點(diǎn)也怠如此另。所圍以k方體傭是偶件圖。又不枕難知越道k方體孤的每秋個(gè)頂絡(luò)點(diǎn)度予數(shù)為k,所以k方體啄是k正則某偶圖聲。由推抹論：k方體貝存在闊完美延匹配否。18證明錦二：其直接趣在k方體甘中找醫(yī)出完形美匹例配。設(shè)k方體滾頂點(diǎn)紡二進(jìn)苦制碼稻為(x1,x2,…撓,xk),我們微取(x1,x2,…睡,xk-哈1,0痰),和(x1,x2,…雖,xk-沃1,1閥)之間緒的全蕉體邊湯所成陪之集渣為M.顯然券，M中的促邊均次不相從鄰接緒，所岡以作擦成k方體卵的匹愛(ài)配，憲又容杜易知祥道：|M沒(méi)|=毒2k-徐1.所以M是完朝美匹評(píng)配。(2股)我們甘用歸留納法顯求K2n和Kn,拍n中不判同的信完美泄匹配抖的個(gè)毅數(shù)。K2n的任冷意一級(jí)個(gè)頂晶點(diǎn)有2n登-1種不寫(xiě)同的鬧方法業(yè)被匹蛋配。唇所以K2n的不祖同完煮美匹承配個(gè)茂數(shù)等牌于(2宰n-但1)水K2n放-2,如此栽推下竊去，鋪可以梯歸納幸出K2n的不兼同完茅美匹首配個(gè)勿數(shù)為鑼?zhuān)?2叢n-賴(lài)1)威!!同樣繡的推召導(dǎo)方撥法可付歸納殺出Kn,斯n的不削同完比美匹兵配個(gè)戒數(shù)為亡：n!19例3證明倚樹(shù)至推多存姨在一異個(gè)完襲美匹詢(xún)配。證明才：若訪不然懶，設(shè)M1與M2是樹(shù)T的兩亞個(gè)不伶同的宅完美端匹配倡，那咐么M1ΔM2≠Φ,容易螺知道燒：T[M1ΔM2]每個(gè)驚非空吊部分溝頂點(diǎn)感度數(shù)蠢為2，即蹈它存鏟在圈釀，于址是推端出T中有煌圈，壟矛盾良。3、點(diǎn)侍覆蓋難與哥現(xiàn)尼定問(wèn)理(1臘)、圖沙的點(diǎn)消覆蓋在概念乳與性朱質(zhì)定義1：圖表的點(diǎn)頂覆蓋--拜-G的一良個(gè)頂全點(diǎn)子蝕集K稱(chēng)為G的一竟個(gè)點(diǎn)枯覆蓋響，如兔果G的每猶條邊疤都至訪少有戶(hù)一個(gè)雙端點(diǎn)究在K中。G的一覽個(gè)包芝含點(diǎn)謝數(shù)最起少的鐵點(diǎn)覆掩蓋稱(chēng)京為G的最直小點(diǎn)圖覆蓋它，其論包含僑的點(diǎn)引數(shù)稱(chēng)材為G的覆牧蓋數(shù)肥，記眼為α(G尤).(a)一個(gè)覆蓋(b)一個(gè)最小覆蓋20定理2設(shè)M是G的匹灶配，K是G的覆紛蓋，互若|M敵|=母|K閑|,則M是最冶大匹磚配，匆而G是最寒小覆煩蓋。證明滔：設(shè)M*與K*分別嫁是G的最驢大匹財(cái)配和府最小經(jīng)覆蓋殃。由匹塔配和于覆蓋爺定義紀(jì)有：|M*|≦|K*|。所徒以，歷有：|M達(dá)|≦|M*|≦|K*|≦|K千|所以們，當(dāng)|M望|=索|K玻|時(shí)，屋有|M漂|另=|皮M*霧|，|K扣*|厚=蠢|K沸|即M是最悔大匹火配，效而G是最廈小覆賢蓋。(2茅)、偶左圖的感點(diǎn)覆雕蓋與憶偶圖沸匹配擇間的稀關(guān)系--收--哥尼尸定理21定理2傘(哥尼藏，19榨31亞)在偶岸圖中錯(cuò)，最昂大匹被配的溫邊數(shù)悲等于宴最小喇覆蓋盜的頂隱點(diǎn)數(shù)伯。證明至：設(shè)G=超(X訪,瓜Y)獎(jiǎng),抽M昆*是偶獲圖G的最蔥大匹悉配。U表示X中M*非飽幣和點(diǎn)挎集。Z表示浪由M*交錯(cuò)濃路連芒到U的頂繳點(diǎn)的店所有組路上洲的點(diǎn)蘋(píng)作成構(gòu)的集孩合。此且令S=秧Z∩X燙,尼T=受Z∩虎Y。SUT=N(S)

X\S22由M*的最貞大性劃，T中點(diǎn)系是M*飽和蝴的，摘且N(園S)礦=T。SUT=N(S)

X\S現(xiàn)在溪，令K*治=撤(X精-S凈)∪T?？梢該屪C明秋：K*鳳=攏(X奮-S字)∪T是G的一朗個(gè)覆拿蓋。事實(shí)剃上，茂若K*疏=弄(X歸-S當(dāng))∪T不是G的一右個(gè)覆緒蓋。刑則存兆在G的一刃條邊,其一脫個(gè)端語(yǔ)點(diǎn)在S中，液而另交一個(gè)炕端點(diǎn)街在Y-紫T中，涉這與N(哈S)鏟=T矛盾棉！顯然|K*|段=殃|M咬*|。由卷定理2，K*是最皂小覆木蓋。23哥尼(K?ni沫g)—剪—第一導(dǎo)本圖茶論教幟材的裹撰寫(xiě)猾者到了19鋪36年，而第一沫本圖鋤論教截材才傅與讀邀者見(jiàn)或面。錄作者登是哥睡尼(1畜88夸4-芝--條-1矩94龍4)舅.哥尼容早期誓學(xué)習(xí)商拓?fù)溲蹖W(xué)，聲但對(duì)堪圖論脅興趣悠特別暈大。罰他一醋直工估作在寬布達(dá)材佩斯腸工業(yè)各大學(xué)窗。講批課很嗎有激呼情，跑吸引礎(chǔ)了很蔥多優(yōu)范秀學(xué)遣生轉(zhuǎn)煩向圖丹論研伐究。境特別瀉是，箭他把場(chǎng)一起搖獲得銳匈牙境利國(guó)猜家高群中數(shù)艱學(xué)競(jìng)濱賽一盆等獎(jiǎng)蘭的3個(gè)學(xué)哭生都其吸引裂來(lái)研鑒究圖退論，用這3個(gè)學(xué)如生是危：Er昨d?s,Ga雹ll資ai,Tu層ra稻n.都是獎(jiǎng)偉大烘的數(shù)抗學(xué)家瀉。哥尼蛇的著部作名括稱(chēng)是《有限笑圖與特?zé)o限差圖理熄論》。這洲本書(shū)旨對(duì)青誼年學(xué)香者產(chǎn)藝生了挖很大呆影響膠，推下動(dòng)了跟圖論側(cè)的進(jìn)懼一步頭發(fā)展遵。在20多年核時(shí)間帥里，械它都斷是世月界上毒唯一燭一本刷圖論青著作億。直慢到19厚58年，躲法國(guó)棋數(shù)學(xué)喉家貝氧爾熱(B認(rèn)er壁ge）才攜出版丑專(zhuān)著《無(wú)限澆圖理早論及鄰其應(yīng)櫻用》。哥尼19蔬44年為裙免遭掙納碎登迫害四，只豎有自堵殺。24例4矩陣挖的一暗行或安一列擺稱(chēng)為夏矩陣肥的一志條線籍。證主明：倒布爾腰矩陣酬中，潔包含會(huì)了所鋤有“1”的線肢的最未少數(shù)您目，扎等于組具有錫性質(zhì)詳“任千意兩愿?jìng)€(gè)1都不凳在同棍一條江線上軟的1的最討大數(shù)極目”柄。例如部：在示如下達(dá)布爾累矩陣翼中：證明悟：設(shè)仿布爾頂陣是n行m列矩議陣，羅把它粥模型優(yōu)為一火個(gè)偶僅圖如雞下：賭每行川每列攔分別擁用一碧個(gè)點(diǎn)絕表示砌，X表示吩行點(diǎn)矩集合招，Y表示兆列點(diǎn)平集合們，兩戀點(diǎn)連鹽線。籌當(dāng)且學(xué)僅當(dāng)容該行冒該列億元為1.25于是敬，包汪含了宅所有統(tǒng)