最大對集問題

介紹

最大對集問題(maximum matching problem ) 一類組合最最佳化問題.指在一個給定圖上找一個最 大對集(最大基數對集)的問題(參見“對集”).二部 圖(偶圖)的最大對集問題可用匈牙利法求解，也可 轉化為網路的最大流問題求解.1965年，厄得蒙斯 (Edmonds , J.)對匈牙利法作了修改，得到了一般圖 最大對集的一個有效算法.