作业帮 > 数学 > 作业

设G是一个有p个顶点q条边的图.试证:如果q=1/2(p-1)(p-2)+2,则G是哈密顿图.

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/05/28 05:28:36
设G是一个有p个顶点q条边的图.试证:如果q=1/2(p-1)(p-2)+2,则G是哈密顿图.
注:G的一个包含所有顶点的圈称为G的一个哈密顿圈.具有哈密顿圈的图称为哈密顿图.
很陷阱.实际上1/2(p-1)(p-2)就是p-1个点的完全图的边数(就是1到p-2的求和),在完全图中当然存在任意两点的H路了,再加上2条边正好连上第p个点.