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

來源: SwiperTheFox 於 2010-04-13 08:57:38 [] [博客] [舊帖] [給我悄悄話] 本文已被閱讀： 次 (450 bytes)
本文內容已被 [ SwiperTheFox ] 在 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

請您先登陸，再發跟帖！