離散數(shù)學(xué)一些特殊的圖

1、離散數(shù)學(xué)一些特殊的圖1第第8章章 一些特殊的圖一些特殊的圖 8.1 二部圖二部圖8.2 8.3 8.4 離散數(shù)學(xué)一些特殊的圖28.1 二部圖二部圖 二部圖二部圖完全二部圖完全二部圖匹配匹配極大匹配極大匹配最大匹配最大匹配匹配數(shù)匹配數(shù)完備匹配完備匹配 離散數(shù)學(xué)一些特殊的圖3二部圖二部圖 定義定義 設(shè)無向圖設(shè)無向圖 G=, 若能將若能將V 分成分成V1 和和 V2 (V1 V2=V, V1 V2=), 使得使得G中的每條邊的兩個(gè)端中的每條邊的兩個(gè)端點(diǎn)都一個(gè)屬于點(diǎn)都一個(gè)屬于V1, 另一個(gè)屬于另一個(gè)屬于V2, 則稱則稱G為二部圖為二部圖(二分圖二分圖), 記為記為, 稱稱V1和和V2為互補(bǔ)頂點(diǎn)子集為互

2、補(bǔ)頂點(diǎn)子集. 又若又若G是簡(jiǎn)單圖是簡(jiǎn)單圖, 且且V1中每個(gè)頂點(diǎn)均與中每個(gè)頂點(diǎn)均與V2中每個(gè)頂點(diǎn)都相中每個(gè)頂點(diǎn)都相鄰鄰, 則稱則稱G為完全二部圖為完全二部圖, 記為記為Kr,s, 其中其中r=|V1|, s=|V2|. (a)(b)以上兩個(gè)圖都是二部圖，其中以上兩個(gè)圖都是二部圖，其中(b)圖是完全二部圖。圖是完全二部圖。離散數(shù)學(xué)一些特殊的圖4例例 完全二分圖完全二分圖Km, n=(V1,V2,E)共有共有 多少條邊多少條邊?解解 因?yàn)橐驗(yàn)閂1中每個(gè)頂點(diǎn)都與中每個(gè)頂點(diǎn)都與V2 中每個(gè)頂點(diǎn)相鄰接中每個(gè)頂點(diǎn)相鄰接,所以所以V1 中每個(gè)頂點(diǎn)關(guān)聯(lián)中每個(gè)頂點(diǎn)關(guān)聯(lián) |V2| = n 條邊條邊; 而而V1 中有

3、中有m個(gè)頂點(diǎn)個(gè)頂點(diǎn), 所以所以Km, n共有共有mn條邊。條邊。離散數(shù)學(xué)一些特殊的圖5二部圖的判別法二部圖的判別法 定理定理 無向圖無向圖G=是二部圖當(dāng)且僅當(dāng)是二部圖當(dāng)且僅當(dāng)G中中 無奇圈無奇圈 。即。即G中的每一條回路都是由偶中的每一條回路都是由偶 數(shù)條邊組成。數(shù)條邊組成。證明：當(dāng)證明：當(dāng)G(V1,V2)是二部圖時(shí)，是二部圖時(shí)，G中的任中的任意一條回路的各邊必須往返于意一條回路的各邊必須往返于V1,V2之間，之間，因此其回路必由偶數(shù)條邊組成。因此其回路必由偶數(shù)條邊組成。離散數(shù)學(xué)一些特殊的圖6例：判斷下圖是否為二部圖。例：判斷下圖是否為二部圖。解：圖中的每一條回路都是由偶數(shù)條邊組成。解：圖中的

4、每一條回路都是由偶數(shù)條邊組成。所以此圖為二部圖。所以此圖為二部圖。離散數(shù)學(xué)一些特殊的圖7匹配匹配 設(shè)設(shè)G = (V, E)是具有互補(bǔ)頂點(diǎn)子集是具有互補(bǔ)頂點(diǎn)子集V1和和V2的二的二分圖分圖, M E, 若若M中任意兩條邊都不相鄰中任意兩條邊都不相鄰, 則稱則稱M為為G中的匹配中的匹配(對(duì)集對(duì)集)。l如果如果M是是G的匹配的匹配, 且且M中再加入任何一條邊就中再加入任何一條邊就都是不匹配了都是不匹配了, 則稱則稱M為極大匹配。為極大匹配。最大匹配最大匹配: 邊數(shù)最多的匹配邊數(shù)最多的匹配匹配數(shù)匹配數(shù): 最大匹配中的邊數(shù)最大匹配中的邊數(shù), 記為記為 1。離散數(shù)學(xué)一些特殊的圖8如在下圖中，如果用如在下圖

