看板ACMCLUB
標 題Re: [閒聊] 無路可走
發信站批踢踢兔 (Fri Feb 17 09:28:15 2006)
轉信站ptt!Group.NCTU!grouppost!Group.NCTU!ptt2
※ 引述《pangfeng (P老師)》之銘言：
: 給定一無向圖, 甲乙玩以下遊戲.
: 甲選定出發點, 乙由甲選定的出發點選一邊出發至下一點.
: 接著由甲選一邊出發至下一點.
: 兩人交互選邊, 但不可走到已走過的點. 無路可走者為負.
: 問甲存在必勝策略的充要條件為何?
以下有解答, 不喜勿入.
甲有必勝方法的充要條件為圖中無完美匹配. (perfect matching).
具體的方法其實不難, 請想一想.
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 140.112.28.26