安定集合
グラフの部分点集合で、どの2点も隣接していないもの
点カバー
グラフの部分点集合Sで、グラフのどの辺もSに含まれる点に接続している
二部グラフの場合、
最小点カバー
と、
最大マッチング
はサイズが同じ
一般のグラフで、最小点カバーと最大安定集合の頂点数を足すとグラフ自体の頂点数