誰能用圖論來解這道題？ 懇請牛人出著。

用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