マッチング (グラフ理論)
(極大マッチング から転送)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/05/24 19:07 UTC 版)
グラフ理論においてマッチングとは、グラフ中の枝集合で、互いに端点を共有しないもののこと。特に、これ以上枝を追加できないもののことを極大マッチング、枝数が最大のものを最大マッチングという。また、グラフ上の全ての頂点が、マッチング中のいずれかの枝の端点になっているとき、そのマッチングを完全マッチングという。
- 1 マッチング (グラフ理論)とは
- 2 マッチング (グラフ理論)の概要
- 3 一般化
- 極大マッチングのページへのリンク