有25个圆一排画5个圆有5排,第5排也就是最后一排的第二个圆不画只有四个,能否一笔连起来,不能用斜线(如下图）000000000000000000000000

Question

有25个圆一排画5个圆有5排,第5排也就是最后一排的第二个圆不画只有四个,能否一笔连起来,不能用斜线(如下图）0 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0

Answer 1

哈密顿图有一个定理：设无向图G=是半哈密顿图,对于任意的V1∈V且V1≠Φ均有p(G-V1)≤v1+1.
换句话说,设V2=G-V1,若|V2|≥|V1|+2,则图一定不是哈密顿图.
定义这玩意就是这样,把简单的东西总要说的很复杂
解释一下上边的含义：
就是说把这个图里的所有点分成2部分,一部分叫V1,一部分叫V2.
如果V1比V2多2个以上,则图肯定一笔画不完（即不是半哈密顿图）.
当然V1,V2不是随便分的,还有个限制,就是V1里的各个点不能相临,V2里的各个点也不能相临.
若要一笔画完的话,无论从哪里开始,设V1中的某个点开始,下一个点必定是V2中的某个点.V2点完了以后下个点必定是V1...依次类推.最后一个V2点画完以后,V1还剩2个点,而这2个点不相临,无论如何也连不上的.所以这是个不可能完成的任务~