5、中，如果用a1,a2,a3,a4表示表示4位教師，位教師，b1,b2,b3表示三門待開的課程。當(dāng)某位教師能開某門表示三門待開的課程。當(dāng)某位教師能開某門課程時(shí)，則把它們的對(duì)應(yīng)頂點(diǎn)用邊連接起來。如果課程時(shí)，則把它們的對(duì)應(yīng)頂點(diǎn)用邊連接起來。如果規(guī)定一個(gè)教師只能擔(dān)任一門課程，那么匹配規(guī)定一個(gè)教師只能擔(dān)任一門課程，那么匹配M就表就表示了一種排課方案。為了使排課方案能最大限度地示了一種排課方案。為了使排課方案能最大限度地作到作到“各盡其能各盡其能”，這就是最大匹配的概念。，這就是最大匹配的概念。 離散數(shù)學(xué)一些特殊的圖9匹配匹配 (續(xù)續(xù))設(shè)設(shè)M為為G中一個(gè)匹配中一個(gè)匹配ai與與bj被被M匹配匹配: (ai,

6、bj) Mai為為M飽和點(diǎn)飽和點(diǎn): M中有邊與中有邊與ai關(guān)聯(lián)關(guān)聯(lián)ai為為M非飽和點(diǎn)非飽和點(diǎn): M中沒有邊與中沒有邊與ai關(guān)聯(lián)關(guān)聯(lián)M為完美匹配為完美匹配: G的每個(gè)頂點(diǎn)都是的每個(gè)頂點(diǎn)都是M飽和點(diǎn)飽和點(diǎn) 離散數(shù)學(xué)一些特殊的圖10定義定義 設(shè)設(shè)G=為二部圖為二部圖, |V1| |V2|, M是是G中最中最大匹配大匹配, 若若V1中頂點(diǎn)全是中頂點(diǎn)全是M飽和點(diǎn)飽和點(diǎn), 則稱則稱M為為G中中V1到到V2的完備匹配的完備匹配. 當(dāng)當(dāng)|V1|=|V2|時(shí)時(shí), 完備匹配變成完美完備匹配變成完美匹配匹配.(1)(2)(3) 圖中紅邊組成各圖的一個(gè)匹配，圖中紅邊組成各圖的一個(gè)匹配，(1)為完備的為完備的, 但不是

7、完但不是完美的美的; (2)不是完備的不是完備的, 其實(shí)其實(shí)(2)中無完備匹配中無完備匹配; (3) 是完美的是完美的.匹配匹配 (續(xù)續(xù))例：如圖例：如圖離散數(shù)學(xué)一些特殊的圖11M1M2例例 求下圖的飽和點(diǎn)，并判斷哪個(gè)圖是求下圖的飽和點(diǎn)，并判斷哪個(gè)圖是完美匹配？完美匹配？ 解：關(guān)于解：關(guān)于M1, a,b,e,d是飽和點(diǎn)是飽和點(diǎn)f,c是非飽和點(diǎn)是非飽和點(diǎn) M1不是完美匹配不是完美匹配 M2是完美匹配，所以是完美匹配，所以M2中中 a,b,c,d,e,f都是飽和點(diǎn)都是飽和點(diǎn)。離散數(shù)學(xué)一些特殊的圖12 設(shè)設(shè)G= V1,V2,E 是二部圖，是二部圖，M是是G的一個(gè)匹配，的一個(gè)匹配，如果對(duì)如果對(duì)G的任意

