哥尼斯堡七橋問(wèn)題學(xué)習(xí)資料課件

哥尼斯堡七橋問(wèn)題哥尼斯堡七橋問(wèn)題1知道一筆畫(huà)問(wèn)題的提法掌握段道圖能否一筆畫(huà)的判斷方法會(huì)用添弧的方法求最優(yōu)解最優(yōu)投遞路線的求法教學(xué)目標(biāo)重點(diǎn)和難點(diǎn)知道一筆畫(huà)問(wèn)題的提法教學(xué)目標(biāo)重點(diǎn)和難點(diǎn)2哥尼斯堡七橋問(wèn)題學(xué)習(xí)資料課件3哥尼斯堡七橋問(wèn)題學(xué)習(xí)資料課件45歐拉的解法

哥尼斯堡七橋問(wèn)題引起了大數(shù)學(xué)家歐拉的興趣。他知道，如果沿著所有可能的路線都走一次的話，一共要走5040次。就算是一天走一次，也需要13年多的時(shí)間。實(shí)際上，歐拉只用了幾天的時(shí)間就解決了七橋問(wèn)題。

5歐拉的解法哥尼斯堡七橋問(wèn)題引起了大數(shù)學(xué)56

歐拉的想法是：兩岸的陸地與河中的小島，都是橋梁的連接點(diǎn)，它們的大小、形狀均與問(wèn)題本身無(wú)關(guān)。因此，不妨把它們看作是4個(gè)點(diǎn)。7座橋是7條必須經(jīng)過(guò)的路線，它們的長(zhǎng)短、曲直，也與問(wèn)題本身無(wú)關(guān)。因此，不妨任意畫(huà)7條線來(lái)表示它們。就這樣，歐拉將七橋問(wèn)題抽象成了一個(gè)“一筆畫(huà)”問(wèn)題，從而否定了問(wèn)題的答案。6歐拉的想法是：兩岸的陸地與河中的小島，67七橋問(wèn)題

哥尼斯堡七橋問(wèn)題：如何不重復(fù)地走完七橋后回到起點(diǎn)？一筆畫(huà)問(wèn)題如何將此圖一筆畫(huà)出？7七橋問(wèn)題哥尼斯堡七橋一筆畫(huà)問(wèn)題7歐拉的推理

凡是一筆畫(huà)中出現(xiàn)的交點(diǎn)處，線一出一進(jìn)總應(yīng)該通過(guò)偶數(shù)條（偶點(diǎn)），只有作為起點(diǎn)和終點(diǎn)的兩點(diǎn)才有可能通過(guò)奇數(shù)條（奇點(diǎn)）。歐拉這種處理問(wèn)題的方法標(biāo)志著圖論的誕生歐拉的推理凡是一筆畫(huà)中出現(xiàn)的交點(diǎn)處，線一出一進(jìn)總歐8

歐拉（L.Euler,1707.4.15-1783.9.18）著名的數(shù)學(xué)家。生于瑞士的巴塞爾，卒于彼得堡。大部分時(shí)間在俄國(guó)和德國(guó)度過(guò)。他早年在數(shù)學(xué)天才貝努里賞識(shí)下開(kāi)始學(xué)習(xí)數(shù)學(xué),17歲獲得碩士學(xué)位，畢業(yè)后研究數(shù)學(xué),是數(shù)學(xué)史上最高產(chǎn)的作家。在世發(fā)表論文700多篇,去世后還留下100多篇待發(fā)表。其論著幾乎涉及所有數(shù)學(xué)分支。歐拉（L.Euler,179歐拉在數(shù)學(xué)、物理、天文、建筑以至音樂(lè)、哲學(xué)方面都取得了輝煌的成就。在數(shù)學(xué)的各個(gè)領(lǐng)域，常常見(jiàn)到以歐來(lái)命名的公式、定理、和重要常數(shù)。課本上常見(jiàn)的如π、i、e、sin、cos、tg、△x、Σ、f(x)等，都是他創(chuàng)立并推廣的。歐拉還首先完成了月球繞地球運(yùn)動(dòng)的精確理論，創(chuàng)立了分析力學(xué)、剛體力學(xué)等力學(xué)學(xué)科，深化了望遠(yuǎn)鏡、顯微鏡的設(shè)計(jì)計(jì)算理論。歐拉在數(shù)學(xué)、物理、天文、建筑以至音樂(lè)、哲學(xué)方面都取得了輝煌的10觀察下列圖形，完成統(tǒng)計(jì)表圖7圖5圖1圖8圖6圖4圖3圖2可以一筆畫(huà)的圖形不能一筆畫(huà)的圖形圖形序號(hào)奇點(diǎn)個(gè)數(shù)偶點(diǎn)個(gè)數(shù)

