哥尼斯堡七橋問題課件

1、哥尼斯堡七橋問題知道一筆畫問題的提法掌握段道圖能否一筆畫的判斷方法會用添弧的方法求最優(yōu)解最優(yōu)投遞路線的求法教學(xué)目標(biāo)教學(xué)目標(biāo)重點和難點重點和難點3哥尼斯堡七橋問題 哥尼斯堡是位于波羅的海東岸一座古老而美麗的哥尼斯堡是位于波羅的海東岸一座古老而美麗的城市，布勒格爾河的兩條支流在這里匯合，然后橫貫城市，布勒格爾河的兩條支流在這里匯合，然后橫貫全城，流入大海。河心有一個小島。河水把城市分成全城，流入大海。河心有一個小島。河水把城市分成了塊，于是，人們建造了座各具特色的橋，把哥了塊，于是，人們建造了座各具特色的橋，把哥尼斯堡連成一體。尼斯堡連成一體。 一天又一天，座橋上走過了無數(shù)的行人。不知一天又一天，

2、座橋上走過了無數(shù)的行人。不知從什么時候起，腳下的橋梁觸發(fā)了人們的靈感，一個從什么時候起，腳下的橋梁觸發(fā)了人們的靈感，一個有趣的問題在居民中傳開了：有趣的問題在居民中傳開了：誰能夠一次走遍所有的誰能夠一次走遍所有的座橋，而且每座橋都只通過一次？座橋，而且每座橋都只通過一次？ 這個問題似乎不難，誰都樂意用它來測試一下自這個問題似乎不難，誰都樂意用它來測試一下自己的智力?？墒?，誰也沒有找到一條這樣的路線。以己的智力?？墒?，誰也沒有找到一條這樣的路線。以博學(xué)著稱的大學(xué)教授們，也感到一籌莫展。博學(xué)著稱的大學(xué)教授們，也感到一籌莫展。 七橋問七橋問題題 難住了哥尼斯堡的所有居民。哥尼斯堡也因難住了哥尼斯堡的

3、所有居民。哥尼斯堡也因 七橋七橋問題問題 而出了名。而出了名。 5歐拉的解法 哥尼斯堡七橋問題引起了大數(shù)學(xué)家歐拉的興趣。他知道，如果沿著所有可能的路線都走一次的話，一共要走5040次。就算是一天走一次，也需要13年多的時間。實際上，歐拉只用了幾天的時間就解決了七橋問題。 6 歐拉的想法是：兩岸的陸地與河中的小島，都是橋梁的連接點，它們的大小、形狀均與問題本身無關(guān)。因此，不妨把它們看作是4個點。7座橋是7條必須經(jīng)過的路線，它們的長短、曲直，也與問題本身無關(guān)。因此，不妨任意畫7條線來表示它們。就這樣，歐拉將七橋問題抽象成了一個“一筆畫”問題，從而否定了問題的答案。7七七 橋橋 問問 題題 哥尼斯堡

4、七橋哥尼斯堡七橋問題：如何不重復(fù)地走完七橋后回到起點？一筆畫問題一筆畫問題如何將此圖一筆畫出？歐拉的推理歐拉的推理 凡是一筆畫中出現(xiàn)的交點處，線一出一進(jìn)總凡是一筆畫中出現(xiàn)的交點處，線一出一進(jìn)總應(yīng)該通過偶數(shù)條（偶點），只有作為起點和終點應(yīng)該通過偶數(shù)條（偶點），只有作為起點和終點的兩點才有可能通過奇數(shù)條（奇點）。的兩點才有可能通過奇數(shù)條（奇點）。歐拉這種處理問題的方法標(biāo)志著圖論圖論的誕生 歐拉（L.Euler,1707.4.15- 1783.9.18）著名的數(shù)學(xué)家。生于瑞士的巴塞爾，卒于彼得堡。大部分時間在俄國和德國度過。他早年在數(shù)學(xué)天才貝努里賞識下開始學(xué)習(xí)數(shù)學(xué), 17歲獲得碩士學(xué)位，畢業(yè)后研究數(shù)