8、匹配的任意匹配M，都有，都有|M|M|，則，則M為為G的最大匹配的最大匹配 為了尋求二部圖的最大匹配，以下引進(jìn)交替通為了尋求二部圖的最大匹配，以下引進(jìn)交替通路和增長(zhǎng)通路兩個(gè)概念。路和增長(zhǎng)通路兩個(gè)概念。 定義定義 設(shè)設(shè)G= V1,V2,E 是二部圖，是二部圖，M是是G的匹配，的匹配，P是是G中的一條路，如果中的一條路，如果P是由是由G中屬于中屬于M的邊和的邊和不屬于不屬于M的邊交替組成，則稱的邊交替組成，則稱P為為G的的M交替通路。交替通路。如果交替通路的始點(diǎn)和終點(diǎn)都是如果交替通路的始點(diǎn)和終點(diǎn)都是M的非飽和點(diǎn)，的非飽和點(diǎn)，則稱為則稱為G的的M增長(zhǎng)通路。增長(zhǎng)通路。離散數(shù)學(xué)一些特殊的圖13 例如，在

9、圖中匹配例如，在圖中匹配M=(a1,b2), (a2,b3), (a3,b5)， 路路 L1：a1b2a2b3a3， L2：a2b3a3b5a4， L3：b1a3b5a4， L4：b1a1b2a2b3a3b5a4 都是都是M的交替通路，其中后兩條交替通路的交替通路，其中后兩條交替通路L3和和L4的的始點(diǎn)和終點(diǎn)都是始點(diǎn)和終點(diǎn)都是M的非飽和點(diǎn)，所以這兩條路是的非飽和點(diǎn)，所以這兩條路是M增增長(zhǎng)通路。長(zhǎng)通路。離散數(shù)學(xué)一些特殊的圖14 設(shè)設(shè)G= V1,V2,E 是二部圖，是二部圖，M是是G的一個(gè)匹配，的一個(gè)匹配，P是是G中的一條中的一條M增長(zhǎng)通路。把增長(zhǎng)通路。把P中所有屬于中所有屬于M的邊的邊從從M中去

10、掉，而把中去掉，而把P中所有不屬于中所有不屬于M的邊添加到的邊添加到M中，得到一個(gè)新的邊集中，得到一個(gè)新的邊集M，則，則M也是一個(gè)匹配，也是一個(gè)匹配，其所含邊數(shù)比匹配其所含邊數(shù)比匹配M所含的邊數(shù)多所含的邊數(shù)多1。離散數(shù)學(xué)一些特殊的圖15 例如在圖中，把例如在圖中，把M增長(zhǎng)通路增長(zhǎng)通路L3：b1a3b5a4中屬于中屬于M的邊的邊(a3,b5) 從從M中去掉，而把中去掉，而把L3中不屬于中不屬于M的邊的邊(a3,b1)和和(a4,b5) 添加到添加到M中，得到一個(gè)新的邊集中，得到一個(gè)新的邊集M= (a1,b2),(a2,b3),(a3,b1), (a4,b5) ，顯然，顯然M也是匹也是匹配且配且M

11、的邊數(shù)比的邊數(shù)比M的邊數(shù)多的邊數(shù)多l(xiāng)，即，即|M|M|+1。離散數(shù)學(xué)一些特殊的圖16 由此可見，利用增長(zhǎng)通路可以增加匹配所含的邊數(shù)。由此可見，利用增長(zhǎng)通路可以增加匹配所含的邊數(shù)。不斷地尋求不斷地尋求G的增長(zhǎng)通路，直到再也找不到新的增長(zhǎng)通的增長(zhǎng)通路，直到再也找不到新的增長(zhǎng)通路，就可得到一個(gè)最大匹配。將這個(gè)結(jié)論寫成下列的定路，就可得到一個(gè)最大匹配。將這個(gè)結(jié)論寫成下列的定理。理。 定理定理 設(shè)設(shè)G= V1,V2,E 是二部圖，是二部圖，M為為G的最大匹配的的最大匹配的充分必要條件是充分必要條件是G中不存在中不存在M增長(zhǎng)通路。增長(zhǎng)通路。 證明：設(shè)證明：設(shè)M為為G的最大匹配，下證的最大匹配，下證G中不存

