都匀新阳:请大家帮忙解决我一个,有奖游戏

来源:百度文库 编辑:杭州交通信息网 时间:2024/04/24 01:53:56
O O O O O
O O O O
O O O O O
O O O O O
O O O O O(就是 这样的图形,请大家帮忙游戏啊)
用一条线连起来,不准画斜线,不准走空格,不准有重合圈圈。谢谢!
你知道吗?我现在很穷,一猪头说,我回答出来就给我500,500哎。对于我来说多么大的数字喔!一定要告诉人家,好不好嘛。我请大家吃冰淇淋。吃一万个喔!

肯定画不出来!
好象跟“汉密尔顿图”有关。
可以用染色法证明:
●○●○●
○●○●
●○●○●
○●○●○
●○●○●
黑圈13个
白圈11个
因为不能斜连,所以连完一个黑圈后只能连白圈,连完一个白圈后只能连黑圈,总是黑白交替出现。因为黑圈比白圈多两个,所以最多只能连上23个圈而不是24个。

参考定义
1.哈密顿通路与哈密顿回路 通过图G的每个结点一次,且仅一次的通路,就是哈密顿通路,通过图G的每个结点一次,且仅一次的回路,就是哈密顿回路。

2.哈密顿图 存在哈密顿回路的图就是哈密顿图。

3.半哈密顿图 存在哈密顿通路不存在哈密顿回路的图就是半哈密顿图。
4.二部图 设G=<V,E>为一个无向图,若能将V分成V1和V2(V1∪V2=V,V1∩V2= ),使得G中的每条边的两个端点都是一个属于V1,另一个属于V2,则称G为二部图(或称二分图,偶图等),称V1和V2为互补顶点子集,常将二部图G记为<V1 ,V2 ,E>.又若G是简单二部图,V1中每个顶点均与V2中所有顶点相邻,则称G为完全二部图,记为Kr,s,其中r=|V1|,s=|V2|.

参考定理
1. 设无向图G=<V,E>是半哈密顿图,对于任意的V1 V且V1≠ 均有 p(G-V1)≤|V1|+1.
2.设G是n阶无向简单图,若对于G中任意不相邻的顶点vi,vj,均有d(vi)+d(vj)≥n-1?(15.1)则G中存在哈密顿通路。

3.设二部图G=<V1,V2,E>,|V1|≤|V2|,且|V1|≥2,|V2|≥2,由定理15.6及其推论可以得出下面结论:
??(1)若G是哈密顿图,则|V1|=|V2|。
??(2)若G是半哈密顿图,则|V2|=|V1|+1。
??(3)若|V2|≥|V1|+2,则G不是哈密顿图,也不是半哈密顿图。

4.一个无向图G=<V,E〉是二部图当且仅当G中无奇数长度的回路。

上图为原图中点与点之间所有可能连结路径,可以看出图中无回路,根据定理4可判断子图为二部图。
下图,被蓝线划掉的是V1 ,其余的是V2,很明显,|V1|=11,|V2|=13,|V2|=|V1|+2,根据定理3(3)可知,此图不是哈密顿图,也不是半哈密顿图,因此没有通过图的每个结点一次,且仅一次的通路的方法,所以,图1中的24个点不可能用一笔连起来

所以此题无解

不可能,如果要走完,从一个点出发,偶数格应少于单数格的个数!

不可能,用一条线连起来,不准画斜线,不准走空格,不准有重合圈圈(点数应是奇数),用一条线连起来,不准走空格,不准有重合圈圈(点数应是偶数),你被骗了!