圖論經(jīng)典問題

1、常見問題：1、圖論的歷史圖論以圖為研究對(duì)象的數(shù)學(xué)分支。圖論中的圖指的是一些點(diǎn)以及連接這些點(diǎn)的線的總體。通常用點(diǎn)代表事物，用連接兩點(diǎn)的線代表事物間的關(guān)系。圖論則是研究事物對(duì)象在上述表示法中具有的特征與性質(zhì)的學(xué)科。在自然界和人類社會(huì)的實(shí)際生活中，用圖形來描述和表示某些事物之間的關(guān)系既方便又直觀。例如，國(guó)家用點(diǎn)表示，有外交關(guān)系的國(guó)家用線連接代表這兩個(gè)國(guó)家的點(diǎn)，于是世界各國(guó)之間的外交關(guān)系就被一個(gè)圖形描述出來了。另外我們常用工藝流程圖來描述某項(xiàng)工程中各工序之間的先后關(guān)系，用網(wǎng)絡(luò)圖來描述某通訊系統(tǒng)中各通訊站之間信息傳遞關(guān)系，用開關(guān)電路圖來描述IC中各元件電路導(dǎo)線連接關(guān)系等等。事實(shí)上，任何一個(gè)包含了某種二元

2、關(guān)系的系統(tǒng)都可以用圖形來模擬。由于我們感興趣的是兩對(duì)象之間是否有某種特定關(guān)系，所以圖形中兩點(diǎn)之間連接與否最重要，而連接線的曲直長(zhǎng)短則無關(guān)緊要。由此經(jīng)數(shù)學(xué)抽象產(chǎn)生了圖的概念。研究圖的基本概念和性質(zhì)、圖的理論及其應(yīng)用構(gòu)成了圖論的主要內(nèi)容。圖論的產(chǎn)生和發(fā)展經(jīng)歷了二百多年的歷史，大體上可分為三個(gè)階段：第一階段是從1736年到19世紀(jì)中葉。當(dāng)時(shí)的圖論問題是盛行的迷宮問題和游戲問題。最有代表性的工作是著名數(shù)學(xué)家L.Euler于1736年解決的哥尼斯堡七橋問題(Konigsberg Seven Bridges Problem)。東普魯士的哥尼斯堡城(現(xiàn)今是俄羅斯的加里寧格勒，在波羅的海南岸）位于普雷格爾(P

3、regel)河的兩岸，河中有一個(gè)島，于是城市被河的分支和島分成了四個(gè)部分，各部分通過7座橋彼此相通。如同德國(guó)其他城市的居民一樣，該城的居民喜歡在星期日繞城散步。于是產(chǎn)生了這樣一個(gè)問題：從四部分陸地任一塊出發(fā)，按什么樣的路線能做到每座橋經(jīng)過一次且僅一次返回出發(fā)點(diǎn)。這就是有名的哥尼斯堡七橋問題。哥尼斯堡七橋問題看起來不復(fù)雜，因此立刻吸引所有人的注意，但是實(shí)際上很難解決。瑞士數(shù)學(xué)家(Leonhard Euler)在1736年發(fā)表的“哥尼斯堡七橋問題”的文章中解決了這個(gè)問題。這篇論文被公認(rèn)為是圖論歷史上的第一篇論文，Euler也因此被譽(yù)為圖論之父。 歐拉把七橋問題抽象成數(shù)學(xué)問題-一筆畫問題，并給出一筆

4、畫問題的判別準(zhǔn)則，從而判定七橋問題不存在解。Euler是這樣解決這個(gè)問題的：將四塊陸地表示成四個(gè)點(diǎn)，橋看成是對(duì)應(yīng)結(jié)點(diǎn)之間的連線，則哥尼斯堡七橋問題就變成了：從A，B，C，D任一點(diǎn)出發(fā)，通過每邊一次且僅一次返回原出發(fā)點(diǎn)的路線(回路)是否存在？Euler證明這樣的回路是不存在的。第二階段是從19世紀(jì)中葉到1936年。圖論主要研究一些游戲問題：迷宮問題、博弈問題、棋盤上馬的行走線路問題。一些圖論中的著名問題如四色問題(1852年)和Hamilton環(huán)游世界問題(1856年)也大量出現(xiàn)。同時(shí)出現(xiàn)了以圖為工具去解決其它領(lǐng)域中一些問題的成果。1847年德國(guó)的克?；舴?G.R.Kirchoff)將樹的概念和