12、在中不存在M可擴(kuò)路?？蓴U(kuò)路。 如果如果G中存在一條中存在一條M可擴(kuò)路，則可以得到比可擴(kuò)路，則可以得到比M的邊數(shù)的邊數(shù)多多1的匹配，所以的匹配，所以M不是最大匹配，矛盾。所以不是最大匹配，矛盾。所以G中不中不存在存在M可擴(kuò)路。可擴(kuò)路。 設(shè)設(shè)G中不存在中不存在M可擴(kuò)路，下證可擴(kuò)路，下證M為為G的最大匹配。的最大匹配。 設(shè)設(shè)M1是最大匹配，證明是最大匹配，證明|M|=|M1|。 考察屬于考察屬于M而不屬于而不屬于M1和屬于和屬于M1而不屬于而不屬于M中的邊，中的邊，由這些邊連同它們的端點(diǎn)一起構(gòu)成由這些邊連同它們的端點(diǎn)一起構(gòu)成G的子圖的子圖H。離散數(shù)學(xué)一些特殊的圖17 在子圖在子圖H中，任一頂點(diǎn)至多與

13、中，任一頂點(diǎn)至多與M中的一條邊關(guān)中的一條邊關(guān)聯(lián)且與聯(lián)且與M1中一條邊關(guān)聯(lián)。因而任一頂點(diǎn)的度數(shù)是中一條邊關(guān)聯(lián)。因而任一頂點(diǎn)的度數(shù)是1或或2。故。故H的連通分支是一條路，或者是一個(gè)回路。的連通分支是一條路，或者是一個(gè)回路。 如果如果H的連通分支是一條路的連通分支是一條路P，則它是，則它是M交替路，交替路，也是也是M1交替路。如果交替路。如果P的兩個(gè)端點(diǎn)均與的兩個(gè)端點(diǎn)均與M中的邊關(guān)中的邊關(guān)聯(lián)，則聯(lián)，則P是是M1可擴(kuò)路。由假設(shè)知，可擴(kuò)路。由假設(shè)知，M1是最大匹配，是最大匹配，所以，不存在所以，不存在M1可擴(kuò)路，得到矛盾。如果可擴(kuò)路，得到矛盾。如果P的兩個(gè)的兩個(gè)端點(diǎn)均與端點(diǎn)均與M1的邊關(guān)聯(lián)，那么的邊關(guān)聯(lián)

14、，那么P是一條是一條M可擴(kuò)路與題可擴(kuò)路與題設(shè)矛盾。故設(shè)矛盾。故P只能是一個(gè)端點(diǎn)與只能是一個(gè)端點(diǎn)與M中的邊關(guān)聯(lián)，另中的邊關(guān)聯(lián)，另一個(gè)端點(diǎn)與一個(gè)端點(diǎn)與M1中的邊關(guān)聯(lián)，這樣中的邊關(guān)聯(lián)，這樣P中屬于中屬于M的邊數(shù)的邊數(shù)與屬于與屬于M1的邊數(shù)相等。的邊數(shù)相等。 離散數(shù)學(xué)一些特殊的圖18 如果如果H的連通分支是一個(gè)回路，回路中的的連通分支是一個(gè)回路，回路中的邊交替地屬于邊交替地屬于M和和M1，因而屬于，因而屬于M的邊數(shù)與的邊數(shù)與屬于屬于M1的邊數(shù)相等。的邊數(shù)相等。 從上面可以看到，從上面可以看到，H中屬于中屬于M的邊與屬的邊與屬于于M1的邊的數(shù)目相等。再加上既屬于的邊的數(shù)目相等。再加上既屬于M又屬又屬于于

15、M1的邊，可以得出：的邊，可以得出：M中的邊數(shù)與中的邊數(shù)與M1中的中的邊數(shù)相等。所以邊數(shù)相等。所以M是最大匹配。是最大匹配。離散數(shù)學(xué)一些特殊的圖19 有了上面的準(zhǔn)備以后，就可以進(jìn)一步討有了上面的準(zhǔn)備以后，就可以進(jìn)一步討論如何在二部圖中求最大匹配的問題。論如何在二部圖中求最大匹配的問題。 設(shè)設(shè)G= V1,V2,E 是二部圖，通常先作是二部圖，通常先作G的的一個(gè)匹配一個(gè)匹配M，再看，再看V1中有沒有中有沒有M的非飽和點(diǎn)。的非飽和點(diǎn)。如果沒有，那么如果沒有，那么M肯定是最大匹配；如果有，肯定是最大匹配；如果有，就從這些點(diǎn)出發(fā)找就從這些點(diǎn)出發(fā)找M增長(zhǎng)通路。由增長(zhǎng)通路。由M增長(zhǎng)通增長(zhǎng)通路作出一個(gè)更大的匹

