一筆畫問題.ppt

哥尼斯堡七橋問題(1/18) 歐洲的普瑞格爾河(Pregel River)流過東普魯士(East Prussia)的古城哥尼斯堡(Konigsberg)市中心，河中有兩座島，築有七座古橋，每逢節假日，市民們紛紛上島，扶老攜幼，遊玩散步。 哥尼斯堡七橋問題(2/18) 不知何日何人提出如下的智力問題：請走過每座橋恰一次，再返回出發點。 反覆的奔走與失敗，使人們不知其所以然地猜想其答案是否定的。 哥尼斯堡七橋問題(3/18) 1736 年，年29 的數學家尤拉(Euler, 1707-1783)嚴格地證明了哥尼斯堡七橋問題無解，並且由此開創了圖論的典型思維及論證方式 1736 年被公認為圖論元年。 哥尼斯堡七橋問題(4/18) 七橋問題無解，關鍵在於與同一地點相通的橋之數量是奇數。 一筆畫問題(5/18) 把一枝筆的筆尖看成是沿路徑散步的人，筆尖沿圖形走所留下的痕跡就是這個人走的路線，那麼七橋問題就可以看成“對這樣一個封閉的圖形，是否可以一筆畫完成它”。 一筆畫問題(6/18) 網絡：由有限條線段所組成的圖形，每條線段都有兩個相異的端點，這些線段稱為弧，這些端點稱為頂點，這些線段只在端點處有交集。 網絡中，互相銜接的一串弧稱為一條路徑。(這些弧不重複，每條弧都一個端點與另一條弧連接) 一條路徑的起點等於終點，稱為一條封閉的路徑。 一條封閉的路徑所經過的端點都不重複，稱為一個圈。 一筆畫問題(7/18) (a, d, e, g) ：一條路徑。 (a, b, c, e, g, d, f) ：一條封閉的路徑。 (a, d, e, h)是一個圈。 一筆畫問題(8/18) 一筆畫問題(9/18) 一筆畫問題相當於：給定一個網絡，有沒有可能將所有的弧排成一條路徑（尤拉路徑(Euler path) ）。 要求一筆畫完成後又回到原出發點相當於：要求把全部的弧排成一條封閉的路徑（封閉的尤拉路徑、尤拉環/尤拉環道(Euler circuit) ）。 一筆畫問題(10/18) 一筆畫問題(11/18) 如果一個網絡的任意二個頂點都可以用一條路徑連接起來，就稱之為連通的，反之稱為不連通的。 一筆畫問題(12/18) 頂點的弧數為奇數，稱為奇頂點。 頂點的弧數為偶數，稱為偶頂點。 一筆畫定理︰一個網絡是一筆畫的充份且必要的條件是：它是連通的，且奇頂點的個數等於0 或2。(0︰有尤拉路徑且有尤拉環 2：有尤拉路徑但沒有尤拉環) 一筆畫問題(18/18) 這樣的圖形呢？ 路徑 封閉的路徑 圈 尤拉路徑 尤拉環 一筆畫問題(13/18) 2 2 3 2 3 2 3 3 3 3 3 3 3 3 6 存在一個尤拉路徑 4 4 4 存在一個尤拉路徑 沒有尤拉路徑 一筆畫問題(14/18) 下圖是一筆畫圖形嗎？ A B 一筆畫問題(15/18) 這樣的圖形呢？ A B 一筆畫問題(16/18) A B 這樣的圖形呢？