如何解“设G是n>=3的连通图,证明若m>=(n-1)(n-2)/2+2,则G存在哈密顿回路”?
来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/10/06 09:37:24
如何解“设G是n>=3的连通图,证明若m>=(n-1)(n-2)/2+2,则G存在哈密顿回路”?
一定存在一个度数至少为n-2的点v.否则的话,每个点的度数不超过n-3,那么边数最多只有n*(n-3)/22.如果v的度数是n-2,那么把v从图中去掉,剩余子图含有n-1个点以及至少(n-2)(n-3)/2+2条边.由归纳假设,子图中有HC(Hamilton Circuit):u1-u2-.-u(n-1)-u1.从这n-1个点里任取两个与v相连的,比如ui与uj.那么原图的HC就是u1-u2-.-ui-v-uj-.-u(n-1)-u1.3.如果v的度数是n-1,那么把v从图中去掉,剩余子图有至少(n-2)(n-3)/2+1条边.在子图里任意加上一条边,使得边数达到(n-2)(n-3)/2+2,再用归纳假设,得到一个HC.如果HC中不包含新加的边,用2的方法构造新HC;如果包含,那么把这条ui-uj边替换成两条ui-v-uj.
设G是n(n>=2)阶欧拉图,证明G是2-边连通图
设G是n阶m条的无向连通图,证明m>=n-1
简单图G有n个结点,e条边,设e>(n-1)(n-2)/2,证明G是连通的
证明!图论!证明:图G是连通的平面图,其点数为n,边数为e,则n-e+f=2
矩阵唯一的证明题:设A是m*n阶矩阵,如果存在G(也是m*n阶矩阵)使得(1)AGA=A;(2)GAG=G;(3)(AG
设G是有n个结点n条边的简单连通图,且G中存在度数为3的结点,证明G中至少有一个度数为1的结点
设f(n)=1 1/2 1/3 ...1/n,是否存在于自然数n的函数g(n),
设an=1+1/2+1/3+...+1/n是否存在关于n的整式g(n),使得等式a1+a2+...+a(n-1)=g(n
设f(n)=1+1/2+1/3+...+1/n,是否存在g(n)使f(1)+f(2)+...+f(n-1)=g(n)f(
设f(n)=1+1/2+1/3+...+1/n,是否存在关于自然数N的函数g(n),使等式f(1)+f(2)+.+f(n
无向图G=,且|V|=n,|e|=m,试证明以下两个命题是等价命题:G中每对顶点间具有唯一的通路,G连通且n=m+1
设G是一个有p个顶点q条边的图.试证:如果q=1/2(p-1)(p-2)+2,则G是哈密顿图.