《圖論及其應(yīng)用》

《《圖論及其應(yīng)用》》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、圖論及其應(yīng)用圖論發(fā)展史圖論在現(xiàn)代科學(xué)技術(shù)中有著重要的理論價(jià)值和廣泛的應(yīng)用背景，如：線性代數(shù)、密碼學(xué)、物理化學(xué)、網(wǎng)絡(luò)設(shè)計(jì)、計(jì)算機(jī)科學(xué)、信息科學(xué)、DNA的基因譜的確定和計(jì)數(shù)、工業(yè)生產(chǎn)和企業(yè)管理中的優(yōu)化方法等都廣泛的應(yīng)用了圖論及其算法。首先我們通過圖的發(fā)展過程來了解一下圖論所研究的內(nèi)容。圖論起源于18世紀(jì)的一個(gè)游戲----俄羅斯的哥尼斯堡七橋問題。（1736年瑞士數(shù)學(xué)家歐拉——圖論之父）ABDC轉(zhuǎn)化Euler1736年BDCA圖論中討論的圖問題：是否能從A，B，C，D中的任一個(gè)開始走，通過每座橋恰好一次再回到起點(diǎn)？是否能從任意一個(gè)頂點(diǎn)開始，通過每條邊恰好一次再回到起點(diǎn)？轉(zhuǎn)化包含兩個(gè)要素：對象（陸地

2、）及對象間的二元關(guān)系（是否有橋連接）七橋問題中國郵遞員問題1962年中國數(shù)學(xué)家管梅谷提出圖論中的“中國郵遞員問題”。問題：一個(gè)郵遞員從街區(qū)的某一點(diǎn)出發(fā)，經(jīng)過街區(qū)每條街道至少一次又回到原出發(fā)點(diǎn)，如何設(shè)計(jì)投遞路線，使總路程最短？Hamilton問題源于1856年，英國數(shù)學(xué)家Hamilton設(shè)計(jì)了一個(gè)名為周游世界的游戲：他用一個(gè)正十二面體的二十個(gè)端點(diǎn)表示世界上的二十座大城市（見圖），提出的問題是要求游戲者找一條沿著十二面體的棱通過每個(gè)端點(diǎn)恰好一次的行走路線。反映到圖論上就是判斷一個(gè)給定的圖是否存在一條含所有頂點(diǎn)的回路。Hamilton問題四色問題是世界近代三大數(shù)學(xué)難題之一。四色問題的內(nèi)容是：任何一

3、張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色。它的提出來自英國。1852年，畢業(yè)于倫敦大學(xué)的弗南西斯·格思里發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來，每幅地圖都可以用四種顏色著色，使得有共同邊界的國家都被著上不同的顏色?！边@個(gè)現(xiàn)象能不能從數(shù)學(xué)上加以嚴(yán)格證明呢？四色問題1872年，英國當(dāng)時(shí)最著名的數(shù)學(xué)家凱利正式向倫敦?cái)?shù)學(xué)學(xué)會(huì)提出了這個(gè)問題，于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問題。1878～1880年兩年間，著名的律師兼數(shù)學(xué)家肯普和泰勒兩人分別提交了證明四色猜想的論文，宣布證明了四色定理，大家都認(rèn)為四色猜想從此也就解決了。1890年，在牛津大學(xué)就讀的年僅29歲的赫伍德以自己的精確計(jì)算指出了肯普在證

4、明上的漏洞。不久，泰勒的證明也被人們否定了。后來，人們開始認(rèn)識(shí)到，這個(gè)貌似容易的題目，其實(shí)是一個(gè)可與費(fèi)馬猜想相媲美的難題。進(jìn)入20世紀(jì)以來，科學(xué)家們對四色猜想的證明基本上是按照肯普的想法在進(jìn)行。后來美國數(shù)學(xué)家富蘭克林于1939年證明了22國以下的地圖都可以用四色著色。1950年，有人從22國推進(jìn)到35國。1960年，有人又證明了39國以下的地圖可以只用四種顏色著色；隨后又推進(jìn)到了50國。1976年6月，美國伊利諾大學(xué)哈肯與阿佩爾在兩臺(tái)不同的電子計(jì)算機(jī)上，用了1200個(gè)小時(shí)，作了100億判斷，終于完成了四色定理的證明，轟動(dòng)了世界。然而，真正數(shù)學(xué)上的嚴(yán)格證明仍然沒有得到！數(shù)學(xué)家仍為此努力，并由此

5、產(chǎn)生了多個(gè)不同的圖論分支。幾個(gè)事實(shí)：任意的6個(gè)人中，總有3個(gè)人互相認(rèn)識(shí)或有3個(gè)人互不認(rèn)識(shí)。任意的9個(gè)人中，總有3個(gè)人互相認(rèn)識(shí)或有4個(gè)人互不認(rèn)識(shí)。問題：對任意的自然數(shù)k和t，是否存在一個(gè)最小的正整數(shù)r(k,t)，使得每個(gè)至少有r(k,t)個(gè)人的團(tuán)體，總有k個(gè)人互相認(rèn)識(shí)或有t個(gè)人互不認(rèn)識(shí)。拉姆瑟（F.P.Ramsey）在1930年證明了這個(gè)數(shù)r(k,t)是存在的，人們稱之為Ramsey數(shù)。確定其精確值是個(gè)公開的難題。Ramsey問題Ramsey數(shù)R(p,q)p,q345678936914182328364182535–4149–6156–8469–115543–4958–8780–143101–

6、216121–3166102–165111–298127–495169–7807205–540216–1031232–17138282–1870317–35839565–6588Ramsey數(shù)的計(jì)算Ramsey數(shù)的計(jì)算是對人類智力的挑戰(zhàn)！例如R(4,5)=25(1993年計(jì)算機(jī)11年的計(jì)算量)Erd?s用如下比喻說明其困難程度：一伙外星人入侵地球，要求一年內(nèi)求得R(5,5)，否則將滅絕人類！那么也許人類能集中所有計(jì)算機(jī)和專家來求出它以自保；但如果外星人問的是R(6,6)，那么人類將別無選擇，只能拼死一戰(zhàn)了。Ramsey理論的哲理意義完全的無序是不可能的(Completedisorderisi

7、mpossible)。任一足夠大的結(jié)構(gòu)中必定包含一個(gè)給定大小的規(guī)則子結(jié)構(gòu)。無序無意的行為產(chǎn)生了有規(guī)律的后果，發(fā)人深思耐人尋味。古人在滿天的星斗中發(fā)現(xiàn)野獸和眾神群集于天空的圖形，以為是造物主的杰作。但根據(jù)Ramsey定理，只要隨機(jī)分布的星星數(shù)目足夠多，就可以描繪出各種圖形的輪廓。1994年StatisticalScience的一篇論文利用統(tǒng)計(jì)方法證明：圣經(jīng)隱藏了許多訊息，而這些訊息是有意安排的，絕非文字排列偶然