マッチング (グラフ理論)

出典: フリー百科事典『ウィキペディア(Wikipedia)』
2013年6月30日 (日) 11:29時点におけるSakesnare (トーク)による版 (一般化)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内検索

グラフ理論においてマッチングとは、グラフ中の枝集合で、互いに端点を共有しないもののこと。特に、これ以上枝を追加できないもののことを極大マッチング、枝数が最大のものを最大マッチングという。また、グラフ上の全ての頂点が、マッチング中のいずれかの枝の端点になっているとき、そのマッチングを完全マッチングという。

極大マッチング、最大マッチングは必ず存在するが、完全マッチングは存在するとは限らない。(例: 奇数個頂点のグラフ)

一般化

関連項目