如何解“设G是n>=3的连通图,证明若m>=(n-1)(n-2)/2+2,则G存在哈密顿回路”?

如何解“设G是n>=3的连通图,证明若m>=(n-1)(n-2)/2+2,则G存在哈密顿回路”?

题目
如何解“设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.
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
1,人们染上烟瘾,最终因吸烟使自己丧命.
最新试题
热门考点

超级试练试题库

© 2017-2019 超级试练试题库,All Rights Reserved.