hall定理例題?
陶小兔65 發表于 動漫2022-07-22
Hall定理是二分圖匹配問題中匈牙利演算法的基礎。
中文名
Hall定理
適用領域範圍
X中的任意k個點至少與Y中的k個點相鄰
適用領域範圍
二分圖匹配問題
推導結論
匈牙利演算法
Hall定理:
此定理使用於組合問題中,二部圖G中的兩部分頂點組成的集合分別為X, Y, X={X1, X2, X3,X4,……。。。,Xm}, Y={y1, y2, y3, y4 ,……。。。,yn},G中有一組無公共點的邊,一端恰好為組成X的點的充分必要條件是:
X中的任意k個點至少與Y中的k個點相鄰。(1≤k≤m)
本論還有一個重要推論:
二部圖G中的兩部分頂點組成的集合分別為X,Y, 若∣X∣=∣Y∣,且G中有一組無公共端點的邊,一端恰好組成X中的點,一端恰好組成Y中的點,則稱二部圖G中存在完美匹配。若圖G的每個點度數為t,則稱二部圖G為t——-正則的二部圖存在完美匹配。