※ 引述《pangfeng (P老師)》之銘言：
: ※ 引述《pangfeng (P老師)》之銘言：
: : 給定一無向圖, 甲乙玩以下遊戲.
: : 甲選定出發點, 乙由甲選定的出發點選一邊出發至下一點.
: : 接著由甲選一邊出發至下一點.
: : 兩人交互選邊, 但不可走到已走過的點. 無路可走者為負.
: : 問甲存在必勝策略的充要條件為何?
以下有解答, 不喜勿入.
: 甲有必勝方法的充要條件為圖中無完美匹配. (perfect matching).
: 具體的方法其實不難, 請想一想.
如有完美匹配, 則不管甲選何處, 乙沿完美匹配走即可, 甲必敗.
如無完美匹配, 則存在一最大匹配. 甲一開始即選一未被此匹配選到的點.
乙不管如何走, 必回到被此匹配選到的點, 甲沿此最大匹配走即可.
乙不管如何走均無法脫困, 否則即存在alternating path, 違反最大匹配定義.
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 220.137.139.85