用容斥原理易证有ai(1<i<k)使a1与ak相连且ai+1与a1相连，

这一点，怎么证的？




> 
> 由于每个人都与半数以上的人是朋友，这样就可以用调整法找到一个哈密顿圈。 
> 
> 把人与人的关系看作一个无向图，易证图是连通的。用贪心法找到一条极长路，设其为a1,a2,……,ak。用容斥原理易证有ai(1<i<k)使a1与ak相连且ai+1与a1相连，再连a1-ai+1与ai-ak,使ai与ai+1断开，则这条路变成了一个环。由于图是连通的，从这个环的某处断开必能找到一个更长的极长路，就这样反复找下去，最后那个最大的环就是该图的哈密顿圈。

• 注意这个条件吧,任意u,v,d(u)+d(v)>=n...而且...不是叫"容斥"吧? (73) ArXoR 2005-06-29 22:29:46
  • pigeon hole (0) frkstyc 2005-06-29 22:30:59
  • 有些明白了，找一条长为k的极长路，将其调整为关于这k个节点的hamiltom回路，然后在找长为k+1的极长路；但是怎么找长为k+1的极长路呢，有可能末尾节点只与当前回路中的点之间有回路，与剩余节点之间没有通路？难道要 (0) sunmoonstar_love 2005-06-29 22:53:52
    • 难道要回溯？我只会n阶完全图的构造（原来标题有长度限制，我晕） (0) sunmoonstar_love 2005-06-29 22:56:08
      • 图连通,存在v不在k圈上,且与圈上某点u相恋, (39) ArXoR 2005-06-29 22:59:34
        • 哦，原来在断长环的的时候，也要有保护，谢谢大家，基本上明白了，我最怵图论的题了，有些算法还没写过，一碰上图论的就算明白算法，也一直写不好 (43) sunmoonstar_love 2005-06-29 23:04:15
          • 写起来也不算麻烦 (0) ArXoR 2005-07-04 10:00:39
            • arxor mm 我终于ac了 (0) sunmoonstar_love 2006-11-06 22:15:58