前面我們介紹了有關(guān)動態(tài)規(guī)劃的相關(guān)內(nèi)容，相信大家也都有了一些收獲，下面我們學(xué)習(xí)的列車?yán)^續(xù)駛往“圖與網(wǎng)絡(luò)分析”的站點(diǎn)，在本次文章中我們將一起走近圖論的奠基人——?dú)W拉Leonhard Euler，希望能給大家學(xué)習(xí)運(yùn)籌學(xué)的旅程中帶來不一樣的感悟。

一、圖論的發(fā)展簡史及應(yīng)用

01圖論的誕生：哥尼斯堡七橋問題

?十八世紀(jì)，在今天俄羅斯加里寧格勒市還被稱為哥尼斯堡的年代。像其他許多大城市一樣，一條大河(普列戈利亞河)穿城而過。哥尼斯堡除了被一分為二以外，還包含河中的兩個島嶼，人們建有七座橋梁連接著不同的陸地。

當(dāng)時有一個著名的游戲謎題，就是在所有橋都只能走一遍的前提下，怎樣才能把這片區(qū)域所有的橋都走遍？

這個謎題成為當(dāng)?shù)厝艘豁?xiàng)熱衷的消遣運(yùn)動，許多人聲稱已經(jīng)找到了這樣一條路徑，但當(dāng)被要求按照規(guī)則再走一遍時，卻發(fā)現(xiàn)還是沒有人能夠做到。

直到1736年，瑞士數(shù)學(xué)家歐拉給出了答案，他在論文《The?seven bridges?of?K?nigsberg》中解釋了其中的原因，證明這樣的步行方式并不存在，并在文中提出和解決了一筆畫問題。歐拉對這一問題的詳細(xì)闡釋標(biāo)志著圖論的誕生，同時也對拓?fù)鋵W(xué)的思想起到了啟蒙作用。

02圖論的發(fā)展熱潮：漢密爾頓回路

1857年英國數(shù)學(xué)家漢密爾頓William Rowan Hamilton發(fā)明了“周游世界”玩具，用一個正十二面體的20個頂點(diǎn)表示世界上20個大城市，30條棱代表這些城市之間的道路。要求游戲者從任意一個城市(即頂點(diǎn))出發(fā)，延棱行走經(jīng)過每個城市一次且只經(jīng)過一次，最終返回出發(fā)地。漢密爾頓將此問題稱為“周游世界”問題，并且作了肯定的回答。以下是一種走法。

這個問題和哥尼斯堡七橋問題的不同之處在于，七橋問題是經(jīng)過每條邊一次，而漢密頓問題是經(jīng)過每個頂點(diǎn)一次。漢密頓問題尋找一條從給定的起點(diǎn)到給定的終點(diǎn)沿途恰好經(jīng)過所有其他城市一次的路徑。

用圖論的語言來說，游戲的目的是在十二面體的圖中找出一個生成圈。這個生成圈后來被稱為漢密爾頓回路，由此掀起了圖論研究的熱潮。

由于運(yùn)籌學(xué)、計算機(jī)科學(xué)和編碼理論中的很多問題都可以化為漢密爾頓問題，從而引起廣泛的注意和研究。

03圖論的推演：四色問題

四色問題是世界近代三大數(shù)學(xué)難題之一。最先是由一位叫格斯里（Francis Guthrie）的英國大學(xué)生提出來的。

1852年，畢業(yè)于倫敦大學(xué)的格斯里來到一家科研單位搞地圖著色工作時，發(fā)現(xiàn)每幅地圖都可以只用四種顏色著色。這個現(xiàn)象能不能從數(shù)學(xué)上加以嚴(yán)格證明呢？?

1852年10月23日，格斯里的弟弟就這個問題的證明請教了他的老師、著名數(shù)學(xué)家德·摩爾根Augustus De Morgan，摩爾根也沒能解決這個問題，于是寫信向自己的好友、著名數(shù)學(xué)家漢密爾頓William Rowan Hamilton爵士請教，但直到1865年漢密爾頓逝世為止，問題也沒有能夠解決。

1872年，英國當(dāng)時最著名的數(shù)學(xué)家凱利Cayley正式向倫敦數(shù)學(xué)學(xué)會提出了這個問題，于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問題。?