16、配。所以，在路作出一個(gè)更大的匹配。所以，在G中求最中求最大匹配的關(guān)鍵是尋找大匹配的關(guān)鍵是尋找M增長(zhǎng)通路。增長(zhǎng)通路。 離散數(shù)學(xué)一些特殊的圖20尋找增長(zhǎng)通路的一個(gè)有效方法是標(biāo)記法，其基本思尋找增長(zhǎng)通路的一個(gè)有效方法是標(biāo)記法，其基本思想如下：想如下： 設(shè)設(shè)G= V1,V2,E 是二部圖，在是二部圖，在G中作一個(gè)匹配中作一個(gè)匹配M，用，用(* *)標(biāo)記標(biāo)記V1中所有中所有M的非飽和點(diǎn)，然后交替地的非飽和點(diǎn)，然后交替地進(jìn)行以下和兩步：進(jìn)行以下和兩步： 選一個(gè)選一個(gè)V2的新標(biāo)記過的頂點(diǎn)，比如說的新標(biāo)記過的頂點(diǎn)，比如說bi，用，用(bi)標(biāo)記通過標(biāo)記通過M中的邊與中的邊與bi鄰接且尚未標(biāo)記過的鄰接且尚未標(biāo)記

17、過的V1的的所有頂點(diǎn)。對(duì)所有頂點(diǎn)。對(duì)V2所有新標(biāo)記過的頂點(diǎn)重復(fù)這一過程。所有新標(biāo)記過的頂點(diǎn)重復(fù)這一過程。 選一個(gè)選一個(gè)V1的新標(biāo)記過的頂點(diǎn)，比如說的新標(biāo)記過的頂點(diǎn)，比如說ai，用，用(ai)標(biāo)記不通過標(biāo)記不通過M中的邊與中的邊與ai鄰接且尚未標(biāo)記過的鄰接且尚未標(biāo)記過的V2的所的所有頂點(diǎn)。對(duì)有頂點(diǎn)。對(duì)V1所有新標(biāo)記過的頂點(diǎn)重復(fù)這一過程。所有新標(biāo)記過的頂點(diǎn)重復(fù)這一過程。 離散數(shù)學(xué)一些特殊的圖21 直至標(biāo)記到一個(gè)直至標(biāo)記到一個(gè)V2中的中的M的非飽和點(diǎn)。從的非飽和點(diǎn)。從該頂點(diǎn)倒向追蹤到標(biāo)記有該頂點(diǎn)倒向追蹤到標(biāo)記有(* *)的頂點(diǎn)，就得到的頂點(diǎn)，就得到了一個(gè)了一個(gè)M增長(zhǎng)通路。把增長(zhǎng)通路。把M增長(zhǎng)通路中所

18、有屬于增長(zhǎng)通路中所有屬于M的邊從的邊從M中去掉，而把中去掉，而把M可擴(kuò)路中所有不屬可擴(kuò)路中所有不屬于于M的邊添加到的邊添加到M中，得到一個(gè)新的匹配中，得到一個(gè)新的匹配M且其所含邊數(shù)比匹配且其所含邊數(shù)比匹配M所含的邊數(shù)多所含的邊數(shù)多1。對(duì)。對(duì)M重復(fù)上述過程，重復(fù)上述過程，直到，直到G中已不存在增長(zhǎng)中已不存在增長(zhǎng)通路，此時(shí)的匹配就是最大匹配。通路，此時(shí)的匹配就是最大匹配。離散數(shù)學(xué)一些特殊的圖22 【例例】如圖是二部圖，求其最大匹配。如圖是二部圖，求其最大匹配。a1 a2 a3 a4b1 b2 b3 b4 b5離散數(shù)學(xué)一些特殊的圖23 【例例】如圖是二部圖，求其最大匹配。如圖是二部圖，求其最大匹配。

