圖論〔Graph Theory〕是數學的一個分支。它以圖為研究對象。圖論中的圖是由若干給定的點及連線兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關係，用點代表事物，用連線兩點的線表示相應兩個事物間具有這種關係。
基本介紹
- 中文名：圖論
- 外文名：Graph Theory
- 提出者：歐拉
- 提出時間：1736年
- 套用學科：數學
- 適用領域範圍：數學
概述,起源,猜想,拓撲學,拓撲學與圖論的關聯,簡介,概述,性質,
概述
圖G=（V,E）是一個二元組（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。為了避免符號上的混淆，我們總是默認V∩B=Ø。集合V中的元素稱為圖G的定點（或節點、點），而集合E的元素稱為邊（或線）。通常，描繪一個圖的方法是把定點畫成一個小圓圈，如果相應的頂點之間有一條邊，就用一條線連線這兩個小圓圈，如何繪製這些小圓圈和連線時無關緊要的，重要的是要正確體現哪些頂點對之間有邊，哪些頂點對之間沒有邊。
起源
眾所周知，圖論起源於一個非常經典的問題——柯尼斯堡（Konigsberg）問題。
1738年，瑞典數學家歐拉( Leornhard Euler)解決了柯尼斯堡問題。由此圖論誕生。歐拉也成為圖論的創始人。
1859年，英國數學家漢密爾頓發明了一種遊戲：用一個規則的實心十二面體，它的20個頂點標出世界著名的20個城市，要求遊戲者找一條沿著各邊通過每個頂點剛好一次的閉迴路，即“繞行世界”。用圖論的語言來說，遊戲的目的是在十二面體的圖中找出一個生成圈。這個生成圈後來被稱為漢密爾頓迴路。這個問題後來就叫做漢密爾頓問題。由於運籌學、計算機科學和編碼理論中的很多問題都可以化為漢密爾頓問題，從而引起廣泛的注意和研究。
猜想
在圖論的歷史中，還有一個最著名的問題－－四色猜想。這個猜想說，在一個平面或球面上的任何地圖能夠只用四種顏色來著色，使得沒有兩個相鄰的國家有相同的顏色。每個國家必須由一個單連通域構成，而兩個國家相鄰是指它們有一段公共的邊界，而不僅僅只有一個公共點。這一問題最早於1852年由Francis Guthrie提出，最早的文字記載則現於德摩根於同一年寫給哈密頓的信上。包括凱萊、肯普等在內的許多人都曾給出過錯誤的證明。泰特(Tait)、希伍德(Heawood)、拉姆齊和哈德維格(Hadwiger)對此問題的研究與推廣引發了對嵌入具有不同虧格的曲面的圖的著色問題的研究。一百多年後，四色問題仍未解決。1969年，Heinrich Heesch發表了一個用計算機解決此問題的方法。1976年，阿佩爾(Appel)和哈肯(Haken)藉助計算機給出了一個證明，此方法按某些性質將所有地圖分為1936類並利用計算機，運行了1200個小時，驗正了它們可以用四種顏色染色。四色定理是第一個主要由電腦證明的理論，這一證明並不被所有的數學家接受，因為採用的方法不能由人工直接驗證。最終，人們必須對電腦編譯的正確性以及運行這一程式的硬體設備充分信任。主要是因為此證明缺乏數學應有的規範，以至於有人這樣評論“一個好的數學證明應當像一首詩——而這純粹是一本電話簿！”
雖然四色定理證明了任何地圖可以只用四個顏色著色，但是這個結論對於現實上的套用卻相當有限。現實中的地圖常會出現飛地，即兩個不連通的區域屬於同一個國家的情況（例如美國的阿拉斯加州），而製作地圖時我們仍會要求這兩個區域被塗上同樣的顏色，在這種情況下，四個顏色將會是不夠用的。
20世紀80-90年代曾邦哲的綜合系統論（結構論）觀將“四色猜想”命題轉換等價為“互鄰面最大的多面體是四面體”。每個地圖可以導出一個圖，其中國家都是點，當相應的兩個國家相鄰時這兩個點用一條線來連線。所以四色猜想是圖論中的一個問題。它對圖的著色理論、平面圖理論、代數拓撲圖論等分支的發展起到推動作用。
（下圖是在上下對摺再左右對摺以後形成一個輪胎形狀，有7個區域兩兩相連，就是說在一個環面上作圖，需要7種顏色，外國數學家構造林格證明：Np=[(7+√1+48p)/2]，p=1，N1=7。
拓撲學
幾何拓撲學是十九世紀形成的一門數學分支，它屬於幾何學的範疇。有關拓撲學的一些內容早在十八世紀就出現了。那時候發現一些孤立的問題，後來在拓撲學的形成中占著重要的地位。
哥尼斯堡（今俄羅斯加里寧格勒）是東普魯士的首都，普萊格爾河橫貫其中。十八世紀在這條河上建有七座橋，將河中間的兩個島和河岸聯結起來。人們閒暇時經常在這上邊散步，一天有人提出：能不能每座橋都只走一遍，最後又回到原來的位置。這個問題看起來很簡單有很有趣的問題吸引了大家，很多人在嘗試各種各樣的走法，但誰也沒有做到。看來要得到一個明確、理想的答案還不那么容易。
1736年，有人帶著這個問題找到了當時的大數學家歐拉，歐拉經過一番思考，很快就用一種獨特的方法給出了解答。歐拉把這個問題首先簡化，他把兩座小島和河的兩岸分別看作四個點，而把七座橋看作這四個點之間的連線。那么這個問題就簡化成，能不能用一筆就把這個圖形畫出來。經過進一步的分析，歐拉得出結論－－不可能每座橋都走一遍，最後回到原來的位置。並且給出了所有能夠一筆畫出來的圖形所應具有的條件。這是拓撲學的“先聲”。
拓撲學與圖論的關聯
簡介
四色猜想的提出來自英國。1852年，畢業於倫敦大學的弗南西斯.格思里來到一家科研單位搞地圖著色工作時，發現了一種有趣的現象：“看來，每幅地圖都可以用四種顏色著色，使得有共同邊界的國家都被著上不同的顏色。”
進入20世紀以來，科學家們對四色猜想的證明基本上是按照肯普的想法在進行。電子計算機問世以後，由於演算速度迅速提高，加之人機對話的出現，大大加快了對四色猜想證明的進程。1976年，美國數學家阿佩爾與哈肯在美國伊利諾斯大學的兩台不同的電子計算機上，用了1200個小時，作了100億判斷，終於完成了四色定理的證明。不過不少數學家並不滿足於計算機取得的成就，他們認為應該有一種簡捷明快的書面證明方法。
上面的幾個例子所講的都是一些和幾何圖形有關的問題，但這些問題又與傳統的幾何學不同，而是一些新的幾何概念。這些就是“拓撲學”的先聲。
概述
拓撲學的英文名是Topology，直譯是地誌學，也就是和研究地形、地貌相類似的有關學科。我國早期曾經翻譯成“形勢幾何學”、“連續幾何學”、“一對一的連續變換群下的幾何學”，但是，這幾種譯名都不大好理解，1956年統一的《數學名詞》把它確定為拓撲學，這是按音譯過來的。
拓撲學是幾何學的一個分支，但是這種幾何學又和通常的平面幾何、立體幾何不同。通常的平面幾何或立體幾何研究的對象是點、線、面之間的位置關係以及它們的度量性質。拓撲學對於研究對象的長短、大小、面積、體積等度量性質和數量關係都無關。
舉例來說，在通常的平面幾何里，把平面上的一個圖形搬到另一個圖形上，如果完全重合，那么這兩個圖形叫做全等形。但是，在拓撲學裡所研究的圖形，在運動中無論它的大小或者形狀都發生變化。在拓撲學裡沒有不能彎曲的元素，每一個圖形的大小、形狀都可以改變。例如，前面講的歐拉在解決哥尼斯堡七橋問題的時候，他畫的圖形就不考慮它的大小、形狀，僅考慮點和線的個數。這些就是拓撲學思考問題的出發點。
性質
拓撲性質有那些呢？首先我們介紹拓撲等價，這是比較容易理解的一個拓撲性質。
在拓撲學裡不討論兩個圖形全等的概念，但是討論拓撲等價的概念。比如，儘管圓和方形、三角形的形狀、大小不同，在拓撲變換下，它們都是等價圖形。左圖的三樣東西就是拓撲等價的，換句話講，就是從拓撲學的角度看，它們是完全一樣的。
在一個球面上任選一些點用不相交的線把它們連線起來，這樣球面就被這些線分成許多塊。在拓撲變換下，點、線、塊的數目仍和原來的數目一樣，這就是拓撲等價。一般地說，對於任意形狀的閉曲面，只要不把曲面撕裂或割破，他的變換就是拓撲變換，就存在拓撲等價。
直線上的點和線的結合關係、順序關係，在拓撲變換下不變，這是拓撲性質。在拓撲學中曲線和曲面的閉合性質也是拓撲性質。
拓撲變換的不變性、不變數還有很多，這裡不在介紹。
二十世紀以來，集合論被引進了拓撲學，為拓撲學開拓了新的面貌。拓撲學的研究就變成了關於任意點集的對應的概念。拓撲學中一些需要精確化描述的問題都可以套用集合來論述。
