圖論的發(fā)展及其在現(xiàn)實(shí)生活中的幾個(gè)應(yīng)用

1、菏澤學(xué)院本科生畢業(yè)設(shè)計(jì)（論文）1圖論的發(fā)展及其在生活中的應(yīng)用數(shù)學(xué)與應(yīng)用數(shù)學(xué)張佳麗指導(dǎo)教師劉秀麗摘要摘要主要介紹了圖論的起源與發(fā)展及其生活中的若干應(yīng)用，如：渡河問(wèn)題、旅游推銷(xiāo)員問(wèn)題、最小生成樹(shù)問(wèn)題、四色問(wèn)題、安排問(wèn)題、中國(guó)郵遞員問(wèn)題。同時(shí)也涉及到了幾種在圖論中應(yīng)用比較廣泛的方法，如：最鄰近法、求最小生成樹(shù)的方法、求最優(yōu)路線的方法等。關(guān)鍵詞關(guān)鍵詞圖論生活問(wèn)題應(yīng)用GraphTheyDevelopmenttheApplicationinLife

2、MathematicsappliedmathematicsZhangJialiTutLiuXiuliAbstractThispapermainlyintroducestheigindevelopmentofgraphtheyitsseveralapplicationsinourlifesuchas:crossingriverproblemtravelingsalesmanproblemminimumspanningtreeproblem

3、fourcolproblem，arrangementproblem，ChinesepostmanproblemItalsoresearchesseveralmethodsthataremewidelyappliedingraphtheyfexample:themethodofmostneighbingthemethodofsolvingtheminimumspanningtree，themethodofthebestroute，soon

4、Keywdsgraphtheylifeproblemapplication引言圖論是一門(mén)古老的學(xué)科，是數(shù)學(xué)中有廣泛應(yīng)用的一個(gè)分支，與其他的數(shù)學(xué)分支，如群論、矩陣論、概率論、拓?fù)鋵W(xué)、數(shù)分析等有著密切的聯(lián)系圖論中以圖為研究對(duì)象，圖形中我們用點(diǎn)表示對(duì)象，兩點(diǎn)之間的連線表示對(duì)象之間的某種特定的關(guān)系事實(shí)上，任何一個(gè)包含了二元關(guān)系的系統(tǒng)都可以用圖論來(lái)模擬而且圖論能把紛雜的信息變的有序、直觀、清晰由于我們感興趣的是兩對(duì)象之間是否有某種特定關(guān)系，所以圖

5、形中兩點(diǎn)間連接與否尤為重要，而圖形的位置、大小、形狀及連接線的曲直長(zhǎng)短則無(wú)關(guān)緊要圖論在自然科學(xué)、社會(huì)科學(xué)等各個(gè)領(lǐng)域都有廣泛的應(yīng)用隨著科學(xué)的發(fā)展，以及生產(chǎn)管理、軍事、交通運(yùn)輸?shù)确矫嫣岢隽舜罅繉?shí)際的需要，圖論的理論及其應(yīng)用研究得到飛速發(fā)展。從20世紀(jì)50年代以后，由于計(jì)算機(jī)的迅速發(fā)展，有力地推動(dòng)了圖論的發(fā)展，加速了圖論向各個(gè)學(xué)科的滲透，尤其是網(wǎng)絡(luò)理論的建立，圖論與線性規(guī)劃、菏澤學(xué)院本科生畢業(yè)設(shè)計(jì)（論文）3問(wèn)題”難住了哥尼斯堡城的所有居民哥尼

6、斯堡城也因“七橋問(wèn)題”而出了名這就是數(shù)學(xué)史上著名的七橋問(wèn)題問(wèn)題看來(lái)并不復(fù)雜，但就是誰(shuí)也解決不了，也說(shuō)不出所以然來(lái)1736年，當(dāng)時(shí)著名的數(shù)學(xué)家歐拉仔細(xì)研究了這個(gè)問(wèn)題，他將上述四塊陸地與七座橋間的關(guān)系用一個(gè)抽象圖形來(lái)描述(見(jiàn)圖二)，其中A、B、C、D四個(gè)陸地分別用四個(gè)點(diǎn)來(lái)表示，而陸地之間有橋相連者則用連接兩個(gè)點(diǎn)的連線來(lái)表示，這樣，上述的哥尼斯堡七橋問(wèn)題就變成了由點(diǎn)和邊所組成的如下問(wèn)題：試求從圖中的任一點(diǎn)出發(fā)，不重復(fù)的通過(guò)每條邊一次，最后返回

7、到該點(diǎn)，這樣的路線是否存在？這樣問(wèn)題就變得簡(jiǎn)潔明了了，同時(shí)問(wèn)題也變得更一般、更深刻了這樣，七橋問(wèn)題就轉(zhuǎn)變?yōu)閳D論中的一筆畫(huà)問(wèn)題即能不能不重復(fù)的一筆畫(huà)出圖二中的這個(gè)圖形原先人們是要求找出一條不重復(fù)的路線，歐拉想，既然成千上萬(wàn)的人都失敗了，那么這樣的路線也許根本就不存在于是，歐拉就想：這樣不重復(fù)的路線究竟存不存在？由于改變了一下提問(wèn)的角度，歐拉抓住了問(wèn)題的實(shí)質(zhì)最后，歐拉認(rèn)真考慮了一筆畫(huà)圖形的結(jié)構(gòu)特征歐拉發(fā)現(xiàn)，凡是能用一筆畫(huà)成的圖形，都有這樣一

8、個(gè)特點(diǎn)：每當(dāng)畫(huà)一條線進(jìn)入中間的一個(gè)點(diǎn)時(shí)，還必須畫(huà)一條線離開(kāi)這個(gè)點(diǎn)否則，這個(gè)圖形就不可能用一筆畫(huà)出也就是說(shuō)，單獨(dú)考察圖中的任何一點(diǎn)（起點(diǎn)和終點(diǎn)除外），這個(gè)點(diǎn)都應(yīng)該與偶數(shù)條線相連；如果起點(diǎn)與終點(diǎn)重合，那么，連這個(gè)點(diǎn)也應(yīng)該與偶數(shù)條線相連在七橋問(wèn)題的幾何圖中，A、B、D三點(diǎn)分別與3條線相連，C點(diǎn)與5條線相連連線數(shù)都是奇數(shù)條因此，歐拉斷定：一筆畫(huà)出這個(gè)圖形是不可能的也就是說(shuō)，不重復(fù)地通過(guò)7座橋的路線是根本不存在的！天才的歐拉只用了一步就證明了這個(gè)

9、難題，從這里我們也可以看到圖論的強(qiáng)大威力.歐拉對(duì)七橋問(wèn)題的研究，是拓?fù)鋵W(xué)研究的先聲1750年，歐拉又發(fā)現(xiàn)了一個(gè)有趣的的現(xiàn)象歐拉因此得到了后人以他的名字命名的“多面體歐拉公式”正4面體有4個(gè)頂點(diǎn)、6條棱，它的面數(shù)加頂點(diǎn)數(shù)減去棱數(shù)等于2；正6面體有8個(gè)頂點(diǎn)、12條棱，它的面數(shù)加頂點(diǎn)數(shù)減去棱數(shù)也等于2接著，歐拉又考察了正12面體、正24面體，發(fā)現(xiàn)都有相同的結(jié)論于是繼續(xù)深入研究這個(gè)問(wèn)題，終于發(fā)現(xiàn)了一個(gè)著名的定理：(面數(shù))＋(頂點(diǎn)數(shù))－(棱數(shù))＝