完全二分图k2，3有奇数长度的回路吗
答案:1 悬赏:80
解决时间 2021-01-28 11:07
- 提问者网友：佞臣
- 2021-01-27 15:21
完全二分图k2，3有奇数长度的回路吗
最佳答案
- 二级知识专家网友：夜风逐马
- 2021-01-27 16:24
（数学归纳法）
当n=3个顶点时候,明显
假设当n=k,k为奇数时,没有Hamiton圈.1
当n=k+2时,假设有hamiton圈
那么由于是二分图,圈中相邻顶点属于不同group,假设ABCD是圈中四个相邻的顶点,则AC在二分图的一个GroupA,BD在GroupB中,那么AD有边相连
取掉BC两点,链接AD,仍然是hamiton圈,而剩下点仍然是二分图
与假设1矛盾,所以没有hamiton圈
由数学归纳法可证
当n=3个顶点时候,明显
假设当n=k,k为奇数时,没有Hamiton圈.1
当n=k+2时,假设有hamiton圈
那么由于是二分图,圈中相邻顶点属于不同group,假设ABCD是圈中四个相邻的顶点,则AC在二分图的一个GroupA,BD在GroupB中,那么AD有边相连
取掉BC两点,链接AD,仍然是hamiton圈,而剩下点仍然是二分图
与假设1矛盾,所以没有hamiton圈
由数学归纳法可证
我要举报
如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