5、理論應(yīng)用于工程技術(shù)的電網(wǎng)絡(luò)方程組的研究。1857年英國(guó)的凱萊(A.Cayley)也獨(dú)立地提出了樹的概念，并應(yīng)用于有機(jī)化合物的分子結(jié)構(gòu)的研究中。1936年匈牙利的數(shù)學(xué)家哥尼格(D.Konig)寫出了第一本圖論專著有限圖與無限圖的理論(Theory of directed and Undirected Graphs)。標(biāo)志著圖論作為一門獨(dú)立學(xué)科。第三階段是1936年以后。由于生產(chǎn)管理、軍事、交通運(yùn)輸、計(jì)算機(jī)和通訊網(wǎng)絡(luò)等方面的大量問題的出現(xiàn)，大大促進(jìn)了圖論的發(fā)展。特別是電子計(jì)算機(jī)的大量應(yīng)用，使大規(guī)模問題的求解成為可能。實(shí)際問題如電網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、電路設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)以及社會(huì)科學(xué)中的問題所涉及到的圖形都

6、是很復(fù)雜的，需要計(jì)算機(jī)的幫助才有可能進(jìn)行分析和解決。目前圖論在物理、化學(xué)、運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)、電子學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、社會(huì)科學(xué)及經(jīng)濟(jì)管理等幾乎所有學(xué)科領(lǐng)域都有應(yīng)用。2、平面圖和印刷電路板的設(shè)計(jì)有時(shí)候，實(shí)際問題要求我們把圖畫在平面上，使得不是節(jié)點(diǎn)的地方不能有邊交叉，這在圖論中就是判斷一個(gè)圖是否是平面圖的問題。像印刷電路板(Printed Circuit Board，PCB)（單層印刷電路板，多層印刷電路板）幾乎會(huì)出現(xiàn)在每一種電子設(shè)備中。PCB的主要功能是提供上頭各項(xiàng)零件的相互電氣連接。隨著電子設(shè)備越來越復(fù)雜，需要的元件越來越多，PCB上頭的導(dǎo)線與元件也越來越密集了。 板子本身的基板是由

7、絕緣隔熱、不易彎曲的材料制作而成。在表面可以看到的細(xì)小線路材料是銅箔，原本銅箔是覆蓋在整個(gè)板子上的，而在制造過程中部份被蝕刻處理掉，留下來的部份就變成網(wǎng)狀的細(xì)小線路了。這些線路被稱作導(dǎo)線或布線，并用來提供PCB上元件的電路連接。 因此在設(shè)計(jì)和制造印刷電路板時(shí)，首先要解決的問題是判定一個(gè)給定的電路圖是否能印刷在同一層板上而使民線不發(fā)生短路？若可以，怎樣給出具體的布線方案？將要印刷的電路圖看成是一個(gè)無向簡(jiǎn)單連通圖G，其中頂點(diǎn)代表電子元件，邊代表導(dǎo)線，于是上述問題歸結(jié)為判定G是否是平面圖？若G是平面圖，由怎樣給出它的一個(gè)平面表示來？平面圖的判斷問題，在數(shù)學(xué)上已由波蘭數(shù)學(xué)家?guī)炖蟹蛩够?Kuratow

8、ski) 于1930年解決。庫(kù)拉托夫斯基定理給出的充要條件看似簡(jiǎn)單，但實(shí)現(xiàn)起來很難。但是許多研究拓?fù)鋱D論的數(shù)學(xué)家提出了比較有效的圖的平面性判定的準(zhǔn)則，如DMP方法以就是其中的一個(gè)有代表性方法。3、圖的著色和四色問題圖的著色起源于“四色問題”。四色問題又稱四色猜想，是世界近代三大數(shù)學(xué)難題之一。四色問題是說畫在紙上的每張地圖只需要用4種顏色就能使具有共同邊界的國(guó)家不會(huì)有相同的顏色。用數(shù)學(xué)語(yǔ)言表示，就是將平面任意地細(xì)分為不相重迭的區(qū)域，每一個(gè)區(qū)域總可以用1，2，3，4這四個(gè)數(shù)字之一來標(biāo)記，而不會(huì)使相鄰的兩個(gè)區(qū)域得到相同的數(shù)字。這里所指的相鄰區(qū)域，是指有一整段邊界是公共的。如果兩個(gè)區(qū)域只相遇于一點(diǎn)或有

