atcoder https://blog.hatena.ne.jp/atcoder/ AtCoderInfo https://info.atcoder.jp/ グラフ理論 ゲーム理論 マッチング Berge の定理 解説動画はこちらです． 1. 概要 Undirected Vertex Geography は，無向グラフ上で駒を動かす $2$ 人ゲームです．各手番では，現在駒がある頂点から隣接する頂点に駒を移動させます．ただし，選べる頂点は，一度も駒が置かれたことがない頂点に限ります．動けなくなったプレイヤの負けです． 本記事では，Undirected Vertex Geography の必勝戦略が最大マッチングを用いて記述できることを証明します． 2. 前提知識 グラフ理論の用語，特にマッチングに関する用語を用います（参考：グラフ理論用語集）． 「関連問題」を解く上ではさらにマッチングに関する知識（例え… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Fundirected_vertex_geography" title="Undirected Vertex Geography - AtCoderInfo" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://img.atcoder.jp/aal-image-library/447b27a0bb3a580e31d39f0f67aafc76.png Hatena Blog https://hatena.blog 2026-04-10 14:41:44 rich https://info.atcoder.jp/entry/algorithm_lectures/undirected_vertex_geography 1.0 100%