作业帮设G是n>=3的连通图,证明若m>=0.5（n-1）（n-2）+2,则G存在哈密顿回路
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/04 20:39:09
设G是n>=3的连通图,证明若m>=0.5（n-1）（n-2）+2,则G存在哈密顿回路
设G是n>=3的连通图,证明若m>=0.5（n-1）（n-2）+2,则G存在哈密顿回路
设G是n>=3的连通图,证明若m>=0.5（n-1）（n-2）+2,则G存在哈密顿回路
这个很简单,如果是作业题的话.
因为如果是作业题,那么很可能你课堂上学过这样一个定理：
若每2个点的度数之和大于等于n,则有Hamiltonian回路.
就用这个定理就可以了.
具体方法：
完全图,总共有：n(n-1)/2条边.
那么,G最多比完全图少了：n(n-1)/2 - (n-1)(n-2)/2 - 2 = n-3 条边.
下面,我们来看看G中两个顶点的度数之和,最少是多少.
完全图中,两个顶点度数之和为：2(n-1)
现在少了 n-3 条边,最极端的情形,这 n-3 条边均与某两个顶点相连,而且其中1条边还是连接这2个顶点的.于是,这2个顶点最多少了 n-2 的度数,也就是还剩：
2(n-1) - (n-2) = n 度数.
所以,符合那个定理,有H回路.
一个相当猥琐的数学归纳，直接证m=(n-1)(n-2)/2+2的情形……
n=3时显然成立，
n=k成立，n=k+1时要在图上加k-1条边，而k-1>3-1=2，也就是说在n=k的基础上绕道走第k+1个点就行了（加的k-1条边必须至少2条加载第k+1个点上，要不余下的n=k的那个子图就强连通了）...
全部展开
一个相当猥琐的数学归纳，直接证m=(n-1)(n-2)/2+2的情形……
n=3时显然成立，
n=k成立，n=k+1时要在图上加k-1条边，而k-1>3-1=2，也就是说在n=k的基础上绕道走第k+1个点就行了（加的k-1条边必须至少2条加载第k+1个点上，要不余下的n=k的那个子图就强连通了）
收起