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

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

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

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

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

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

5、產(chǎn)生了多個不同的圖論分支。幾個事實：任意的6個人中，總有3個人互相認(rèn)識或有3個人互不認(rèn)識。任意的9個人中，總有3個人互相認(rèn)識或有4個人互不認(rèn)識。問題：對任意的自然數(shù)k和t，是否存在一個最小的正整數(shù)r(k,t)，使得每個至少有r(k,t)個人的團(tuán)體，總有k個人互相認(rèn)識或有t個人互不認(rèn)識。拉姆瑟（F.P.Ramsey）在1930年證明了這個數(shù)r(k,t)是存在的，人們稱之為Ramsey數(shù)。確定其精確值是個公開的難題。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ù)的計算Ramsey數(shù)的計算是對人類智力的挑戰(zhàn)！例如R(4,5)=25(1993年計算機(jī)11年的計算量)Erd?s用如下比喻說明其困難程度：一伙外星人入侵地球，要求一年內(nèi)求得R(5,5)，否則將滅絕人類！那么也許人類能集中所有計算機(jī)和專家來求出它以自保；但如果外星人問的是R(6,6)，那么人類將別無選擇，只能拼死一戰(zhàn)了。Ramsey理論的哲理意義完全的無序是不可能的(Completedisorderisi

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