19、離散數(shù)學(xué)一些特殊的圖24 解：取二部圖的一個(gè)匹配解：取二部圖的一個(gè)匹配M= (a3,b1), (a5,b2)。用。用(* *)標(biāo)記標(biāo)記V1中所有中所有M的非飽和點(diǎn)的非飽和點(diǎn)a1, a2, a4。 選選V1的新標(biāo)記過的頂點(diǎn)的新標(biāo)記過的頂點(diǎn)a1，用，用(a1)標(biāo)記不標(biāo)記不通過通過M的邊與的邊與a1鄰接且尚未標(biāo)記過的鄰接且尚未標(biāo)記過的V2的頂點(diǎn)的頂點(diǎn)b1；類似地用類似地用(a2)標(biāo)記標(biāo)記b2。 選選V2的新標(biāo)記過的頂點(diǎn)的新標(biāo)記過的頂點(diǎn)b1，用，用(b1)標(biāo)記通標(biāo)記通過過M的邊與的邊與b1鄰接且尚未標(biāo)記過的鄰接且尚未標(biāo)記過的V1的頂點(diǎn)的頂點(diǎn)a3；類似地用類似地用(b2)標(biāo)記標(biāo)記a5。 離散數(shù)學(xué)一些特殊

20、的圖25 選選V1的新標(biāo)記過的頂點(diǎn)的新標(biāo)記過的頂點(diǎn)a3，因?yàn)椴淮嬖诓煌?，因?yàn)椴淮嬖诓煌ㄟ^過M的邊與的邊與a3鄰接的鄰接的V2的頂點(diǎn)，所以不用的頂點(diǎn)，所以不用(a3)標(biāo)標(biāo)記記V2的頂點(diǎn)；用的頂點(diǎn)；用(a5)標(biāo)記標(biāo)記b3或或b4，假定用，假定用(a5)標(biāo)標(biāo)記記b3。如圖所示。如圖所示。 b3是是M的非飽和點(diǎn)，標(biāo)記結(jié)束。的非飽和點(diǎn)，標(biāo)記結(jié)束。 從從b3倒向追蹤到標(biāo)記有倒向追蹤到標(biāo)記有(* *)的頂點(diǎn)，就得到的頂點(diǎn)，就得到了了M增長(zhǎng)通路：增長(zhǎng)通路：a4b2a5b3或或a2b2a5b3，取后者。把，取后者。把M增長(zhǎng)通路增長(zhǎng)通路a2b2a5b3中的邊中的邊(a5,b2)從從M中去掉，中去掉，而把而把(a2

21、,b2)和和(a5,b3)添加到添加到M中得到新的匹配中得到新的匹配M=(a3,b1), (a2,b2), (a5,b3)，如圖，如圖9.61所示。所示。離散數(shù)學(xué)一些特殊的圖26離散數(shù)學(xué)一些特殊的圖27 對(duì)匹配對(duì)匹配M= (a3,b1), (a2,b2), (a5,b3) 再用標(biāo)記法：再用標(biāo)記法： 用用(* *)標(biāo)記標(biāo)記V1中所有中所有M的非飽和點(diǎn)的非飽和點(diǎn)a1和和 a4。 選選V1的新標(biāo)記過的頂點(diǎn)的新標(biāo)記過的頂點(diǎn)a1，用，用(a1)標(biāo)記不通過標(biāo)記不通過M的邊與的邊與a1鄰接且尚未標(biāo)記過的鄰接且尚未標(biāo)記過的V2的所有頂點(diǎn)的所有頂點(diǎn)b1；再用；再用(a4)標(biāo)記標(biāo)記b2。 選選V2的新標(biāo)記過的頂點(diǎn)

22、的新標(biāo)記過的頂點(diǎn)b1，用，用(b1)標(biāo)記通過標(biāo)記通過M的的邊與邊與b1鄰接且尚未標(biāo)記過的鄰接且尚未標(biāo)記過的V1的所有頂點(diǎn)的所有頂點(diǎn)a3；再用；再用(b2)標(biāo)標(biāo)記記a2。 選選V1的新標(biāo)記過的頂點(diǎn)的新標(biāo)記過的頂點(diǎn)a2和和a3，V2中已無可標(biāo)記中已無可標(biāo)記的頂點(diǎn)。的頂點(diǎn)。 圖中已不存在增長(zhǎng)通路，所以圖中已不存在增長(zhǎng)通路，所以M就是最大匹配。就是最大匹配。離散數(shù)學(xué)一些特殊的圖28 【例例】求下圖的最大匹配。求下圖的最大匹配。 離散數(shù)學(xué)一些特殊的圖29 解：取二部圖圖解：取二部圖圖9.62的一個(gè)匹配的一個(gè)匹配 M=(a2,b2), (a3,b3), (a5,b5)。用。用(* *)標(biāo)記標(biāo)記V1中所有中

