読み方:まっちんぐもんだい 【英】:matching problem 概要 無向グラフが与えられたときに, ある目的にしたがってマッチングを選ぶ問題をマッチング問題と呼ぶ. 例えば, 最大要素マッチング問題, 最大重みマッチング問題(割当問題), 安定なマッチングを求める安定結婚問題などが挙げられる. 2部グラフでのマッチング問題はネットワークフロー問題の特殊ケースとして解くことができるのに対し, 一般のグラフの場合は問題の構造がより複雑になり多少工夫を要するが, いずれの問題も多項式時間で解くことができる. 詳説 を無向グラフとする. のマッチング (matching) とは, 端点を共有しない枝の集合 のことである. 本の枝からなるマッチングを -マッチングと呼び, 特に のときは完全マッチングと呼ぶ. 与えられた目的に従ってマッチングを選ぶ問題のことを, マッチング問題という.