谁能用图论来解这道题？ 恳请牛人出着。

来源: SwiperTheFox 于 2010-04-13 08:57:38 [] [博客] [旧帖] [给我悄悄话] 阅读数 : (450 bytes)
本帖于 2010-04-15 10:02:55 时间, 由版主 于德利 编辑

用123456六个数组成一个六位数， 要求任何相邻的两个数互质。

用排列组合有几种解法，思路差不多。 但是觉得都比较 ad hoc， 不具推广性--如果各任意大的数，比如100，你怎么算？

想到一个图论的思路，但想了一天没想出来。当然顺着这个思路编程序好算。 就不知道有没有用图论的理论直接解决的办法。

我的思路是这样的： 把自然数看作顶点， 把互质的数用边连起来。 这道题就变成了，从各个顶点出发，遍历所有顶点，有几条路线？ 感觉上应该跟连通图有关。

所有跟帖： 

• 忘了把原题写完整，应该是： -SwiperTheFox- ♂ 给 SwiperTheFox 发送悄悄话 SwiperTheFox 的博客首页 (82 bytes) () 04/13/2010 postreply 09:02:14

• 回复：忘了把原题写完整，应该是： -sqgs- ♂ 给 sqgs 发送悄悄话 (112 bytes) () 04/13/2010 postreply 12:58:36

• 你有没有考虑 -SwiperTheFox- ♂ 给 SwiperTheFox 发送悄悄话 SwiperTheFox 的博客首页 (20 bytes) () 04/13/2010 postreply 13:21:33

• 144 -jinjing- ♀ 给 jinjing 发送悄悄话 (79 bytes) () 04/13/2010 postreply 20:28:01

• no -SwiperTheFox- ♂ 给 SwiperTheFox 发送悄悄话 SwiperTheFox 的博客首页 (26 bytes) () 04/14/2010 postreply 08:21:48

• 70 -jinjing- ♀ 给 jinjing 发送悄悄话 (220 bytes) () 04/14/2010 postreply 17:33:29

• You are close, but not exactly -SwiperTheFox- ♂ 给 SwiperTheFox 发送悄悄话 SwiperTheFox 的博客首页 (364 bytes) () 04/15/2010 postreply 09:55:41

• 72=(5!-4!*2) -jinjing- ♀ 给 jinjing 发送悄悄话 (10 bytes) () 04/15/2010 postreply 13:26:38

• This seems to be the best solution, can you reveal details? -SwiperTheFox- ♂ 给 SwiperTheFox 发送悄悄话 SwiperTheFox 的博客首页 (6 bytes) () 04/16/2010 postreply 09:44:10

• Thanks. -jinjing- ♀ 给 jinjing 发送悄悄话 (0 bytes) () 04/17/2010 postreply 05:17:39

• details? please! -皆兄弟也- ♂ 给 皆兄弟也 发送悄悄话 皆兄弟也 的博客首页 (0 bytes) () 04/16/2010 postreply 12:19:17

• 回复：details? please! -jinjing- ♀ 给 jinjing 发送悄悄话 (221 bytes) () 04/16/2010 postreply 16:00:53

• 2*4!可以理解，5!仍不太明白。anyway, thank you! -皆兄弟也- ♂ 给 皆兄弟也 发送悄悄话 皆兄弟也 的博客首页 (0 bytes) () 04/16/2010 postreply 20:55:59

• 回复：2*4!可以理解，5!仍不太明白。anyway, thank you! -jinjing- ♀ 给 jinjing 发送悄悄话 (161 bytes) () 04/17/2010 postreply 05:43:11

• 回复：谁能用图论来解这道题？ 恳请牛人出着。 -aisanguo- ♀ 给 aisanguo 发送悄悄话 aisanguo 的博客首页 (187 bytes) () 04/13/2010 postreply 15:44:53

• You're right.If don't think about first and last Nbs.Erler paths -jinjing- ♀ 给 jinjing 发送悄悄话 (98 bytes) () 04/13/2010 postreply 18:52:23

• 0. -twfx- ♂ 给 twfx 发送悄悄话 (35 bytes) () 04/13/2010 postreply 21:09:41

• 1虽然不是质数但 -SwiperTheFox- ♂ 给 SwiperTheFox 发送悄悄话 SwiperTheFox 的博客首页 (120 bytes) () 04/14/2010 postreply 02:25:08

• 进一步的思路，觉得可以彻底解决 -SwiperTheFox- ♂ 给 SwiperTheFox 发送悄悄话 SwiperTheFox 的博客首页 (298 bytes) () 04/14/2010 postreply 02:27:10

• 这个不对 -SwiperTheFox- ♂ 给 SwiperTheFox 发送悄悄话 SwiperTheFox 的博客首页 (28 bytes) () 04/14/2010 postreply 02:41:41

• 非图论解一：偶数不相邻，3，6不相邻，共32种。 -皆兄弟也- ♂ 给 皆兄弟也 发送悄悄话 皆兄弟也 的博客首页 (954 bytes) () 04/15/2010 postreply 17:30:56

• 非图论解二：偶数不相邻，共72种。其中3，6相邻，40种。72-40=32种 -皆兄弟也- ♂ 给 皆兄弟也 发送悄悄话 皆兄弟也 的博客首页 (700 bytes) () 04/15/2010 postreply 18:11:51

• 偶数不相邻，共144种。其中3，6相邻，72种。144-72=72种 -jinjing- ♀ 给 jinjing 发送悄悄话 (187 bytes) () 04/16/2010 postreply 06:14:25

• 我的结论不对，少算了两种情况。谢谢！ -皆兄弟也- ♂ 给 皆兄弟也 发送悄悄话 皆兄弟也 的博客首页 (0 bytes) () 04/16/2010 postreply 08:24:31

• think easy - combinatorial solution 回复：谁能用图论来解这道题？ 恳请牛人出着。 -mathg- ♂ 给 mathg 发送悄悄话 (145 bytes) () 08/15/2010 postreply 21:46:19

请您先登陆，再发跟帖！