9、限多點(diǎn)，就不叫相鄰的。因?yàn)橛孟嗤念伾o它們著色不會(huì)引起混淆。四色猜想的提出來自英國(guó)。1852年，畢業(yè)于倫敦大學(xué)的格思里(F.Guthrie)來到一家科研單位搞地圖著色工作時(shí)，發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來，每幅地圖都可以用四種顏色著色，使得有共同邊界的國(guó)家都著上不同的顏色?！边@個(gè)現(xiàn)象能不能從數(shù)學(xué)上加以嚴(yán)格證明呢？他和在大學(xué)讀書的弟弟格里斯決心試一試。兄弟二人為證明這一問題而使用的稿紙已經(jīng)堆了一大疊，可是研究工作沒有進(jìn)展。1852年10月23日，他的弟弟就這個(gè)問題的證明請(qǐng)教了他的老師、著名數(shù)學(xué)家德?摩爾根(De Morgan)，摩爾根也沒有能找到解決這個(gè)問題的途徑，于是寫信向自己的好友、著名數(shù)學(xué)

10、家漢密爾頓爵士(W.R. Hamilton)請(qǐng)教。漢密爾頓接到摩爾根的信后，對(duì)四色問題進(jìn)行論證。但直到1865年漢密爾頓逝世為止，問題也沒有能夠解決。起初，這個(gè)問題并沒有引起數(shù)學(xué)家們的注意，認(rèn)為這是一個(gè)不證即明的事實(shí)。但經(jīng)過一些嘗試之后，發(fā)現(xiàn)并不是那么回事。1878年，英國(guó)當(dāng)時(shí)最著名的數(shù)學(xué)家凱利(A. Cayley)正式向倫敦?cái)?shù)學(xué)學(xué)會(huì)提出了這個(gè)問題，于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問題。世界上許多一流的數(shù)學(xué)家都紛紛參加了證明四色猜想的大會(huì)戰(zhàn)。18781880年兩年間，著名的律師兼數(shù)學(xué)家肯普(Kempe)和泰勒(Taylor)兩人分別提交了證明四色猜想的論文，宣布證明了四色定理，大家都認(rèn)為四色猜

11、想從此也就解決了。但是后來人們發(fā)現(xiàn)他們都錯(cuò)了。后來，越來越多的數(shù)學(xué)家雖然對(duì)此絞盡腦汁，但一無所獲。于是，人們開始認(rèn)識(shí)到，這個(gè)貌似容易的題目，其實(shí)是一個(gè)可與費(fèi)馬大定理相媲美的難題。不過肯普的證明雖然失敗了，但它在證明中提供的思想和方法仍然是后來許多數(shù)學(xué)家沖擊四色問題的基礎(chǔ)。美國(guó)數(shù)學(xué)家富蘭克林于1939年證明了22國(guó)以下的地圖都可以用四色著色。1950年，有人從22國(guó)推進(jìn)到35國(guó)。1960年，有人又證明了39國(guó)以下的地圖可以只用四種顏色著色；隨后又推進(jìn)到了50國(guó)。但是這種推進(jìn)仍然十分緩慢。電子計(jì)算機(jī)問世以后，由于演算速度迅速提高，加之人機(jī)對(duì)話的出現(xiàn)，大大加快了對(duì)四色猜想證明的進(jìn)程。1976年6月，

12、美國(guó)伊利諾大學(xué)的阿佩爾(Appel)、哈肯(Haken)和柯齊(Koch)三人合作編制了一個(gè)程序，在美國(guó)伊利諾斯大學(xué)的兩臺(tái)不同的電子計(jì)算機(jī)上，用了1260個(gè)小時(shí)，作了100多億次邏輯判斷，給出了四色猜想證明，轟動(dòng)了世界。這是一百多年來吸引許多數(shù)學(xué)家與數(shù)學(xué)愛好者的大事，當(dāng)兩位數(shù)學(xué)家將他們的研究成果發(fā)表的時(shí)候，當(dāng)?shù)氐泥]局在當(dāng)天發(fā)出的所有郵件上都加蓋了“四色足夠”的特制郵戳，以慶祝這一難題獲得解決?！八纳珕栴}”的被證明不僅解決了一個(gè)歷時(shí)100多年的難題，而且成為數(shù)學(xué)史上一系列新思維的起點(diǎn)。在“四色問題”的研究過程中，不少新的數(shù)學(xué)理論隨之產(chǎn)生，也發(fā)展了很多數(shù)學(xué)計(jì)算技巧。如將地圖的著色問題化為圖論問題，