圖形序號(hào)奇點(diǎn)個(gè)數(shù)偶點(diǎn)個(gè)數(shù)

觀察下列圖形，完成統(tǒng)計(jì)表圖7圖5圖1圖8圖6圖4圖3圖2可11不連通的圖形不能一筆畫(huà)

連通的圖形有可能一筆畫(huà)全都是偶點(diǎn)的連通圖可以一筆畫(huà)

奇點(diǎn)個(gè)數(shù)超過(guò)兩個(gè)的連通圖形不能一筆畫(huà)畫(huà)時(shí)以任一點(diǎn)為起點(diǎn)，最后仍回到該點(diǎn)畫(huà)時(shí)以一個(gè)奇點(diǎn)為起點(diǎn)，另一個(gè)奇點(diǎn)為終點(diǎn)有兩個(gè)奇點(diǎn)的連通圖可以一筆畫(huà)

不連通的圖形不能一筆畫(huà)連通的圖形有可能一筆畫(huà)全都是偶點(diǎn)的12歐拉回路

經(jīng)過(guò)圖中所有邊一次，且訪問(wèn)每個(gè)頂點(diǎn)至少一次的一個(gè)回路，稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。

注意：通過(guò)圖中所有邊一次且僅一次行遍所有頂點(diǎn)的通路稱為歐拉通路。歐拉回路經(jīng)過(guò)圖中所有邊一次，且訪問(wèn)每個(gè)頂點(diǎn)至少13判斷下列圖形能否一筆畫(huà)圖5圖4圖3圖2圖6圖1判斷下列圖形能否一筆畫(huà)圖5圖4圖3圖2圖6圖114下圖是一個(gè)公園的平面圖，要使游人走遍每一條路不重復(fù)，出口和入口應(yīng)設(shè)在哪兒？下圖是一個(gè)公園的平面圖，要使游人走遍每一條路不重復(fù)，出口和入15中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題(ChinesePostmanProblem,CPP)是由我國(guó)管梅谷教授于1962年首先提出并發(fā)表的例如：觀察下列段道圖

從郵局出發(fā)，走遍郵區(qū)的所有街道至少

一次再回到郵局，按照什么樣的路線投

遞郵件才能使總的路程最短？圖（1）圖（2）中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題(ChinesePostman16

投遞路線一筆畫(huà)歐拉回路

最理想的投遞路線，就是該段道圖是一條歐拉回路。圖（2）的投遞路線如下圖（3）。

含有奇點(diǎn)的段道圖不能一筆畫(huà)出，有些道路需要重復(fù)走兩次的都要添上一條弧。圖（1）添弧后如圖（4）。圖（3）圖（4）投遞路線一筆畫(huà)17定理1一個(gè)能夠不重復(fù)的一筆畫(huà)出的連通圖中，所以的點(diǎn)一定都是偶點(diǎn)。定理2沒(méi)有奇點(diǎn)的連通圖一定能夠從任意一點(diǎn)開(kāi)始不重復(fù)的一筆畫(huà)出。最優(yōu)投遞路線重復(fù)的路最短添弧的總長(zhǎng)度最短添弧最短的條件（1）沒(méi)有重疊的添?。?）每一個(gè)圈上添弧的總長(zhǎng)度不超過(guò)圈長(zhǎng)的一半最短的一組添弧稱為最優(yōu)解。

定理1一個(gè)能夠不重復(fù)的一筆畫(huà)出的連通圖中，所以的點(diǎn)一定都18案例：西北大學(xué)的灑水車要給主要路面灑水，該如何確定行車路線？案例：西北大學(xué)的灑水車要給主要路面灑水，該如何確定行車路線？19灑水車要給主要路面灑水，也就意味著行車路線必需經(jīng)過(guò)圖示所有的路面至少一次。這類似于郵路問(wèn)題。類似的還有送奶工送奶問(wèn)題。灑水車要給主要路面灑水，也就意味著行車路線必需經(jīng)過(guò)圖示所有的20哥尼斯堡七橋問(wèn)題哥尼斯堡七橋問(wèn)題21知道一筆畫(huà)問(wèn)題的提法掌握段道圖能否一筆畫(huà)的判斷方法會(huì)用添弧的方法求最優(yōu)解最優(yōu)投遞路線的求法教學(xué)目標(biāo)重點(diǎn)和難點(diǎn)知道一筆畫(huà)問(wèn)題的提法教學(xué)目標(biāo)重點(diǎn)和難點(diǎn)22哥尼斯堡七橋問(wèn)題學(xué)習(xí)資料課件23哥尼斯堡七橋問(wèn)題學(xué)習(xí)資料課件2425歐拉的解法

哥尼斯堡七橋問(wèn)題引起了大數(shù)學(xué)家歐拉的興趣。他知道，如果沿著所有可能的路線都走一次的話，一共要走5040次。就算是一天走一次，也需要13年多的時(shí)間。實(shí)際上，歐拉只用了幾天的時(shí)間就解決了七橋問(wèn)題。

5歐拉的解法哥尼斯堡七橋問(wèn)題引起了大數(shù)學(xué)2526

歐拉的想法是：兩岸的陸地與河中的小島，都是橋梁的連接點(diǎn)，它們的大小、形狀均與問(wèn)題本身無(wú)關(guān)。因此，不妨把它們看作是4個(gè)點(diǎn)。7座橋是7條必須經(jīng)過(guò)的路線，它們的長(zhǎng)短、曲直，也與問(wèn)題本身無(wú)關(guān)。因此，不妨任意畫(huà)7條線來(lái)表示它們。就這樣，歐拉將七橋問(wèn)題抽象成了一個(gè)“一筆畫(huà)”問(wèn)題，從而否定了問(wèn)題的答案。6歐拉的想法是：兩岸的陸地與河中的小島，2627七橋問(wèn)題

哥尼斯堡七橋問(wèn)題：如何不重復(fù)地走完七橋后回到起點(diǎn)？一筆畫(huà)問(wèn)題如何將此圖一筆畫(huà)出？7七橋問(wèn)題哥尼斯堡七橋一筆畫(huà)問(wèn)題27歐拉的推理

凡是一筆畫(huà)中出現(xiàn)的交點(diǎn)處，線一出一進(jìn)總應(yīng)該通過(guò)偶數(shù)條（偶點(diǎn)），只有作為起點(diǎn)和終點(diǎn)的兩點(diǎn)才有可能通過(guò)奇數(shù)條（奇點(diǎn)）。歐拉這種處理問(wèn)題的方法標(biāo)志著圖論的誕生歐拉的推理凡是一筆畫(huà)中出現(xiàn)的交點(diǎn)處，線一出一進(jìn)總歐28

歐拉（L.Euler,1707.4.15-1783.9.18）著名的數(shù)學(xué)家。生于瑞士的巴塞爾，卒于彼得堡。大部分時(shí)間在俄國(guó)和德國(guó)度過(guò)。他早年在數(shù)學(xué)天才貝努里賞識(shí)下開(kāi)始學(xué)習(xí)數(shù)學(xué),17歲獲得碩士學(xué)位，畢業(yè)后研究數(shù)學(xué),是數(shù)學(xué)史上最高產(chǎn)的作家。在世發(fā)表論文700多篇,去世后還留下100多篇待發(fā)表。其論著幾乎涉及所有數(shù)學(xué)分支。歐拉（L.Euler,1729歐拉在數(shù)學(xué)、物理、天文、建筑以至音樂(lè)、哲學(xué)方面都取得了輝煌的成就。在數(shù)學(xué)的各個(gè)領(lǐng)域，常常見(jiàn)到以歐來(lái)命名的公式、定理、和重要常數(shù)。課本上常見(jiàn)的如π、i、e、sin、cos、tg、△x、Σ、f(x)等，都是他創(chuàng)立并推廣的。歐拉還首先完成了月球繞地球運(yùn)動(dòng)的精確理論，創(chuàng)立了分析力學(xué)、剛體力學(xué)等力學(xué)學(xué)科，深化了望遠(yuǎn)鏡、顯微鏡的設(shè)計(jì)計(jì)算理論。歐拉在數(shù)學(xué)、物理、天文、建筑以至音樂(lè)、哲學(xué)方面都取得了輝煌的30觀察下列圖形，完成統(tǒng)計(jì)表圖7圖5圖1圖8圖6圖4圖3圖2可以一筆畫(huà)的圖形不能一筆畫(huà)的圖形圖形序號(hào)奇點(diǎn)個(gè)數(shù)偶點(diǎn)個(gè)數(shù)

圖形序號(hào)奇點(diǎn)個(gè)數(shù)偶點(diǎn)個(gè)數(shù)

觀察下列圖形，完成統(tǒng)計(jì)表圖7圖5圖1圖8圖6圖4圖3圖2可31不連通的圖形不能一筆畫(huà)

連通的圖形有可能一筆畫(huà)全都是偶點(diǎn)的連通圖可以一筆畫(huà)

奇點(diǎn)個(gè)數(shù)超過(guò)兩個(gè)的連通圖形不能一筆畫(huà)畫(huà)時(shí)以任一點(diǎn)為起點(diǎn)，最后仍回到該點(diǎn)畫(huà)時(shí)以一個(gè)奇點(diǎn)為起點(diǎn)，另一個(gè)奇點(diǎn)為終點(diǎn)有兩個(gè)奇點(diǎn)的連通圖可以一筆畫(huà)

不連通的圖形不能一筆畫(huà)連通的圖形有可能一筆畫(huà)全都是偶點(diǎn)的32歐拉回路

經(jīng)過(guò)圖中所有邊一次，且訪問(wèn)每個(gè)頂點(diǎn)至少一次的一個(gè)回路，稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。

注意：通過(guò)圖中所有邊一次且僅一次行遍所有頂點(diǎn)的通路稱為歐拉通路。歐拉回路經(jīng)過(guò)圖中所有邊一次，且訪問(wèn)每個(gè)頂點(diǎn)至少33判斷下列圖形能否一筆畫(huà)圖5圖4圖3圖2圖6圖1判斷下列圖形能否一筆畫(huà)圖5圖4圖3圖2圖6圖134下圖是一個(gè)公園的平面圖，要使游人走遍每一條路不重復(fù)，出口和入口應(yīng)設(shè)在哪兒？下圖是一個(gè)公園的平面圖，要使游人走遍每一條路不重復(fù)，出口和入35中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題(ChinesePostmanProblem,CPP)是由我國(guó)管梅谷教授于1962年首先提出并發(fā)表的例如：觀察下列段道圖

從郵局出發(fā)，走遍郵區(qū)的所有街道至少

一次再回到郵局，按照什么樣的路線投

遞郵件才能使總的路程最短？圖（1）圖（2）中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題(ChinesePostman36

投遞路線一筆畫(huà)歐拉回路

最理想的投遞路線，就是該段道圖是一條歐拉回路。圖（2）的投遞路線如下圖（3）。

含有奇點(diǎn)的段道圖不能一筆畫(huà)出，有些道路需要重復(fù)走兩次的都要添上一條弧。圖（1）添弧后如圖（4）。圖（3）圖（4）投遞路線一筆畫(huà)37定理1一個(gè)能夠不重復(fù)的一筆畫(huà)出的連通圖中，所以的點(diǎn)一定都是偶點(diǎn)。定理2沒(méi)有奇點(diǎn)的連通圖一定能夠從任意一點(diǎn)開(kāi)始不重復(fù)的一筆畫(huà)出。最優(yōu)投遞路線重復(fù)的路最短添弧的總長(zhǎng)度最短添弧最短