Skip to content →

グラフ上の陣取りゲーム

Graph Theory (Diestel) の演習問題4 (Chapter2) が面白いと思ったので取り上げてみます。

問題:無向グラフ \(G\) 上で二人の男女がひとつの駒を使った陣取りゲームをしている。男が先手、女が後手。それぞれのターンでは、駒を未訪問の隣接頂点に動かさなければならない。動かせなくなった方が負け。まだ駒がどの頂点にも置かれていないときは、好きな頂点に駒を置ける。男女は最適に行動するとき、どちらが勝つか。

勝利条件は次の通り。

完全マッチング \(M\) が存在 \(\Leftrightarrow\) 後手の勝ち。

証明:

\(\Rightarrow\) : 後手は完全マッチングの辺に沿って動かすと必勝。

\(\Leftarrow\) : 対偶を示します。最大マッチング \(M’\) を一つ固定し、\(M’\) に含まれない頂点 \(v\) から先手が始めます。先手は \(M’\) の辺に沿って動かすと必勝です。\(M’\) の辺に沿って動かせないと先手の負けですが、そのとき交互増加道が存在するので、最大マッチングに矛盾。

始点が固定されている場合

こんなツイートが届きました。

考えてみましょう……。

問題:無向グラフ \(G\) 上で二人の男女がひとつの駒を使った陣取りゲームをしている。男が先手、女が後手。それぞれのターンでは、駒を未訪問の隣接頂点に動かさなければならない。動かせなくなった方が負け。最初、駒は頂点 \(v\) に置かれている(頂点 \(v\) は訪問済みとする)。男女は最適に行動するとき、どちらが勝つか。

勝利条件は次の通り。

始点 \(v\) を含まない最大マッチング \(M\) が存在 \(\Leftrightarrow\) 後手の勝ち

証明

\(\Rightarrow\) : 後手は \(M\) の辺に沿って動かすと必勝。動かせなければ、交互増加道が存在して、最大性に矛盾。

\(\Leftarrow\) : 対偶を示します。最大マッチング \(M’\) に沿って先手は動かすと必勝。動かせなければ、交互道が存在して、\(v\) を含まないマッチングが存在しないことに矛盾。

綺麗に解決しましたね。一問目の必勝法は去年の輪読で maspy さんに教えてもらいました。

Published in グラフ理論

Comments

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA