离散数学有关Hamilton图的题n人中假设任意两人认识其余-查字典问答网

来自黄维雄的问题

　　离散数学有关Hamilton图的题n人中假设任意两人认识其余n-2个人,证明：1,当n>=3时,n人排成一行,除排头排尾外其余人认识自己左右邻2,当n〉=4时,n人围成圈,每人认识自己左右邻

　　离散数学有关Hamilton图的题

　　n人中假设任意两人认识其余n-2个人,证明：

　　1,当n>=3时,n人排成一行,除排头排尾外其余人认识自己左右邻

　　2,当n〉=4时,n人围成圈,每人认识自己左右邻

5回答

2020-07-3100:59

我要回答

提示：回答问题需要登录哦！

提交

陈子侠

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

　　Direr1952年的定理n>=3个顶点的图最小度数大于n/2则有哈密顿圈

2020-07-31 01:02:35

黄维雄

　　没有啊，我看书上是任意两点度数之和大于n-1则有哈姆顿路，大于n则有哈姆敦图，可是如何得到n-1与n，只能得到n-2啊？

2020-07-31 01:04:22

陈子侠

　　这是图论中的定理你那个定理也可以两个认识的人之间连线，每人连出去n-2，两个人之和2n-4，当n>3时2n-4>=n，当n=3时2n-4>=n-1

2020-07-31 01:08:26

黄维雄

　　我写错题了,是任意两人合起来认识其他n-2人,这该如何解决?

2020-07-31 01:11:30

陈子侠

　　1.n=3时一定有哈密顿路是显然的2.n>3用数学归纳法可证一定有哈密顿路3.下证n>3时一定有哈密顿圈根据题目至少有一对顶点相邻（否则图不连通，不可能满足题意），因为任意两人认识其余n-2个人，所以从这对顶点各自出发，可连结到一对不相同的顶点（因为n>=4）。然后从这对不相同的顶点出发做上面相同的事（但要排除前面用过的顶点），做到不能做为止（即两个顶点连接相同顶点），于是最早两队顶点相邻边加上做出来这条路，组成哈密顿圈。

2020-07-31 01:13:30

大家都在问