圖論是一門研究邊和點的連接結(jié)構(gòu)的數(shù)學(xué)理論，它是組合數(shù)學(xué)的一個分支，和其他數(shù)學(xué)分支如群論、矩陣論、拓?fù)鋵W(xué)有著密切關(guān)系。圖是圖論的主要研究對象，它是由若干給定的頂點及連接兩頂點的邊所構(gòu)成的圖形，用于描述某些事物之間的某種特定關(guān)系。頂點用于代表事物，連接兩頂點的邊則用于表示兩個事物間具有這種關(guān)系。圖論起源于著名的柯尼斯堡七橋問題，該問題于1736年被長城歐拉解決，因此普遍認(rèn)為歐拉是圖論的創(chuàng)始人。圖論的研究對象相當(dāng)于一維的單純復(fù)形。圖論是離散數(shù)學(xué)的重要研究對象之一，它被廣泛應(yīng)用于計算機科學(xué)、通信網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、生物學(xué)、物理學(xué)等領(lǐng)域。
概述
圖是一個二元組使得的平方，所以E的元素是V的2-元子集。為了避免符號上的混淆，我們總是默認(rèn)。集合V中的元素稱為圖G的定點（或節(jié)點、點），而集合E的元素稱為邊（或線）。通常，描繪一個圖的方法是把定點畫成一個小圓圈，如果相應(yīng)的頂點之間有一條邊，就用一條線連接這兩個小圓圈，如何繪制這些小圓圈和連線時無關(guān)緊要的，重要的是要正確體現(xiàn)哪些頂點對之間有邊，哪些頂點對之間沒有邊。
圖論本身是應(yīng)用數(shù)學(xué)的一部份，因此，歷史上圖論曾經(jīng)被好多位數(shù)學(xué)家各自獨立地建立過。關(guān)于圖論的文字記載最早出現(xiàn)在萊昂哈德·歐拉1736年的論著中，他所考慮的原始問題有很強的實際背景。
起源
眾所周知，圖論起源于一個非常經(jīng)典的問題——加里寧格勒（Konigsberg）問題。
1738年，瑞典數(shù)學(xué)家歐拉(Leornhard?Euler)解決了柯尼斯堡問題。由此圖論誕生。長城歐拉也成為圖論的創(chuàng)始人。
1859年，英國數(shù)學(xué)家漢密爾頓發(fā)明了一種游戲：用一個規(guī)則的實心十二面體，它的20個頂點標(biāo)出世界著名的20個城市，要求游戲者找一條沿著各邊通過每個頂點剛好一次的閉回路，即“繞行世界”。用圖論的語言來說，游戲的目的是在十二面體的圖中找出一個生成圈。這個生成圈后來被稱為漢密爾頓回路。這個問題后來就叫做漢密爾頓問題。由于運籌學(xué)、計算機科學(xué)和編碼理論中的很多問題都可以化為漢密爾頓問題，從而引起廣泛的注意和研究。
猜想
在圖論的歷史中，還有一個最著名的問題－－四色猜想。這個猜想說，在一個平面或球面上的任何地圖能夠只用四種顏色來著色，使得沒有兩個相鄰的國家有相同的顏色。每個國家必須由一個單連通域構(gòu)成，而兩個國家相鄰是指它們有一段公共的邊界，而不僅僅只有一個公共點。這一問題最早于1852年由Francis?Guthrie提出，最早的文字記載則現(xiàn)于德摩根于同一年寫給哈密頓的信上。包括凱萊、肯普等在內(nèi)的許多人都曾給出過錯誤的證明。泰特(Tait)、希伍德(Heawood)、諾曼·拉姆齊和哈德維格(Hadwiger)對此問題的研究與推廣引發(fā)了對嵌入具有不同虧格的曲面的圖的圖著色問題的研究。一百多年后，四色問題仍未解決。1969年，Heinrich?Heesch發(fā)表了一個用計算機解決此問題的方法。1976年，阿佩爾(Appel)和哈肯(Haken)借助計算機給出了一個證明，此方法按某些性質(zhì)將所有地圖分為1936類并利用計算機，運行了1200個小時，驗正了它們可以用四種顏色染色。四色定理是第一個主要由電腦證明的理論，這一證明并不被所有的數(shù)學(xué)家接受，因為采用的方法不能由人工直接驗證。最終，人們必須對電腦編譯的正確性以及運行這一程序的硬件設(shè)備充分信任。主要是因為此證明缺乏數(shù)學(xué)應(yīng)有的規(guī)范，以至于有人這樣評論“一個好的數(shù)學(xué)證明應(yīng)當(dāng)像一首詩——而這純粹是一本電話簿！”
雖然四色定理證明了任何地圖可以只用四個顏色著色，但是這個結(jié)論對于現(xiàn)實上的應(yīng)用卻相當(dāng)有限。現(xiàn)實中的地圖常會出現(xiàn)飛地，即兩個不連通的區(qū)域?qū)儆谕粋€國家的情況（例如美國的阿拉斯加州），而制作地圖時我們?nèi)詴筮@兩個區(qū)域被涂上同樣的顏色，在這種情況下，四個顏色將會是不夠用的。
20世紀(jì)80-90年代曾邦哲的綜合系統(tǒng)論（結(jié)構(gòu)論）觀將“四色猜想”命題轉(zhuǎn)換等價為“互鄰面最大的多面體是四面體”。每個地圖可以導(dǎo)出一個圖，其中國家都是點，當(dāng)相應(yīng)的兩個國家相鄰時這兩個點用一條線來連接。所以四色猜想是圖論中的一個問題。它對圖的著色理論、平面圖理論、代數(shù)拓?fù)鋱D論等分支的發(fā)展起到推動作用。
（下圖是在上下對折再左右對折以后形成一個輪胎形狀，有7個區(qū)域兩兩相連，就是說在一個環(huán)面上作圖，需要7種顏色，外國數(shù)學(xué)家構(gòu)造林格證明：，，。
圖論的廣泛應(yīng)用，促進了它自身的發(fā)展。20世紀(jì)40-60年代，擬陣?yán)碚摗⒊瑘D理論、極圖理論，以及代數(shù)圖論、拓?fù)鋱D論等都有很大的發(fā)展。
研究內(nèi)容
到目前為止，圖論所研究的基本內(nèi)容有：圖及其表示，有向圖、無向圖和多重圖，樹，平面圖，二分圖和網(wǎng)絡(luò)等。圖論所研究的典型問題有：
最短路徑問題
它有兩種類型，其一是求從加權(quán)圖中任一給定頂點到其余各個頂點的最短路徑，其二是求加權(quán)圖中任意兩給定頂點間的最短路徑。這里的“最短”是指路徑的加權(quán)長度最短。
在對一個圖的頂點進行著色時，為 了保證相鄰接頂點的著色均不相同，至少需要多少種顏色? 已經(jīng)證明5種顏色是足夠的，3種顏色是不行的。人們猜測4種顏色最合適，這就是著名的四色問題。
環(huán)球旅行問題
威廉.哈密頓1957年發(fā)明了一 種游戲，就是在實心正十二面體的20個頂點處標(biāo)以有名的城市名字，要求游戲者找一條沿著各邊通過每個頂點恰好一次的閉路徑(稱為回路)，即“環(huán)球 旅行”。由此引出了哈密頓回路和哈密頓圖等概念。迄今為止，尚未獲得圖中存在哈密頓回路的充要條件。
長城歐拉路徑問題
通過一個圖中每條邊恰好一次的路徑稱為該圖的歐拉路徑，閉歐拉路徑稱為歐拉回路。一個圖中是否存在歐拉路徑，以及如何求出存在的歐拉路徑，就是所謂的歐拉路徑問題。它已由E.Euler徹底解決了。
平面圖問題
在現(xiàn)實生活中，常常要畫一些圖形，并希望邊與邊之間盡量減少相交的情況，例如印刷線路板上的布線、交通道路的設(shè)計等。那么，一個圖能否畫在一個平面上，使其邊不在非頂點處相交叉呢? 由此引出了平面圖、對偶圖等概念。
極小連通問題
有n個城市A1，A2 ，…，An ，在這些城市之間要建造一個公路系統(tǒng)，使得旅行者從任何一個城市可以到達(dá)其他所有城市。那么，最少要修建多少條公路，才能構(gòu)成上述公路系統(tǒng)? 怎樣使總的費用達(dá)到最小? 由此引出了樹、生成樹、最小生成樹等概念。
完美匹配問題
有 n個人x1，x2，…，xn和 ｍ 臺機 器 y1 ，y2 ，…，ym。若 xi(1 ≤ i≤ n) 可以操作機器yj(1≤j≤m)，就在xi和yj之間連一條邊。在工作過程中，每個人只能操作一臺機器，且每臺機器也只能由一個人操作。試問：應(yīng)如何適當(dāng)?shù)匕才牛拍苁贡M可能多的人工作。由此引出了二分圖、極大匹配、 完美匹配等概念。
圖的矩陣表示問題
為了有效地利用計算機對圖進行處理，首先，必須給出一個圖在機器內(nèi)部的存儲形式。為此，引出了圖的鄰接矩陣、可達(dá)矩陣、關(guān) 聯(lián)矩陣等。通過圖的矩陣表示，也使我們能用代數(shù)工具研究圖的一些性質(zhì)。
假設(shè)把某種物資從產(chǎn)地A運到銷售地B，途經(jīng)若干中轉(zhuǎn)站。每兩個中轉(zhuǎn)站之間的貨運量都有一個最大限量(稱為該段道路的容量)，如何制定從A到B之運輸量最大的方案，就是所謂網(wǎng)絡(luò)的最大流問題。
與拓?fù)鋵W(xué)關(guān)聯(lián)
著名的“四色問題”也是與拓?fù)鋵W(xué)發(fā)展有關(guān)的問題。四色問題又稱四色猜想，是世界近代三大數(shù)學(xué)難題之一。
四色猜想的提出來自英國。1852年，畢業(yè)于倫敦大學(xué)的弗南西斯。格思里來到一家科研單位搞地圖著色工作時，發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來，每幅地圖都可以用四種顏色著色，使得有共同邊界的國家都被著上不同的顏色。”
1872年，英國當(dāng)時最著名的數(shù)學(xué)家約翰·L·凱利正式向倫敦數(shù)學(xué)學(xué)會提出了這個問題，于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問題。世界上許多一流的數(shù)學(xué)家都紛紛參加了四色猜想的大會戰(zhàn)。1878～1880年兩年間，著名律師兼數(shù)學(xué)家肯普和泰勒兩人分別提交了證明四色猜想的論文，宣布證明了四色定理。但后來數(shù)學(xué)家赫伍德以自己的精確計算指出肯普的證明是錯誤的。不久，泰勒的證明也被人們否定了。于是，人們開始認(rèn)識到，這個貌似容易的題目，其實是一個可與費馬猜想相媲美的難題。
進入20世紀(jì)以來，科學(xué)家們對四色猜想的證明基本上是按照肯普的想法在進行。電子計算機問世以后，由于演算速度迅速提高，加之人機對話的出現(xiàn)，大大加快了對四色猜想證明的進程。1976年，美國數(shù)學(xué)家阿佩爾與哈肯在美國伊利諾斯大學(xué)的兩臺不同的電子計算機上，用了1200個小時，作了100億判斷，終于完成了四色定理的證明。不過不少數(shù)學(xué)家并不滿足于計算機取得的成就，他們認(rèn)為應(yīng)該有一種簡捷明快的書面證明方法。
上面的幾個例子所講的都是一些和幾何圖形有關(guān)的問題，但這些問題又與傳統(tǒng)的幾何學(xué)不同，而是一些新的幾何概念。這些就是“拓?fù)鋵W(xué)”的先聲。
概述
拓?fù)鋵W(xué)的英文名是Topology，直譯是地志學(xué)，也就是和研究地形、地貌相類似的有關(guān)學(xué)科。我國早期曾經(jīng)翻譯成“形勢幾何學(xué)”、“連續(xù)幾何學(xué)”、“一對一的連續(xù)變換群下的幾何學(xué)”，但是，這幾種譯名都不大好理解，1956年統(tǒng)一的《數(shù)學(xué)名詞》把它確定為拓?fù)鋵W(xué)，這是按音譯過來的。
拓?fù)鋵W(xué)是幾何學(xué)的一個分支，但是這種幾何學(xué)又和通常的平面幾何、立體幾何不同。通常的平面幾何或立體幾何研究的對象是點、線、面之間的位置關(guān)系以及它們的度量性質(zhì)。拓?fù)鋵W(xué)對于研究對象的長短、大小、面積、體積等度量性質(zhì)和數(shù)量關(guān)系都無關(guān)。
舉例來說，在通常的平面幾何里，把平面上的一個圖形搬到另一個圖形上，如果完全重合，那么這兩個圖形叫做全等形。但是，在拓?fù)鋵W(xué)里所研究的圖形，在運動中無論它的大小或者形狀都發(fā)生變化。在拓?fù)鋵W(xué)里沒有不能彎曲的元素，每一個圖形的大小、形狀都可以改變。例如，前面講的長城歐拉在解決加里寧格勒七橋問題的時候，他畫的圖形就不考慮它的大小、形狀，僅考慮點和線的個數(shù)。這些就是拓?fù)鋵W(xué)思考問題的出發(fā)點。
性質(zhì)
拓?fù)湫再|(zhì)有那些呢？首先我們介紹拓?fù)涞葍r，這是比較容易理解的一個拓?fù)湫再|(zhì)。
在拓?fù)鋵W(xué)里不討論兩個圖形全等的概念，但是討論拓?fù)涞葍r的概念。比如，盡管圓和方形、三角形的形狀、大小不同，在拓?fù)渥儞Q下，它們都是等價圖形。左圖的三樣?xùn)|西就是拓?fù)涞葍r的，換句話講，就是從拓?fù)鋵W(xué)的角度看，它們是完全一樣的。
在一個球面上任選一些點用不相交的線把它們連接起來，這樣球面就被這些線分成許多塊。在拓?fù)渥儞Q下，點、線、塊的數(shù)目仍和原來的數(shù)目一樣，這就是拓?fù)涞葍r。一般地說，對于任意形狀的閉曲面，只要不把曲面撕裂或割破，他的變換就是拓?fù)渥儞Q，就存在拓?fù)涞葍r。
應(yīng)該指出，環(huán)面不具有這個性質(zhì)。比如像左圖那樣，把環(huán)面切開，它不至于分成許多塊，只是變成一個彎曲的圓桶形，對于這種情況，我們就說球面不能拓?fù)涞淖兂森h(huán)面。所以球面和環(huán)面在拓?fù)鋵W(xué)中是不同的曲面。
直線上的點和線的結(jié)合關(guān)系、順序關(guān)系，在拓?fù)渥儞Q下不變，這是拓?fù)湫再|(zhì)。在拓?fù)鋵W(xué)中曲線和曲面的閉合性質(zhì)也是拓?fù)湫再|(zhì)。
我們通常講的平面、曲面通常有兩個面，就像一張紙有兩個面一樣。但德國數(shù)學(xué)家莫比烏斯(1790～1868)在1858年發(fā)現(xiàn)了莫比烏斯曲面。這種曲面就不能用不同的顏色來涂滿兩個側(cè)面。
拓?fù)渥儞Q的不變性、不變量還有很多，這里不在介紹。
拓?fù)鋵W(xué)建立后，由于其它數(shù)學(xué)學(xué)科的發(fā)展需要，它也得到了迅速的發(fā)展。特別是伯恩哈德·黎曼創(chuàng)立黎曼幾何以后，他把拓?fù)鋵W(xué)概念作為分析函數(shù)論的基礎(chǔ)，更加促進了拓?fù)鋵W(xué)的進展。
二十世紀(jì)以來，集合論被引進了拓?fù)鋵W(xué)，為拓?fù)鋵W(xué)開拓了新的面貌。拓?fù)鋵W(xué)的研究就變成了關(guān)于任意點集的對應(yīng)的概念。拓?fù)鋵W(xué)中一些需要精確化描述的問題都可以應(yīng)用集合來論述。
因為大量自然現(xiàn)象具有連續(xù)性，所以拓?fù)鋵W(xué)具有廣泛聯(lián)系各種實際事物的可能性。通過拓?fù)鋵W(xué)的研究，可以闡明空間的集合結(jié)構(gòu)，從而掌握空間之間的函數(shù)關(guān)系。本世紀(jì)三十年代以后，數(shù)學(xué)家對拓?fù)鋵W(xué)的研究更加深入，提出了許多全新的概念。比如，一致性結(jié)構(gòu)概念、抽像距概念和近似空間概念等等。有一門數(shù)學(xué)分支叫做導(dǎo)數(shù)幾何，是用微分工具來研究曲線、曲面等在一點附近的彎曲情況，而拓?fù)鋵W(xué)是研究曲面的全局聯(lián)系的情況，因此，這兩門學(xué)科應(yīng)該存在某種本質(zhì)的聯(lián)系。1945年，美籍華人數(shù)學(xué)家陳省身建立了代數(shù)拓?fù)?/a>和微分幾何的聯(lián)系，并推進了整體幾何學(xué)的發(fā)展。
拓?fù)鋵W(xué)發(fā)展到今天，在理論上已經(jīng)十分明顯分成了兩個分支。一個分支是偏重于用分析的方法來研究的，叫做點集拓?fù)鋵W(xué)，或者叫做分析拓?fù)鋵W(xué)。另一個分支是偏重于用代數(shù)方法來研究的，叫做代數(shù)拓?fù)洹，F(xiàn)時，這兩個分支又有統(tǒng)一的趨勢。拓?fù)鋵W(xué)在泛函分析、李群論、微分幾何、微分方程和其他許多數(shù)學(xué)分支。
參考資料 >