不是VIP会员,不能显示答案

题目解答

题目:
Hackenbush 是一款老少皆宜的双人博弈游戏。该游戏双方分别被称为红方与蓝方。游戏的局面基于一些顶点和边 ,其中边分为红色、蓝色与绿色。一些顶点长在大地上(用虚线表示),而另一些顶点将通过边直接与间接地与大地相连。每一局将从事先约定好的一方开始,每一方轮流选择属于自己颜色的边,然后将该边删除。特别地,对于绿色的边,红蓝双方都可以进行删除操作。如果删除后,某些顶点或边不再与大地联通,则这些顶点或边将自动被删除。如果轮到某一方时,属于他的颜色的所有的边都被删除了,那么他就输了整场游戏。

游戏的局面可以分为四种,分别为先手必胜局面、后手必胜局面、红方必胜局面、蓝方必胜局面。例如,图中第一、二个局面为蓝方必胜局面(无论蓝方先手后手,它只需要删除唯一的蓝色边,红方就无法操作了);第三个局面为红方必胜局面;第四、五个局面为先手必胜局面。下列说法正确的为( )。
  • A.若 Hackenbush 中不存在绿色边,则一定不 会出现先手必胜局面
  • B.Hackenbush 中不存在后手必胜局面
  • C.即使不存在红色边与蓝色边,Hackenbush 问题仍是NP-Hard问题
  • D.若不存在绿色边,则Hackenbush问题是P类问题
考点:
分析:
解答:
评论:
老师: