完全二分图k2，3有奇数长度的回路吗
答案:2 悬赏:0 手机版
解决时间 2021-12-23 15:32
- 提问者网友：两耳就是菩提
- 2021-12-22 17:12
完全二分图k2，3有奇数长度的回路吗
最佳答案
- 五星知识达人网友：轮獄道
- 2021-12-22 17:59
（数学归纳法）
当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圈
由数学归纳法可证
全部回答
- 1楼网友：渡鹤影
- 2021-12-22 19:29
没有
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息
大家都在看
推荐资讯