電子計算機(jī)問世以后，由于演算速度迅速提高，加之人機(jī)對話的出現(xiàn)，大大加快了對四色猜想證明的進(jìn)程。就在1976年6月，美國數(shù)學(xué)家阿佩爾Kenneth Appel和德國數(shù)學(xué)家哈肯Wolfgang Haken在美國伊利諾斯大學(xué)的兩臺不同的電子計算機(jī)上，用了1200個小時，作了100億個判斷，結(jié)果沒有一張地圖是需要五色的，最終證明了四色定理，轟動了世界。到目前為止，四色定理還只能靠計算機(jī)驗(yàn)證證明。

四色問題作為最著名和最具啟發(fā)性的圖論問題，如今仍有許多數(shù)學(xué)家在努力地追求，試圖從數(shù)學(xué)理論上證明。

一個多世紀(jì)以來，數(shù)學(xué)家們?yōu)樽C明這條定理絞盡腦汁，所引進(jìn)的概念與方法刺激了拓?fù)鋵W(xué)與圖論的生長、發(fā)展。在“四色問題”的研究過程中，不少新的數(shù)學(xué)理論隨之產(chǎn)生，也發(fā)展了很多數(shù)學(xué)計算技巧，極大得豐富了圖論的內(nèi)容。

04圖論的應(yīng)用

圖論是運(yùn)籌學(xué)的一個重要分支，它是建立和處理離散類數(shù)學(xué)模型的一個重要工具。用圖論的方法往往能幫助人們解決一些用其它方法難于解決的問題。由于這種數(shù)學(xué)模型和方法直觀形象，富有啟發(fā)性和趣味性，深受人們的青睞。到目前為止，已被廣泛地應(yīng)用于系統(tǒng)工程、通訊工程、計算機(jī)科學(xué)及經(jīng)濟(jì)領(lǐng)域。傳統(tǒng)的物理、化學(xué)、生命科學(xué)也越來越廣泛地使用了圖論模型方法。

二、圖論的奠基人——?dú)W拉

萊昂哈德·歐拉（Leonhard Euler，1707年4月15日～1783年9月18日），瑞士數(shù)學(xué)家、自然科學(xué)家。

生平紀(jì)事

歐拉1707年4月15日出生于瑞士的巴塞爾的牧師家庭，自幼受父親的影響。13歲時入讀巴塞爾大學(xué)，15歲大學(xué)畢業(yè)，16歲獲得碩士學(xué)位。

1725年，歐拉來到圣彼得堡，開始了他的數(shù)學(xué)生涯。1733年，年僅26歲的歐拉擔(dān)任了圣彼得堡科學(xué)院數(shù)學(xué)教授。過度的工作使他28歲得了眼病，右眼失明。1741年歐拉到柏林擔(dān)任科學(xué)院物理數(shù)學(xué)所所長。1766年，重回圣彼得堡任職。

沒過多久，左眼視力衰退，最后完全失明．不幸的事情接踵而來，1771年一場大火將他的書房和大量研究成果全部化為灰燼。沉重的打擊，仍然沒有使歐拉倒下．他以驚人的毅力，憑著記憶和心算進(jìn)行研究，直到逝世。

歐拉回路與圖論

哥尼斯堡七橋問題是18世紀(jì)著名古典數(shù)學(xué)問題之一。但在相當(dāng)長的時間里，沒有人能解出來。29歲的歐拉發(fā)表了《The?seven bridges?of?K?nigsberg》的論文，圓滿解決了這一問題，同時開創(chuàng)了數(shù)學(xué)新分支——圖論。

歐拉把七橋問題的實(shí)質(zhì)歸于“一筆畫”問題，即判斷一個圖是否能夠遍歷完所有的邊而沒有重復(fù)。很快他就判斷出要一次不重復(fù)走遍哥尼斯堡的7座橋是不可能的。也就是說，多少年來，讓無數(shù)人燒腦、試圖發(fā)現(xiàn)的不重復(fù)的路線，根本就不存在。一個號稱最燒腦且困擾無數(shù)人的難題，居然就是這樣的最簡單答案。

