哥尼斯堡七橋問題和歐拉回路課件

知道一筆畫問題的提法掌握段道圖能否一筆畫的判斷方法會(huì)用添弧的方法求最優(yōu)解最優(yōu)投遞路線的求法教學(xué)目標(biāo)重點(diǎn)和難點(diǎn)6.4.1哥尼斯堡七橋問題BDACABCD哥尼斯堡七橋問題：如何不重復(fù)地走完七橋后回到起點(diǎn)？一筆畫問題如何將此圖一筆畫出？歐拉的推理

凡是一筆畫中出現(xiàn)的交點(diǎn)處，線一出一進(jìn)總應(yīng)該通過偶數(shù)條（偶點(diǎn)），只有作為起點(diǎn)和終點(diǎn)的兩點(diǎn)才有可能通過奇數(shù)條（奇點(diǎn)）。

結(jié)論：凡是奇點(diǎn)個(gè)數(shù)多于兩個(gè)的平面圖都不能一筆畫出。

七橋問題中有四個(gè)奇點(diǎn)，故不能一筆畫出歐拉這種處理問題的方法標(biāo)志著圖論的誕生6.4.2歐拉和歐拉回路歐拉

歐拉（L.Euler,1707.4.15-1783.9.18）著名的數(shù)學(xué)家。生于瑞士的巴塞爾，卒于彼得堡。大部分時(shí)間在俄國和德國度過。他早年在數(shù)學(xué)天才貝努里賞識(shí)下開始學(xué)習(xí)數(shù)學(xué),17歲獲得碩士學(xué)位，畢業(yè)后研究數(shù)學(xué),是數(shù)學(xué)史上最高產(chǎn)的作家。在世發(fā)表論文700多篇,去世后還留下100多篇待發(fā)表。其論著幾乎涉及所有數(shù)學(xué)分支。歐拉在數(shù)學(xué)、物理、天文、建筑以至音樂、哲學(xué)方面都取得了輝煌的成就。在數(shù)學(xué)的各個(gè)領(lǐng)域，常常見到以歐來命名的公式、定理、和重要常數(shù)。課本上常見的如π、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ì)算理論。關(guān)鍵詞：驚人的記憶力杰出的智慧頑強(qiáng)的毅力孜孜不倦的奮斗精神高尚的科學(xué)道德歐拉回路經(jīng)過圖中所有邊一次，且訪問每個(gè)頂點(diǎn)至少一次的一個(gè)回路，稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。

注意：通過圖中所有邊一次且僅一次行遍所有頂點(diǎn)的通路稱為歐拉通路。具有歐拉通路而無歐拉回路的圖稱為半歐拉圖。例1：下列平面圖哪些能一筆畫出，哪些不可以？哪些有歐拉回路？6.4.3中國郵遞員問題中國郵遞員問題(ChinesePostmanProblem,CPP)是由我國管梅谷教授于1962年首先提出并發(fā)表的例如：觀察下列段道圖

：從郵局出發(fā)，走遍郵區(qū)的所有街道至少一次再回到郵局，按照什么樣的路線投遞郵件才能使總的路程最短？圖（1）圖（2）問題

投遞路線一筆畫歐拉回路

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

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

例2：找出下列段道圖的最優(yōu)解333322211334

先分奇偶點(diǎn)，奇點(diǎn)對(duì)對(duì)連；連線不重疊，重疊要改變；圈上連線長，不得過半圈。

先分奇偶點(diǎn)，奇點(diǎn)對(duì)對(duì)連；連線不重疊，重疊要改變；圈上連線長，不得過半圈。33321

先分奇偶點(diǎn)，奇點(diǎn)對(duì)對(duì)連；連線不重疊，重疊要改變；圈上連線長，不得過半圈。33223最優(yōu)解

先分奇偶點(diǎn)，奇點(diǎn)對(duì)對(duì)連；連線不重疊，重疊要改變；圈上連線長，不得過半圈。