マッチングアルゴリズム

【まっちんぐあるごりずむ (matching algorithm)】

マッチング問題を解くアルゴリズムのこと. 一般に, マッチングアルゴリズムは増加道を繰り返し求めることで実現される. マッチングに関する増加道とは, マッチングの枝とそうでない枝を交互に含み, かつ最初と最後の枝がマッチングに含まれるような道のことである. アルゴリズムは, 枝数 0 のマッチングからはじめ, 各反復では, ある条件を満たす増加道を求めてマッチングの枝数を増やす. このような手順により所望のマッチングを求める.