Matching vs Independent Set - #567 div2 e

#グラフ #相補的 #greedy

できる限り大きな matching を満たす辺の集合をとる
matching : どの 2 要素も端点を共有しない
集合のサイズを x とする

matching の端点でない頂点で, できる限り大きな independent を満たす頂点の集合をとる
independent : どの 2 要素も辺で結ばれてない
集合のサイズを y とする

x または y ≥ n
であることを示す

まず, x ≥ n ならそれが答え
そうでないとする
matching の端点は2 * n 未満なので, matching の端点でない頂点は n 以上ある

matching の端点でない頂点はすべて, independent を満たす頂点集合の頂点とできる
ことを示す

ある頂点が matching の端点でないとする
その頂点と辺で結ばれている頂点は matching の頂点である

そうでないと, その 2 頂点間の辺は matching の要素にできる