13、豐富了圖論的內(nèi)容。不僅如此，“四色問題”在有效地設(shè)計(jì)航空班機(jī)日程表、設(shè)計(jì)計(jì)算機(jī)的編碼程序上都起到了推動(dòng)作用。不過不少數(shù)學(xué)家并不滿足于計(jì)算機(jī)取得的成就，他們認(rèn)為應(yīng)該有一種簡(jiǎn)捷明快的書面證明方法。直到現(xiàn)在，仍由不少數(shù)學(xué)家和數(shù)學(xué)愛好者在尋找更簡(jiǎn)潔的證明方法。4、運(yùn)輸網(wǎng)絡(luò)自從克?；舴蜻\(yùn)用圖論從事電路網(wǎng)絡(luò)的結(jié)構(gòu)分析以來，網(wǎng)絡(luò)理論的研究和應(yīng)用就越來越廣泛。特別是近幾十年來，電路網(wǎng)絡(luò)、運(yùn)輸網(wǎng)絡(luò)、通訊網(wǎng)絡(luò)等與工程和應(yīng)用密切相關(guān)的課題受到了高度的重視。無自回路的有向賦權(quán)圖稱為網(wǎng)絡(luò)(Network)。在一個(gè)網(wǎng)絡(luò)中，有向邊上的權(quán)稱為容量(Capacity)。網(wǎng)絡(luò)中入度為0的結(jié)點(diǎn)稱為源(Source)，用字母s表示；

14、出度為0的結(jié)點(diǎn)稱為匯(Trap),用字母t表示。在某些問題，只考慮有單一源和單一匯的網(wǎng)絡(luò)（即運(yùn)輸網(wǎng)絡(luò)），而在另一些問題中（如通訊網(wǎng)絡(luò)），根本就不考慮源和匯。運(yùn)輸網(wǎng)絡(luò)的實(shí)際意義可以用公路網(wǎng)、鐵路網(wǎng)、和供水系統(tǒng)、電網(wǎng)等來說明，也就是“貨物從產(chǎn)地s，通過若干中轉(zhuǎn)站，到達(dá)目的地t”這類情形的一般模型。這里將源和匯分別看成是貨物的產(chǎn)地和目的地，其他結(jié)點(diǎn)是中轉(zhuǎn)站，有向邊是連接兩站的道路（公路、鐵路、水管或電線等），容量則是某一段道路允許的通行能力的上限。在運(yùn)輸網(wǎng)絡(luò)中要考慮的是從源到匯的實(shí)際流通量，顯然它與每條有向邊的容量有關(guān)，也和每個(gè)結(jié)點(diǎn)的轉(zhuǎn)運(yùn)能力有關(guān)。對(duì)運(yùn)輸貨物來講，除了容量之外，每條邊還被賦予一個(gè)非負(fù)

15、實(shí)數(shù)，這一組數(shù)若滿足以下條件：?jiǎn)挝粫r(shí)間內(nèi)通過每條道路運(yùn)送的貨物總量不能超過道路的容量；每一個(gè)中轉(zhuǎn)站的流入量等于流出量；源的流出量等于匯的總流入量（即網(wǎng)絡(luò)的流量(Discharge)）。則稱這組數(shù)為該運(yùn)輸網(wǎng)絡(luò)的一個(gè)流(Flow)。一個(gè)運(yùn)輸網(wǎng)絡(luò)中具有可能的最大值的流稱為最大流。在一個(gè)運(yùn)輸網(wǎng)絡(luò)中，可能不止一個(gè)最大流，即可能有幾個(gè)不同的流，都具有最大值。給定運(yùn)輸網(wǎng)絡(luò)求其最大流的問題，就是怎樣使給定網(wǎng)絡(luò)在單位時(shí)間運(yùn)輸量最大的問題，并且確定當(dāng)網(wǎng)絡(luò)的流量最大時(shí)的流。最大流問題的解決顯然在現(xiàn)實(shí)生活中有很重大的應(yīng)用價(jià)值。5、通訊網(wǎng)絡(luò)網(wǎng)絡(luò)應(yīng)用的另一重要方面是通訊網(wǎng)絡(luò)，如電話網(wǎng)絡(luò)、計(jì)算機(jī)網(wǎng)絡(luò)、管理信息系統(tǒng)、醫(yī)療數(shù)據(jù)

