マッチング問題

【まっちんぐもんだい (matching problem)】

無向グラフが与えられたときに, ある目的にしたがってマッチングを選ぶ問題をマッチング問題と呼ぶ. 例えば, 最大要素マッチング問題, 最大重みマッチング問題(割当問題), 安定なマッチングを求める安定結婚問題などが挙げられる. 2部グラフでのマッチング問題はネットワークフロー問題の特殊ケースとして解くことができるのに対し, 一般のグラフの場合は問題の構造がより複雑になり多少工夫を要するが, いずれの問題も多項式時間で解くことができる.