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