设G是n>=3的连通图,证明若m>=0.5（n-1）（n-2）+2,则G存在哈密顿回路

来源：学生作业帮助网编辑：六六作业网时间：2024/11/25 14:01:58

设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的连通图,证明

设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的那个子图就强连通了）

收起

如何解“设G是n>=3的连通图,证明若m>=(n-1)(n-2)/2+2,则G存在哈密顿回路”? 设G是n>=3的连通图,证明若m>=0.5（n-1）（n-2）+2,则G存在哈密顿回路设G是n阶m条的无向连通图,证明m>=n-1 设G是n(n>=2)阶欧拉图,证明G是2-边连通图有关平面图的问题设G为任意的连通平面图,则有n-m+r=( )；若G是简单连通平面图n>=3,则m<=( )；若G是简单连通平面图n>=3,且G是二部图,则m<=（）.其中n表示定点数,m表示边数,r表设n阶无向简单图G有m条边,已知m>=1/2(n-1)(n-2)+1,证明G必连通设G是简单图,有n个顶点,最小度数a>[n/2]-1,证明G是连通的无向图G=,且|V|=n,|e|=m,试证明以下两个命题是等价命题:G中每对顶点间具有唯一的通路,G连通且n=m+1 设G为连通图,证明:e=(u,v)是G的割边的充要条件是e不含在G的任何回路已知n阶m条边的无向图G为k(k>=2)个连通分支的森林,证明m=n-k 证明：G连通不含回路推出G无回路且n=m+1 简单图G有n个结点,e条边,设e>(n-1)(n-2)/2,证明G是连通的简单图G有n个结点,e条边,设e>(n-1)(n-2)/2,证明G是连通的证明!图论!证明：图G是连通的平面图,其点数为n,边数为e,则n-e+f=2 设G是有n个结点,n条边的简单连通图,且G中存在度数为3的结点.证明：G中至少存在有一个度数为1的结点. 设G是有n个结点n条边的简单连通图,且G中存在度数为3的结点,证明G中至少有一个度数为1的结点设G是有n个结点n条边的简单连通图,且G中存在度数为3的结点,证明G中至少有一个度数为1的结点设G是有n个结点,m条边的连通图,必须删去G的( )条边,才能确定G的一棵生成树． A.m-n+1 B.m-n C.m+n+1