5、學(xué),是數(shù)學(xué)史上最高產(chǎn)的作家。在世發(fā)表論文700多篇,去世后還留下100多篇待發(fā)表。其論著幾乎涉及所有數(shù)學(xué)分支。 歐拉在數(shù)學(xué)、物理、天文、建筑以至音樂、哲學(xué)方面都取得了輝煌的成就。在數(shù)學(xué)的各個領(lǐng)域，常常見到以歐來命名的公式、定理、和重要常數(shù)。課本上常見的如、i、e、sin、cos、tg、x、f(x)等，都是他創(chuàng)立并推廣的。歐拉還首先完成了月球繞地球運動的精確理論，創(chuàng)立了分析力學(xué)、剛體力學(xué)等力學(xué)學(xué)科，深化了望遠(yuǎn)鏡、顯微鏡的設(shè)計計算理論。觀察下列圖形，完成統(tǒng)計表觀察下列圖形，完成統(tǒng)計表 圖7圖5圖1圖8圖6圖4圖3圖2可以一筆畫的圖形 不能一筆畫的圖形 圖形序號 奇點個數(shù)偶點個數(shù)圖形序號 奇點個數(shù)偶

6、點個數(shù)不連通的圖形不能一筆畫不連通的圖形不能一筆畫 連通的圖連通的圖形形有可能有可能一筆畫一筆畫 全都是偶點的連全都是偶點的連通圖可以一筆畫通圖可以一筆畫 奇點個數(shù)超過兩個的連通圖奇點個數(shù)超過兩個的連通圖形不能一筆畫形不能一筆畫 畫時以任一點為起點，最后仍回畫時以任一點為起點，最后仍回到該點到該點 畫時以一個奇點為起點，另一個畫時以一個奇點為起點，另一個奇點為終點奇點為終點有兩個奇點的連有兩個奇點的連通圖可以一筆畫通圖可以一筆畫 歐拉回路 經(jīng)過圖中經(jīng)過圖中所有邊所有邊一次，且訪問每個頂點一次，且訪問每個頂點至少至少一一次的一個次的一個回路回路，稱為歐拉回路。，稱為歐拉回路。 具有歐拉回路的圖稱

7、為具有歐拉回路的圖稱為歐拉圖歐拉圖。 注意：通過圖中所有邊一次且僅一次行遍所有通過圖中所有邊一次且僅一次行遍所有頂點的通路稱為歐拉通路。頂點的通路稱為歐拉通路。判斷下列圖形能否一筆畫判斷下列圖形能否一筆畫圖5圖4圖3圖2圖6圖1下圖是一個公園的平面圖，要使游人走遍每一條路不重復(fù)，出口和入口應(yīng)設(shè)在哪兒？中國郵遞員問題中國郵遞員問題 中國郵遞員問題中國郵遞員問題( (Chinese Postman Problem, Chinese Postman Problem, CPPCPP) )是由我國管梅谷教授于是由我國管梅谷教授于19621962年首先提出并年首先提出并發(fā)表的發(fā)表的 例如：觀察下列段道圖例

8、如：觀察下列段道圖 從郵局出發(fā)，走遍郵區(qū)的所有街道至少從郵局出發(fā)，走遍郵區(qū)的所有街道至少一次再回到郵局，按照什么樣的路線投一次再回到郵局，按照什么樣的路線投遞郵件才能使總的路程最短？遞郵件才能使總的路程最短？圖（1）圖（2） 投遞路線 一筆畫 歐拉回路 最理想的投遞路線，就是該段道圖是一條歐拉回路。圖最理想的投遞路線，就是該段道圖是一條歐拉回路。圖（2 2）的投遞路線如下圖（）的投遞路線如下圖（3 3）。）。 含有奇點的段道圖不能一筆畫出，有些道路需要重復(fù)走含有奇點的段道圖不能一筆畫出，有些道路需要重復(fù)走兩次的都要添上一條弧。圖（兩次的都要添上一條弧。圖（1 1）添弧后如圖（）添弧后如圖（4 4）。）。圖（3）圖（4） 定理定理1 1 一個能夠不重復(fù)的一筆畫出的連通圖中一個能夠不重復(fù)的一筆畫出的連通圖中，所以的點一定都是偶點。，所以的點一定都是偶點。 定理定理2 2 沒有奇點的連通圖一定能夠從任意一點沒有奇點