AOJ 12/28

2014-12-28 | [Competitive programming]

2347

与えられるグラフの頂点を倍増し (頂点 v に対しては対応する v’ を新たに加える)，次の規則で新たな辺を張る．

• 頂点 1 と頂点 q を結ぶ辺に対しては，1’ と q を新たに結ぶ．
• 頂点 p (p ≠ 1) と頂点 q を結ぶ辺に対しては，p’ と q’ を新たに結ぶ．

こうしてできるグラフが完全マッチングを持てば，元のグラフは Sunny Graph である．

十分性は，Sunny Graph であれば新グラフにおいて具体的なマッチングを構成できることから従う．

必要性を示す．完全マッチングがあると仮定する． 頂点 1 から「今いる頂点から，マッチングの相手に移動し，さらにその頂点から対応する頂点に移動する」ことを繰り返すと必ず頂点 1’ にたどり着くことがわかる． この繰り返しで通った頂点たちはサイクルを構成する． さて，新グラフからサイクルを構成する頂点たちを (対応する頂点も含め) 除去すると，在来の頂点と新しい頂点を結ぶ辺はもはや存在しない． 在来の頂点たちだけで完全マッチングがあるので，これがサイクル以外の部分を構成する．