Question

离散数学有关Hamilton图的题

n人中假设任意两人认识其余n-2个人，证明：
1，当n>=3时，n人排成一行，除排头排尾外其余人认识自己左右邻
2，当n〉=4时，n人围成圈，每人认识自己左右邻

Answer 1

本质上是有哈密顿路和哈密顿圈的问题

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）。然后从这对不相同的顶点出发做上面相同的事（但要排除前面用过的顶点），做到不能做为止（即两个顶点连接相同顶点），于是最早两队顶点相邻边加上做出来这条路，组成哈密顿圈。