離散數(shù)學(xué)-二部圖復(fù)習(xí)
定義1： 若能將無向圖G=若V1中任一頂點(diǎn)與V2中每一個(gè)頂點(diǎn)均有且僅有一條邊相關(guān)聯(lián)，則稱二部圖G為完全二部圖（或完全偶圖）。
定理1： 一個(gè)無向圖G=
定義2： 設(shè)G=
設(shè)M為G中一個(gè)匹配。v屬于V（G），若存在M中的邊與v關(guān)聯(lián)，
則稱v為M飽和點(diǎn)，否則稱v為M非飽和點(diǎn)。若G中每個(gè)頂點(diǎn)都是M飽和點(diǎn)，則稱M為G中完美匹配。
定義3： 設(shè)G=
定理2：（Hall定理）設(shè)二部圖G=〈V1，V2，E〉，|V1|<=|V2|，G中存在從V1到V2的完備匹配當(dāng)且僅當(dāng)V1中任意k個(gè)頂點(diǎn)（k=1，2....，|V1|）至少鄰接V2中的k個(gè)頂點(diǎn)。
定理3：
由Hall定理容易證明下面定理：
1，V1中每個(gè)頂點(diǎn)至少關(guān)聯(lián)t（t>0）條邊；
2，V2中每個(gè)頂點(diǎn)至多關(guān)聯(lián)t條邊，則G中存在V1到V2的完備匹配。
Hall定理中的條件為“相異性條件”，定理3中的條件為“t條件”。
滿足t條件的二部圖，一定滿足相異性條件，事實(shí)上，由條件（1）可知，V1中k個(gè)頂點(diǎn)至少關(guān)聯(lián) kt條邊。由條件（2）可知，這 kt條邊至少關(guān)聯(lián)V2中的k個(gè)頂點(diǎn)，于是若G滿足t條件，則G一定滿足相異性條件，但反之不真。http://www.fuchuonang.cn/
【離散數(shù)學(xué)-二部圖復(fù)習(xí)】相關(guān)文章：
離散數(shù)學(xué)-歐拉圖復(fù)習(xí)10-09
離散數(shù)學(xué)-哈密頓圖復(fù)習(xí)10-09
離散數(shù)學(xué)-圖論基礎(chǔ)復(fù)習(xí)10-09
離散數(shù)學(xué)趣味題目10-09
報(bào)關(guān)員考試復(fù)習(xí)大綱第二章[第十二部分]02-03
探尋刑法司考規(guī)律，預(yù)測(cè)來年復(fù)習(xí)重點(diǎn)(圖)10-13
報(bào)關(guān)員考試復(fù)習(xí)大綱第三章[第十二部分]02-03