作业帮离散数学有关Hamilton图的题
来源：学生作业帮 编辑：作业帮 分类：数学作业 时间：2024/05/18 03:59:55
离散数学有关Hamilton图的题
n人中假设任意两人认识其余n-2个人,证明：
1,当n>=3时,n人排成一行,除排头排尾外其余人认识自己左右邻
2,当n〉=4时,n人围成圈,每人认识自己左右邻
n人中假设任意两人认识其余n-2个人,证明：
1,当n>=3时,n人排成一行,除排头排尾外其余人认识自己左右邻
2,当n〉=4时,n人围成圈,每人认识自己左右邻
本质上是有哈密顿路和哈密顿圈的问题
Direr 1952年的定理n>=3个顶点的图最小度数大于n/2则有哈密顿圈
再问： 没有啊，我看书上是任意两点度数之和大于n-1则有哈姆顿路，大于n则有哈姆敦图，可是如何得到n-1 与n，只能得到n-2啊？
再答： 这是图论中的定理 你那个定理也可以 两个认识的人之间连线，每人连出去n-2，两个人之和2n-4，当n>3时2n-4>=n，当n=3时2n-4>=n-1
再问： 我写错题了,是任意两人合起来认识其他n-2人,这该如何解决?
再答： 1. n=3时一定有哈密顿路是显然的 2. n>3用数学归纳法可证 一定有哈密顿路 3. 下证n>3时一定有哈密顿圈 根据题目至少有一对顶点相邻（否则图不连通，不可能满足题意），因为任意两人认识其余n-2个人，所以从这对顶点各自出发，可连结到一对不相同的顶点（因为n>=4）。然后从这对不相同的顶点出发做上面相同的事（但要排除前面用过的顶点），做到不能做为止（即两个顶点连接相同顶点），于是最早两队顶点相邻边加上做出来这条路，组成哈密顿圈。
Direr 1952年的定理n>=3个顶点的图最小度数大于n/2则有哈密顿圈
再问： 没有啊，我看书上是任意两点度数之和大于n-1则有哈姆顿路，大于n则有哈姆敦图，可是如何得到n-1 与n，只能得到n-2啊？
再答： 这是图论中的定理 你那个定理也可以 两个认识的人之间连线，每人连出去n-2，两个人之和2n-4，当n>3时2n-4>=n，当n=3时2n-4>=n-1
再问： 我写错题了,是任意两人合起来认识其他n-2人,这该如何解决?
再答： 1. n=3时一定有哈密顿路是显然的 2. n>3用数学归纳法可证 一定有哈密顿路 3. 下证n>3时一定有哈密顿圈 根据题目至少有一对顶点相邻（否则图不连通，不可能满足题意），因为任意两人认识其余n-2个人，所以从这对顶点各自出发，可连结到一对不相同的顶点（因为n>=4）。然后从这对不相同的顶点出发做上面相同的事（但要排除前面用过的顶点），做到不能做为止（即两个顶点连接相同顶点），于是最早两队顶点相邻边加上做出来这条路，组成哈密顿圈。