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

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

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

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

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

所有跟帖： 

• 忘了把原题写完整，应该是： -SwiperTheFox- ♂ (82 bytes) () 04/13/2010 postreply 09:02:14

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

• 你有没有考虑 -SwiperTheFox- ♂ (20 bytes) () 04/13/2010 postreply 13:21:33

• 144 -jinjing- ♀ (79 bytes) () 04/13/2010 postreply 20:28:01

• no -SwiperTheFox- ♂ (26 bytes) () 04/14/2010 postreply 08:21:48

• 70 -jinjing- ♀ (220 bytes) () 04/14/2010 postreply 17:33:29

• You are close, but not exactly -SwiperTheFox- ♂ (364 bytes) () 04/15/2010 postreply 09:55:41

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

• This seems to be the best solution, can you reveal details? -SwiperTheFox- ♂ (6 bytes) () 04/16/2010 postreply 09:44:10

• Thanks. -jinjing- ♀ (0 bytes) () 04/17/2010 postreply 05:17:39

• details? please! -皆兄弟也- ♂ (0 bytes) () 04/16/2010 postreply 12:19:17

• 回复：details? please! -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- ♀ (161 bytes) () 04/17/2010 postreply 05:43:11

• 回复：谁能用图论来解这道题？ 恳请牛人出着。 -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- ♀ (98 bytes) () 04/13/2010 postreply 18:52:23

• 0. -twfx- ♂ (35 bytes) () 04/13/2010 postreply 21:09:41

• 1虽然不是质数但 -SwiperTheFox- ♂ (120 bytes) () 04/14/2010 postreply 02:25:08

• 进一步的思路，觉得可以彻底解决 -SwiperTheFox- ♂ (298 bytes) () 04/14/2010 postreply 02:27:10

• 这个不对 -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- ♀ (187 bytes) () 04/16/2010 postreply 06:14:25

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

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