23、所有M的非飽和點(diǎn)的非飽和點(diǎn)a1, a4。 選選V1的新標(biāo)記過的頂點(diǎn)的新標(biāo)記過的頂點(diǎn)a1，用，用(a1)標(biāo)記標(biāo)記b2和和b3。 選選V2的新標(biāo)記過的頂點(diǎn)的新標(biāo)記過的頂點(diǎn)b2和和b3，用，用(b2)標(biāo)記標(biāo)記a2，用，用(b3)標(biāo)記標(biāo)記a3。 選選V1的新標(biāo)記過的頂點(diǎn)的新標(biāo)記過的頂點(diǎn)a2，用，用(a2)標(biāo)記標(biāo)記b1, b4和和b5。 由于由于b1和和b4都是都是M的非飽和點(diǎn)，說明找到了的非飽和點(diǎn)，說明找到了M可擴(kuò)路?？蓴U(kuò)路。 它們是：它們是：a1b2a2b4和和a1b2a2b1。選前者，把邊。選前者，把邊(a2,b2)從從M中中去掉，而把去掉，而把(a1,b2)和和(a2,b4)添加到添加到M中，得

24、到新的匹配中，得到新的匹配M= (a1,b2),(a2,b4),(a3,b3), (a5,b5) ，如圖，如圖9.63所示。所示。 對(duì)于匹配對(duì)于匹配M= (a1,b2),(a2,b4),(a3,b3), (a5,b5)重復(fù)上述過重復(fù)上述過程，已找不到程，已找不到M可擴(kuò)路。所以可擴(kuò)路。所以M就是最大匹配。就是最大匹配。離散數(shù)學(xué)一些特殊的圖30離散數(shù)學(xué)一些特殊的圖31Hall定理 定理定理(Hall定理定理) 設(shè)二部圖設(shè)二部圖G=中，中，|V1| |V2|. G中存中存在從在從V1到到V2的完備匹配當(dāng)且僅當(dāng)?shù)耐陚淦ヅ洚?dāng)且僅當(dāng)V1中任意中任意k 個(gè)頂個(gè)頂點(diǎn)至少與點(diǎn)至少與V2中的中的k個(gè)頂點(diǎn)相鄰個(gè)頂點(diǎn)

25、相鄰(k=1,2,|V1|).由由Hall定理不難證明定理不難證明, 上一頁圖上一頁圖(2)沒有完備匹配沒有完備匹配. Hall定理中的條件稱為定理中的條件稱為“相異性條件相異性條件”離散數(shù)學(xué)一些特殊的圖32定理定理 設(shè)二部圖設(shè)二部圖G=中中, 如果存在如果存在t 1, 使得使得(1)V1中每中每個(gè)頂點(diǎn)至少關(guān)聯(lián)個(gè)頂點(diǎn)至少關(guān)聯(lián) t 條邊條邊, (2)而而V2中每個(gè)頂點(diǎn)至多關(guān)聯(lián)中每個(gè)頂點(diǎn)至多關(guān)聯(lián)t條條邊，則邊，則G中存在中存在V1到到V2的完備匹配的完備匹配. (充分條件充分條件)證明證明 如果如果(1)成立成立, 則與則與V1中中k (1k|V1|)個(gè)頂點(diǎn)相關(guān)聯(lián)的邊個(gè)頂點(diǎn)相關(guān)聯(lián)的邊的總數(shù)的總數(shù), 至少是至少是kt條。根據(jù)條。根據(jù)(2)這些邊至少要與這些邊至少要與V2中中k個(gè)頂個(gè)頂點(diǎn)相關(guān)聯(lián)。點(diǎn)相關(guān)聯(lián)。l這就得出這就得出V1中每中每k (1k|V1|)個(gè)頂點(diǎn)個(gè)