SALT TREE XV (salt) 解説
ここでは端的に必勝法を書いてしまう。
頂点数と辺数が両方とも偶数になっているときが必敗状態だから、自分の操作のあとに必敗になるようにすればよい。
必敗状態からは必ず必勝状態に遷移することの証明
- 頂点を削除したとき： 頂点数の偶奇が反転するので明らか。
- 辺を削除したとき： 辺の数の偶奇が反転するので明らか。
必勝状態からは必ず必敗状態に遷移できることの証明
- 頂点が奇数個・辺が奇数個の場合： グラフは森であり、1つ以上の辺を持つから、次数が1の頂点が必ず存在するので、それを取り除けばよい。
- 頂点が奇数個・辺が偶数個の場合： 全ての頂点の次数が奇数だとすると、次数の和も奇数になるが、これは握手補題に反する。したがって、次数が偶数の頂点が必ず存在するので、それを取り除けばよい。
- 頂点が偶数個・辺が奇数個の場合： 辺が奇数個あるということは1個以上の辺があるので、どれでもいいから取り除けばよい。
コメント
最終更新：2013年02月22日 20:19
