设n是大于2的奇数,证明n阶完全无向图有(n-1)个边不相交的哈密顿回路

Question

如题所述

Answer 1

给结点编号1,2,3,.....,n

哈密顿回路1 ： 1-2-3-4-...-n

哈密顿回路2 ： 1-3-5-7-...-(n-1)

哈密顿回路3 ： 1-4-7-10-...-(n-2)

......

哈密顿回路i ： 1-(1+i)%n-(1+2i)%n-...-(1+(n-1)i)%n

......

哈密顿回路(n-1) ： 1-n-(n-1)-...-2

其中第i组和第(n-i)组重复，和其他组都不相交，可以用数论的知识证明，所以一共有(n-1)/2组。

扩展资料：

哈密顿图的必要条件： 若G=(V,E) 是一个哈密顿图，则对于V的每一个非空子集S，均有W(G－S) ≤|S|。其中|S|是S中的顶点数，W(G－S)表示图G擦去属于S中的顶点后，剩下子图的连通分支的个数。

哈密顿图的充分条件： 设G=(V,E)是一个无向简单图，|V|=n. n≥3. 若对于任意的两个顶点u，v∊V，d(u)+d(v) ≥n，那么, G是哈密尔顿图。此条件由美国图论数学家奥勒在1960年给出。

Answer 2

：G是n阶简单无向图，如果图G中任意两点的度数之和大于等于n-1，证明图G是连通图 假设G有两个连通分支G1和G2，那么取v1是G1中度数最小的顶点，v2是G2中度数最小的顶点，则d(v1)+d(v2)≤n-2（等号在G1和G2都是完全图时取到），这与条件矛盾。本回答被网友采纳

Answer 3

同学你好，我是李欢老师，我希望我布置的作业是由同学们经过思考做出来的，而不是从网上抄袭的，希望你可以认真思考自己解决这道问题。

Answer 4

同学，你题目都记错了，是(n-1)/2个，离散还想不想过了

Answer 5

同学你好，我是吕卫锋院长，我希望你可以自己来做这一道题，做一个自主思考的北航学子，以后的回复将会被屏蔽。