b匹配問題

b匹配問題(b-matching problem)匹配問題的推廣.在圖G=(V,E)上，對於每個節點二，設定正整數by，作為E的子集M，若滿足:對每個節點二，關聯於二的M中的邊數不超過叔，則稱M為b匹配。

b匹配問題(b-matching problem)匹配問題的推廣.在圖G=(V,E)上，對於每個節點二，設定正整數by，作為E的子集M，若滿足:對每個節點二，關聯於二的M中的邊數不超過叔，則稱M為b匹配.問題是max{c(M) }M為h匹配}，這裡

。為邊集E上的一個權函式.當對任何一個節點二，均有by = 1時，它就是匹配問題.若b。為任意的正數，則這種匹配問題被稱為最優匹配問題.從算法複雜性的角度而言，b匹配問題是一類P問題.