> 就是序列...AB...
> 出现A和B是敌人的情况，就一定可以找到CD,使得C是A的朋友，D是B的朋友，就是形如：...AB...CD...。证明略
> 这样变为...AC...BD...，就是把链B..C翻转
> 可以在有限步内停止
>  

• 不是吧，没有随机的 (0) children_s_dining 2005-06-24 18:35:28
  • 如果把Friendly的dis设成1，!Friendly的dis设成oo，这个是不是就等同于求最短Hamilton圈了 (0) TN 2005-06-24 19:53:50
    • oo.... (0) frkstyc 2005-06-24 20:06:50
    • 不是等同的，至少是特殊情况下的hamilton问题，因为约束条件非常强，每个小孩很乖，不会有多于n-1个的敌人 (0) children_s_dining 2005-06-24 20:27:52