题目链接:Click here~~
题意:
n 个点的竞赛图,找出它的哈密顿路(n <= 100)。
解题思路:
首先,竞赛图是指每两个点之间都有一条边的有向图(即边数为 n*(n-1)/2 )。
然后,对于竞赛图,一定存在哈密顿路。转载一个证明:
求竞赛图中的哈密顿路的算法:
首先,由数学归纳法可证竞赛图在n>=2时必存在哈密顿路;
(1)n=2时显然;
(2)假设n=k时,结论成立,哈密顿路为V1,V2,...,Vi,...,Vk;
现添加第k+1个结点,若存在弧<Vi,Vk+1>和弧<Vk+1,Vi+1>,则可得哈密顿回路V1,V2,...,Vi,Vk+1,Vi+1,...,......
阅读全文