マッチング

出典: ORWiki

【まっちんぐ (matching)】

無向グラフ $G = (V, E)\,$ の枝部分集合 $M \subseteq A\,$ で, どの2つの枝も端点を共有しないものをマッチングと呼ぶ. 枝部分集合 $M \subseteq A\,$ がマッチングならば, $M\,$ の枝に接続する点の数は $M\,$ の要素数の2倍に等しく, またそのときに限って $M\,$ はマッチングである. $k\,$ 本の枝からなるマッチングを $k\,$ -マッチングと呼び, 特に $|V|/2\,$ 本の枝からなるマッチングを完全マッチングと呼ぶ.