2012.08.06 小小夢想家召集令!
超省時的逛展方法
本世紀知名畫派「五告派」的天才畫家來台展示15幅名畫，科科與端端相約參觀展覽，然而到了會場後，他們發現會場的動線非常複雜，而且再過一個半小時後，他們就得去補習，究竟該如何規劃路線，才能讓他們在最短的時間內參觀完這15幅世紀名畫呢？
如果要省下時間，最快方法就是不走重複的路線，走一次就能參觀完所有的名畫。其實有個數學家的數學定理可以為科科和端端找到解答喔!
首先，以下有兩個圖形A和B，你能夠不重複且一筆畫完嗎?
試幾次後，你會發現圖形A可以輕鬆找到多種一筆畫完的方式，下圖為其中一種方式:
但是圖形B不論怎麼畫，都無法用一筆畫畫完。
為什麼圖形A可以完成，而圖形B卻不行呢?其實像圖形A這類圖形，能夠一筆完成且不重複的圖形，在數學上，我們將其歸類為「尤拉圖」，這類圖形必須要擁有尤拉路徑或是尤拉迴路。
【尤拉圖：能夠走過所有的邊而沒有重複的圖】
什麼是尤拉路徑、尤拉迴路？
尤拉路徑(Euler path)：圖形中，走過每一個邊恰好一次。
→ 一筆畫走完，起點與終點可以不同。
尤拉迴路(Eulerian cycle)：有限圖中，走過每一個邊恰好一次且最終回到原點。 →一筆畫走完，起點與終點必須相同。
如何判別圖形有無尤拉路徑或尤拉迴路？
最快速的方式為觀察圖形的奇數頂點數量，若圖形中奇數頂點的總數為0個或是2個，此圖形必為尤拉圖!
什麼是奇數頂點?簡單來說，我們在圖形上找一個頂點，如果這個頂點所連接的線段有奇數條，那我們就稱這個頂點為「奇數頂點」。同理，如果這個頂點所連接的線段有偶數條，那麼這個頂點就叫做「偶數頂點」。因此，用前述準則分析圖形A與B(見下圖)，圖形A有兩個奇數頂點，符合尤拉路徑的規則，屬於尤拉圖；而圖形B有四個奇數頂點，馬上可知這個圖形不可能一筆完成不重複了!就可以清楚看出那一個屬於尤拉圖了!
0個和2個奇數頂點差別在哪呢?
奇數頂點的數量和尤拉路徑與尤拉迴路有關。
而有尤拉迴路的圖形(圖形D)，會有0個奇數頂點。不管從哪個頂點出發，最終一筆畫完後都會回到最初的頂點。
所以，利用尤拉圖定論規劃看展的動線，科科與端端的煩惱就可以馬上被解開囉!
首先，我們先將展場地圖簡化為線條與頂點的圖形E(見下圖)，就會發現圖形C的每個頂點皆為偶數頂點，所以它是一個擁有尤拉迴路規則的尤拉圖。
因此，只要科科和端端從入口處(也就是頂點A)開始規劃，不僅可以觀賞到所有的畫作，還不用走重複的路就能回到原本的入口處(參考路線見下圖五)，真是個有趣又省時的逛展路徑呢!
【學更多˙懂更多】
尤拉 (Leonhard Euler，1707~1783)
尤拉是有史以來瑞士最多產的科學家，也是一個不可思議的數學幻想家。他對數學的貢獻是全面性的，在任何領域都能發現數學，在任何情況都能進行研究，可被稱作為「百科全書型的數學家」
尤拉圖的由來
德國柯尼斯堡是一個有河流經的城市，在河的中心有兩個小島，小島與河的兩岸共有七條橋連接交通。有一天，有人問尤拉能否不重複路線、一次走完七座橋而回到出發點，於是在他一番研究之下，不僅圓滿解決問題，證明無法一次走完七座橋而不重複，更重要的是，他解決了一筆畫問題，在數學圖論史上發表第一篇重要文獻。
七橋之謎
按照尤拉的方式，先將七橋問題的圖形簡化(見下圖)，變成圖形F。
從圖形F可知，A、B、C、D四個頂點皆為「奇數頂點」，不是尤拉圖，無法一筆畫完成且不重複，所以七橋問題無解囉!
沒有留言:
張貼留言