之前我們講了哥尼斯堡七橋問題
這個問題最後被偉大的大數學家歐拉解決了。
他證明出這七座橋永遠不可能一次性不帶重複的走完。
但是還有一個問題歐拉一直沒有解決，那就是：
如果只走其中的6座橋（不帶重複一次性走完），一共有多少種走法？
這個問題對歐拉來說可能太難了，所以他一直沒有……
開個玩笑。
這是一個記數問題，在計算機領域應用很廣。
比如一個密碼破譯系統，需要遍歷所有可能的組合。
比如一個城市交通導航系統，需要實時列出從A地到B地的所有走法。
比如公路電路的設計、物流旅行的規劃，一共多少種線路，哪種最省錢？
比如下載文件，文件被切分成了很多份，存放在不同的IP地址，有多少種路徑，如何選擇最優路徑？
上面說的這些大多是計算機圖論裡的東西，我們今天的問題也和圖論有關。
下面帶大家一起解決它。
（下文所說的走法指的是不帶重複一次性走完圖中所有線路的走法）
首先，我們要明白這幾個事實。
①下圖中，從A到B有4種走法。
（2×2=4）
②下圖中，從A到B有6種走法。
（3×2=6）
③下圖中，從O到O有8種走法。
（2×4=8）
其次，我們要進階一步。
④下圖中，從A到B有16種走法。
（1×4+2×6=16）（4是①的4，6是②的6）
⑤下圖中，從A到B有24種走法。
（3×8=24）（8是③的8）
最後，進入今天的主題。
首先我們把哥尼斯堡七橋拆一座，變成6。
情況一：
這其實就是④，只不過樣式變了，但是不影響本質，所以走法是16
但是要×2，因為可以從A到B，也可以從B到A。
16×2=32
情況二：
這其實也是④，只不過樣式變了，但是不影響本質，所以走法是16
但是要×2，因為可以從A到B，也可以從B到A。
而且要×4，因為情況二有四種。（左邊四個橋）
16×2×4=128
情況三：
這其實就是⑤，只不過樣式變了，但是不影響本質，所以走法是24
但是要×2，因為可以從A到B，也可以從B到A。
而且要×2，因為情況三有二種。（右上和右下）
24×2×2=96
結論：
32+128+96=256
不帶重複一次性走完哥尼斯堡的6座橋共有256種走法！
閱讀更多 數學與編程 的文章
