之前我們講了哥尼斯堡七橋問題
這個問題最後被偉大的大數學家歐拉解決了。
他證明出這七座橋永遠不可能一次性不帶重複的走完。
但是還有一個問題歐拉一直沒有解決,那就是:
如果只走其中的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種走法!