




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、1二部圖二部圖一、二部圖一、二部圖定義定義1:若無向圖:若無向圖G的頂點集合的頂點集合V可以劃分成兩個子集可以劃分成兩個子集X 和和Y,使,使G中的每一條邊中的每一條邊e的一個端點在的一個端點在X中,另一個端點中,另一個端點 在在Y中,則稱中,則稱G為為二部圖二部圖或或偶圖偶圖。二部圖可記為。二部圖可記為 G,X和和Y稱為稱為互補結點子集互補結點子集。 二部圖不會有自回路。二部圖不會有自回路。定義定義2: 二部圖二部圖G中,若中,若X的每一頂點都與的每一頂點都與Y的每一的每一頂點鄰接,則稱頂點鄰接,則稱G為為完全二部圖完全二部圖, 記為記為Km,n,這里,這里m=|X|, n=|Y|。K2,4
2、K3,32一、二部圖一、二部圖定理定理1:無向圖:無向圖G為二部圖的充要條件為為二部圖的充要條件為G中所有中所有 回路的長度均為偶數(shù)。回路的長度均為偶數(shù)。證明:必要性證明:必要性:設設G是具有互補結點子集是具有互補結點子集X和和Y的二部圖,的二部圖,C是是G中任中任一回路,一回路,C:(v0,v1,v2,vk,v0)。 不妨設設不妨設設v0X,則,則v0,v2,v4,X,v1,v3,v5,Y,k必必為奇數(shù),否則,不存在邊為奇數(shù),否則,不存在邊(vk,v0)。于是由。于是由C中共有中共有k1條條邊,故邊,故C是偶數(shù)長度的回路。是偶數(shù)長度的回路。3 證明:充分性證明:充分性設設G是連通圖,否則對是
3、連通圖,否則對G的每個連通分圖進行證明。設的每個連通分圖進行證明。設 G=只含有偶數(shù)長度的回路,定義互補結點子集只含有偶數(shù)長度的回路,定義互補結點子集X和和Y如如 下:任取一個頂點下:任取一個頂點v0,v0V, 取取Xx|x V且且d(v0,x)=偶數(shù)偶數(shù),YVX。 Y y| y V且且d(v0,y)=奇數(shù)奇數(shù) 反證:假設存在一條邊反證:假設存在一條邊(vi,vj), vi,vjY。由于圖是連通。由于圖是連通 的,所以從的,所以從v0到到vi有一條最短路徑,其長度為奇數(shù);同理,有一條最短路徑,其長度為奇數(shù);同理, 從從v0到到vj有一條長度為奇數(shù)的最短路徑。于是由有一條長度為奇數(shù)的最短路徑。于
4、是由(vi,vj)及以及以 上兩條最短路徑構成的回路長度為奇數(shù),這與題設矛盾。則上兩條最短路徑構成的回路長度為奇數(shù),這與題設矛盾。則Y 的任兩結點間不存在邊。同理可證的任兩結點間不存在邊。同理可證X的任兩結點間不存在邊。的任兩結點間不存在邊。 所以所以G是二部圖。是二部圖。一、二部圖一、二部圖4二、匹配二、匹配定義定義3:給定一個二部圖:給定一個二部圖G,如果,如果E的子集的子集M中的邊中的邊無公共端點,則稱無公共端點,則稱M為二部圖為二部圖G的一個的一個匹配匹配。含有最多邊數(shù)。含有最多邊數(shù)的匹配稱為的匹配稱為G的的最大匹配最大匹配。若。若G中的一個頂點中的一個頂點v與與M中一條邊中一條邊關聯(lián)
5、,則稱關聯(lián),則稱v是關于是關于M的的飽和點飽和點,否則稱,否則稱v為關于為關于M的的非飽和非飽和點點。x1x2x3x4y1y2y3y4y5XY例:上圖中,例:上圖中,M(x1,y5),(x3,y1),(x4,y3)是是G的一個匹配。的一個匹配。5定義定義4:如果二部圖:如果二部圖G中的一條鏈由不屬于匹配中的一條鏈由不屬于匹配M的邊和屬于的邊和屬于M的的 邊交替組成,且鏈的兩端點不是邊交替組成,且鏈的兩端點不是M中的邊的端點,那么稱此鏈為中的邊的端點,那么稱此鏈為G中關于匹配中關于匹配M的的交替鏈交替鏈,首尾相接的交替鏈稱為,首尾相接的交替鏈稱為交替回路交替回路;若;若交替鏈的起點和終點都是非飽
6、和點,則該路徑稱為交替鏈的起點和終點都是非飽和點,則該路徑稱為M的的可增廣可增廣交替鏈交替鏈。最短的最短的交替鏈交替鏈是由一條邊組成,該邊的兩端點不是是由一條邊組成,該邊的兩端點不是M中邊的端點。中邊的端點。x1x2x3x4y1y2y3y4y5XY例:上圖中例:上圖中(x2,y1,x3,y4)是是交替鏈交替鏈。三、最大匹配三、最大匹配6三、最大匹配三、最大匹配 交替鏈可用標記法求出,過程如下:交替鏈可用標記法求出,過程如下:首先把首先把X中所有中所有不是不是M的邊的端點的邊的端點用用(*)加以標記,然后加以標記,然后交替交替進行以進行以下所述的過程下所述的過程I)和和II)。I) 選一個選一個
7、X的新標記過的結點,例如的新標記過的結點,例如xi,用,用(xi)標記標記不通過不通過M中的邊中的邊與與xi鄰接且鄰接且未標記過未標記過的的Y的所有結點。對所有的所有結點。對所有X的新標記過的結點重復的新標記過的結點重復這一過程;這一過程;II) 選一個選一個Y的新標記過的結點,例如的新標記過的結點,例如yi,用,用(yi)標記標記通過通過M中的邊中的邊與與yi鄰接且鄰接且未標記過未標記過的的X的所有結點。對所有的所有結點。對所有Y的新標記過的結點重復這的新標記過的結點重復這一過程;一過程;直至標記到直至標記到一個一個Y的不與的不與M中任何邊鄰接的結點中任何邊鄰接的結點,或者已,或者已不可能標
8、不可能標記更多結點記更多結點時為止。出現(xiàn)前一情況,說明已找到了一條可增廣交替鏈時為止。出現(xiàn)前一情況,說明已找到了一條可增廣交替鏈(逆著標記次序,返回到標記著逆著標記次序,返回到標記著(*)的結點,所經(jīng)過的路徑就是所求的結點,所經(jīng)過的路徑就是所求)。出現(xiàn)后一情況,說明出現(xiàn)后一情況,說明G中不存在關于中不存在關于M的交替鏈。的交替鏈。7n下圖中,標記過程如下:下圖中,標記過程如下:把把x2標記為標記為(*);從從x2出發(fā),應用過程出發(fā),應用過程I,把,把y1和和y3標記為標記為(x2);從從y1出發(fā),應用過程出發(fā),應用過程II,把,把x3標記為標記為(y1),從,從y3出發(fā),應出發(fā),應 用過程用過
9、程II,把,把x4標記為標記為(y3);從從x3出發(fā),應用過程出發(fā),應用過程I,把,把y4標記為標記為(x3),因為,因為y4不是不是M中中 邊的端點,說明已找到了一條可增廣交替鏈邊的端點,說明已找到了一條可增廣交替鏈P,即,即(x2,y1,x3,y4)。(y1)(y3)(*)(x2)(x2)(x3)x1x2x3x4y1y2y3y4y5XY三、最大匹配三、最大匹配8n在二部圖在二部圖G中,如果能找出一條關于匹配中,如果能找出一條關于匹配M的交替鏈的交替鏈L,則把,則把L中屬于中屬于M的邊從的邊從M中刪去,而把中刪去,而把L中不屬于中不屬于M的邊添到的邊添到M中,中,得到一個新集合得到一個新集合
10、M,此,此M也是也是G的匹配。因為添入的邊自身的匹配。因為添入的邊自身不相交,又不與不相交,又不與M中不屬于中不屬于L的邊相交。的邊相交。x1x2x3x4y1y2y3y4y5XYn前面圖變換后,得到的前面圖變換后,得到的M如上圖所示,比如上圖所示,比M多了一條邊。于多了一條邊。于 是,反復進行這樣的過程,直至找不出關于是,反復進行這樣的過程,直至找不出關于M的交替鏈為止,的交替鏈為止, 即可求出即可求出G的最大匹配。的最大匹配。三、最大匹配三、最大匹配9 對于已知匹配:對于已知匹配: M(x1,y5),(x3,y1),(x4,y3)。 設上面找到的一條交替鏈設上面找到的一條交替鏈P:(x2,y
11、1,x3,y4)可表示為可表示為 E(P)=( x2,y1),(y1,x3),(x3,y4), 則更大的匹配為則更大的匹配為 M E(P)=(x1,y5),( x2,y1),(x3,y4),(x4,y3)三、最大匹配三、最大匹配x1x2x3x4y1y2y3y4y5XY定理定理2: 無向圖無向圖G為二部圖,為二部圖,M為為G的最大匹配的的最大匹配的 充要條件是充要條件是G中不存在關于中不存在關于M的可增廣的交替鏈。的可增廣的交替鏈。10n例:求圖示二部圖的最大匹配。例:求圖示二部圖的最大匹配。1、置、置M為為,M ;2、找出一條邊的可增廣交替鏈、找出一條邊的可增廣交替鏈(x2,y2),M(x2,
12、y2);3、找出一條邊的可增廣交替鏈、找出一條邊的可增廣交替鏈(x3,y3),M(x2,y2),(x3,y3);4、找出一條邊的可增廣交替鏈、找出一條邊的可增廣交替鏈(x4,y4),M(x2,y2),(x3,y3),(x4,y4);5、用標記法找出一條可增廣交替鏈、用標記法找出一條可增廣交替鏈(x1,y3,x3,y2,x2,y1),進行變,進行變換得換得M=(x1,y3),(x2,y1),(x3,y2),(x4,y4);x1x2x3x4x5x6y1y2y3y4y5y6三、最大匹配三、最大匹配116、再用標記法找可增廣交替鏈,但已找不到。所以、再用標記法找可增廣交替鏈,但已找不到。所以M=(x1
13、,y3),(x3,y2),(x2,y1),(x4,y4)就是所求的最大匹配。就是所求的最大匹配。x1x2x3x4x5x6y1y2y3y4y5y6三、最大匹配三、最大匹配12例:在某電視臺的姻緣速配節(jié)目中,有例:在某電視臺的姻緣速配節(jié)目中,有6個女青年個女青年L1,L2,L3,L4,L5,L6,6個男青年個男青年G1,G2,G3,G4,G5,G6,經(jīng)過,經(jīng)過相互了解后,每人心中都有一個表,只愿意和表中的人交相互了解后,每人心中都有一個表,只愿意和表中的人交朋友,現(xiàn)在知道女青年的表分別為:朋友,現(xiàn)在知道女青年的表分別為:L1:G1,G2,G4;L2:G3,G5;L3:G1,G2,G4;L4:G2,G5,G6;L5:G3,G6;L6:G2,G5,G6;男青年的表分別為:男青年的表分別為:G1:L1,L3,L6;G2:L2,L4,L6;G3:L2,L5;G4:L1,L3;G5:L2,L6;G6:L3,L4,L5;請問如何匹配,使得男女雙方都滿意且速配的對數(shù)最多。請問如何匹配,使得男女雙方都滿意且速配的對數(shù)最多。三、最大匹配三、最大匹配13解:令解:令XL1,L2,L3,L4,L5,L6,YG1
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 泵類銷售員崗位面試問題及答案
- 保安隊長崗位面試問題及答案
- 自動化測試工程師崗位面試問題及答案
- 游戲數(shù)值策劃師崗位面試問題及答案
- 浙江省麗水市四校聯(lián)考2025屆高二下化學期末達標檢測試題含解析
- 安徽師范大學附中2025屆高二下化學期末達標檢測試題含解析
- 2025屆山西省同煤一中聯(lián)盟校高一下化學期末聯(lián)考試題含解析
- 2025屆浙江寧波市北侖區(qū)高二化學第二學期期末達標檢測模擬試題含解析
- 公用澡堂制度管理辦法
- 幼兒園戶外活動管理:現(xiàn)狀與對策探討
- 專題:閱讀理解 30篇 中考英語高分提升之新題速遞第二輯【含答案+解析】
- 企業(yè)面試題目和答案大全
- 抖音房產(chǎn)直播課件
- 2025至2030中國近視眼治療儀市場競爭力剖析及企業(yè)經(jīng)營形勢分析報告
- 2025年高考化學試卷(廣東卷)(空白卷)
- 體育老師招聘試題及答案
- 自然生態(tài)探險之旅行業(yè)跨境出海項目商業(yè)計劃書
- 2025年北京市高考英語試卷真題(含答案解析)
- 西藏自治區(qū)拉薩市達孜區(qū)孜縣2025年七下英語期中質量檢測模擬試題含答案
- 遼寧省沈陽市2023?2024學年高二下冊期末考試數(shù)學試卷2附解析
- 廚師三級考試試題及答案
評論
0/150
提交評論