資源描述：
《七橋問題探究.pptx》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。
1、七橋問題探究目錄七橋問題的產(chǎn)生七橋問題的復雜歐拉與歐拉的解七橋問題的解小結七橋問題的產(chǎn)生18世紀，位于現(xiàn)立陶宛內(nèi)的哥尼斯堡鎮(zhèn)，一條河流叫普雷格爾河穿鎮(zhèn)而過，河中有兩個相鄰的小島，島與島、島與陸地之間建有七座橋（如圖，A、B為島嶼，C、D為兩岸。）當時哥尼斯堡的居民經(jīng)常到河邊散步，或者到島上買東西，有人提出了一個問題：一個人能否一次無重復地走遍所有的七座橋，最后回到出發(fā)點？當時，對這個問題誰也回答不了，這就是著名的“七橋問題”。聰明的你們能不能解答這個問題呢？七橋問題的復雜——走法……………………7…………
2、……6…………………5…………………4………………………3…………………………2…………………………11234567437657645765767七橋問題的復雜關鍵在于它的走法太多，右圖只是示例，因為太過于復雜，在這里就不一一列舉了，從樹狀圖中我們可以知道至少有754321=5040種走法。那哪一種走法才符合條件呢？歐拉萊昂哈德·歐拉（LeonhardEuler，1707年4月15日～1783年9月18日），瑞士數(shù)學家、自然科學家。1707年4月15日出生于瑞士的巴塞爾，1783年9月18日于俄國圣彼得堡
3、去世。歐拉是18世紀數(shù)學界最杰出的人物之一，他不但為數(shù)學界作出貢獻，更把整個數(shù)學推至物理的領域。1736年，一位小學教師寫信給當時著名的數(shù)學家歐拉，請教對七橋問題的解答，這個問題引起了歐拉的極大興趣，他用數(shù)學方法對七橋問題進行了深入的研究。歐拉的解答——一筆畫問題歐拉發(fā)現(xiàn)該問題不是一個代數(shù)問題，也不是一個平面幾何問題。該問題的解決僅依賴與陸地、島嶼、橋梁等的具體個數(shù)及其相互位置關系，因此可以把陸地看成“點”，將橋梁看作“線”（如下圖的數(shù)學模型）。按照歐拉的思想，七橋問題就轉(zhuǎn)化為以下問題：一筆畫問題：能否從
4、圖上某一點開始，筆不離紙、不重復的畫出整個圖形？我們知道，數(shù)學上把下圖形稱為一個圖(graph)，其中的點稱為頂點，線稱為邊，頂點集記為V，一個頂點記為v，邊的集合記為E，一條邊記為e。如果n條邊e?、e?、e?、……en首尾相連組成一個序列，其中ei鏈接頂點vi和vi+1（i=1，2，3，……n）稱該序列為從端點v1到端點vn+1的鏈長為n的鏈。如果一個圖的任意兩頂點之間都有鏈相連，則稱為連通圖。把一個頂點v處引出邊的條數(shù)叫做該頂點v的次數(shù)，頂點次數(shù)為奇（偶）數(shù)的頂點叫奇（偶）點。為了更好地理解，用右圖
5、作說明，A、B、C、D為頂點，且任意兩頂點之間都有鏈相連，所以很明顯右圖是連通圖。根據(jù)概念可知，A、B、C、D均為奇點（A點引出了5條邊，B、C、D引出了3條邊）。我們也可以從此圖中推出，所有頂點的次數(shù)總和必然是偶數(shù)，且在奇點處，必然有一條只進不出或只出不進的邊（如右圖中BD線沒有進出與之對應），因而奇點的個數(shù)必為偶數(shù)。右圖也是一個連通圖，且A、B、C均為偶點。我們可以看到，在偶點處邊線有進有出，進出對應?；诖?，歐拉給出了如下的一筆畫定理。定理1：一個圖是一筆畫的充要條件是：圖形是連通的，并且奇點的個數(shù)
6、為0或2.同學們能不能根據(jù)下圖分析一下奇點為0和奇點為2時的特點。AAB上圖沒有奇點，從任意一頂點（A）出發(fā)，最終也會到了那一頂點，且路線不會重復。上圖有兩個奇點（A、B），你會發(fā)現(xiàn)只有從一個奇點出發(fā)到另一個奇點終止，才能不重復的走完路線。定理2：當奇點個數(shù)為2時，一個奇點為起點，另一個則為終點；當奇點個數(shù)為0時，任取一個頂點，它是起點，也是終點。七橋問題的解講到這里，大家是不是已經(jīng)知道七橋問題的解了呢？現(xiàn)在，請大家看一下下面的圖形，你們能不重復地走完全部路線嗎？沒錯，這個圖根本就無法不重復地走完全部路線
7、，原因在于它的奇點個數(shù)有四個，就意味著要想不重復，無論怎么走，最終都有兩段是沒走過的，這與七橋問題是一樣的，所以我們可以知道，七橋問題其實是沒有解的。小結歐拉一筆畫定理：定理1：一個圖是一筆畫的充要條件是：圖形是連通的，并且奇點的個數(shù)為0或2.定理2：當奇點個數(shù)為2時，一個奇點為起點，另一個則為終點；當奇點個數(shù)為0時，任取一個頂點，它是起點，也是終點。讀讀歐拉，讀讀歐拉，他是我們大家的老師?！绽?/p>