16、網(wǎng)絡(luò)、銀行數(shù)據(jù)網(wǎng)絡(luò)、開關(guān)網(wǎng)絡(luò)等等。這些網(wǎng)絡(luò)的基本要求是網(wǎng)絡(luò)中各用戶能夠快速安全地傳遞信息，不產(chǎn)生差錯(cuò)和故障，同時(shí)使建造和維護(hù)網(wǎng)絡(luò)所需費(fèi)用低。通訊網(wǎng)絡(luò)中最重要的整體問題是網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。根據(jù)用途和性能指標(biāo)的不同要求，通訊網(wǎng)絡(luò)有不同的拓?fù)浣Y(jié)構(gòu)，如環(huán)形網(wǎng)絡(luò)、樹形網(wǎng)絡(luò)、星形網(wǎng)絡(luò)、分布式網(wǎng)絡(luò)、網(wǎng)狀網(wǎng)絡(luò)及混合型網(wǎng)絡(luò)等等。通訊網(wǎng)絡(luò)是一個(gè)強(qiáng)連通的有向圖。除了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)之外，通訊網(wǎng)絡(luò)還要考慮流量和控制問題、網(wǎng)絡(luò)的可靠性等問題。圖論中的連通度在通訊網(wǎng)絡(luò)中有著重要的應(yīng)用，是大規(guī)?；ミB容錯(cuò)網(wǎng)絡(luò)可靠性的有效性分析的基礎(chǔ)。當(dāng)然網(wǎng)絡(luò)的可靠性涉及的因素很多，但是從通訊網(wǎng)絡(luò)作為一個(gè)強(qiáng)連通的有向圖來說，一個(gè)具有最佳連通性的網(wǎng)

17、絡(luò)就不易出現(xiàn)阻礙問題。6、二元樹的應(yīng)用-前綴碼(哈夫曼編碼)在通訊系統(tǒng)中，常用二進(jìn)制來表示字符。但由于字符出現(xiàn)的頻率不一樣以及為了保密的原因，能否用不等長(zhǎng)的二進(jìn)制數(shù)表示不同的字符，使傳輸?shù)男畔⑺玫目偞a元盡可能少呢？但是不等長(zhǎng)的編碼方案給編碼和譯碼帶來了困難。為了解決這個(gè)問題，我們引入了前綴碼（哈夫曼編碼）。設(shè)abcd為一個(gè)長(zhǎng)為n的字符串，則a,ab,abc分別為它的長(zhǎng)為1,2,n-1的前綴(Prefix)。設(shè)A是一個(gè)字符串集，若其中的任一字符串都不是其它字符串的前綴，則稱A為一個(gè)前綴碼(哈夫曼編碼)(Prefixed Code)。若組成A的字符串的只有字符0和1，則稱A為二元前綴碼(Bina

18、ry Prefixed Code)。如000，001，01，10，110，111是一個(gè)二元前綴碼，而000，001，01，10，11，111不是一個(gè)二元前綴碼。那么如何構(gòu)造一個(gè)二元前綴碼并用它進(jìn)行編碼和譯碼呢？我們利用二元樹來產(chǎn)生一個(gè)二元前綴碼：1 構(gòu)造一棵二元樹，樹根的左側(cè)用0標(biāo)記，右側(cè)用1標(biāo)記；2 分支點(diǎn)v的左側(cè)(右側(cè))的標(biāo)記就是標(biāo)記v的二進(jìn)制數(shù)最右端加上0(1)；3 任一片樹葉的標(biāo)記串不是其它樹葉的標(biāo)記串的前綴；4 將所有樹葉的標(biāo)記串取來就可構(gòu)成一個(gè)二元前綴碼。然后對(duì)要發(fā)送的信息中的每個(gè)字符分別用這個(gè)二元前綴碼中的字符串代表，當(dāng)然應(yīng)該用越長(zhǎng)的字符串代表出現(xiàn)頻率越最低的字符串。當(dāng)接收方接到發(fā)送方發(fā)過去的信息（實(shí)