在論文中，歐拉將七橋問題抽象出來，得到歐拉回路關(guān)系：要使得一個圖形可以一筆畫，必須滿足如下兩個條件：1.圖形必須是連通的。2.圖中的“奇點(diǎn)”個數(shù)是0或2。（連到一點(diǎn)的數(shù)目如是奇數(shù)條，就稱為奇點(diǎn)）

大道至簡，歐拉天才地把一道著名古典數(shù)學(xué)難題簡化成一道小學(xué)生習(xí)題，并寫進(jìn)了小學(xué)課本，叫做“七橋問題”。七橋問題播下了圖論誕生與發(fā)展的種子。這門一開始以游戲形式出現(xiàn)，而且此后也一直沒有完全失去這一特點(diǎn)的數(shù)學(xué)分支，在20世紀(jì)得到迅速發(fā)展，已經(jīng)成為十分有用的重要數(shù)學(xué)分支。

歐拉與中國

歐拉的著作最初傳入中國，可追溯到大約250年前，由俄國傳教士帶進(jìn)來，并送給天主教的一個支派“耶穌會”在中國的機(jī)構(gòu)，曾收藏在北京天主教北堂的圖書館里。

然而，明、清年代中國數(shù)學(xué)已經(jīng)日漸衰落，裹足不前，遠(yuǎn)遠(yuǎn)落后于歐洲。大約在乾隆年間傳入中國的歐拉著作只能束之高閣，無人問津。

19世紀(jì)中葉，在李善蘭與英國傳教士合譯的《代微積拾級》，華蘅芳與美國傳教士傅蘭雅合譯的《微積溯源》中都介紹了歐拉和他的工作。中國人開始知道這位數(shù)學(xué)大家了，歐拉也登上了晚清人編寫的《疇人傳》。

清末民初，西方的先進(jìn)數(shù)學(xué)被引進(jìn)中國，大學(xué)里開設(shè)了“微積分”等課程，這才使得越來越多的中國人認(rèn)識了歐拉，學(xué)習(xí)他的數(shù)學(xué)。

大師評價

“Euler calculated without effort, just as men breathe, as eagles sustain themselves in the air.”——Francois Arago

歐拉計算起來輕松自如，就像人們呼吸，鷹在空中飛翔。（法國物理學(xué)家、天文學(xué)家阿拉戈）

?

“The study of Euler’s works will remain the best school for the different fields of mathematics, and nothing else can replace it.”——?Carl Friedrich Gauss

研究歐拉的著作永遠(yuǎn)是了解數(shù)學(xué)的最好方法。（德國著名數(shù)學(xué)家、物理學(xué)家、天文學(xué)家、幾何學(xué)家，大地測量學(xué)家卡爾·弗里德里?！じ咚梗?/span>

?

“Our students of mathematics would profit much more from a study of Euler's Introductio in Analysin Infinitorum, rather than of the available modern textbooks.”——André Weil

今天的學(xué)生從歐拉的《無窮分析引論》中所能獲得的益處, 是現(xiàn)代任何一本教科書都不能比擬的。（法國數(shù)學(xué)家安德烈·韋伊）

?

“Read Euler, read Euler, he is the master of us all.”——Pierre Simon Laplace

讀讀歐拉吧，他是我們所有人的導(dǎo)師。（法國數(shù)學(xué)家皮埃爾-西蒙·拉普拉斯）

?

歐拉可以說是所有學(xué)生的導(dǎo)師。不僅是因?yàn)槊恳粋€進(jìn)入學(xué)校接受教育的人，都要學(xué)習(xí)他所創(chuàng)造的數(shù)學(xué)知識；更是因?yàn)?，他那苦難而光輝的一生給后世無限的啟迪，教導(dǎo)人們?nèi)绾巫鋈耍绾巫鰧W(xué)問，如何生存。

讀到這里大家是不是對圖論的誕生和奠基人有了更深入的了解呢，下面就讓我們繼續(xù)探索圖論世界的其他內(nèi)容吧。

參考來源

http://ren.bytravel.cn/history/4/oula.html

https://www.sohu.com/a/286821764_120017399

https://tieba.baidu.com/p/2347936070