※ 引述《pangfeng (P老师)》之铭言： : ※ 引述《pangfeng (P老师)》之铭言： : : 给定一无向图, 甲乙玩以下游戏. : : 甲选定出发点, 乙由甲选定的出发点选一边出发至下一点. : : 接着由甲选一边出发至下一点. : : 两人交互选边, 但不可走到已走过的点. 无路可走者为负. : : 问甲存在必胜策略的充要条件为何? 以下有解答, 不喜勿入. : 甲有必胜方法的充要条件为图中无完美匹配. (perfect matching). : 具体的方法其实不难, 请想一想. 如有完美匹配, 则不管甲选何处, 乙沿完美匹配走即可, 甲必败. 如无完美匹配, 则存在一最大匹配. 甲一开始即选一未被此匹配选到的点. 乙不管如何走, 必回到被此匹配选到的点, 甲沿此最大匹配走即可. 乙不管如何走均无法脱困, 否则即存在alternating path, 违反最大匹配定义. --

※ 发信站: 批踢踢兔(ptt2.cc) ◆ From: 220.137.139.85