圖論〔Graph Theory〕是數(shù)學(xué)的一個(gè)分支。它以圖為研究對(duì)象。圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來(lái)描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。一些由結(jié)點(diǎn)及邊構(gòu)成的圖稱為線圖。在線圖中，結(jié)點(diǎn)的位置分布和邊的長(zhǎng)短曲直都可以任意描畫，這并不改變實(shí)際問(wèn)題的性質(zhì)。我們關(guān)心的是它有多少個(gè)結(jié)點(diǎn)，在哪些結(jié)點(diǎn)間有邊相連，以及整個(gè)線圖具有的某些特性。

概述

圖G=（V,E）是一個(gè)二元組（V,E）使得E?[V]的平方，所以E的元素是V的2-元子集。為了避免符號(hào)上的混淆，我們總是默認(rèn)V∩B=?。集合V中的元素稱為圖G的定點(diǎn)（或節(jié)點(diǎn)、點(diǎn)），而集合E的元素稱為邊（或線）。通常，描繪一個(gè)圖的方法是把定點(diǎn)畫成一個(gè)小圓圈，如果相應(yīng)的頂點(diǎn)之間有一條邊，就用一條線連接這兩個(gè)小圓圈，如何繪制這些小圓圈和連線時(shí)無(wú)關(guān)緊要的，重要的是要正確體現(xiàn)哪些頂點(diǎn)對(duì)之間有邊，哪些頂點(diǎn)對(duì)之間沒(méi)有邊。

圖論本身是應(yīng)用數(shù)學(xué)的一部份，因此，歷史上圖論曾經(jīng)被好多位數(shù)學(xué)家各自獨(dú)立地建立過(guò)。關(guān)于圖論的文字記載最早出現(xiàn)在歐拉1736年的論著中，他所考慮的原始問(wèn)題有很強(qiáng)的實(shí)際背景。

起源

眾所周知，圖論起源于一個(gè)非常經(jīng)典的問(wèn)題——柯尼斯堡（Konigsberg）問(wèn)題。

1738年，瑞典數(shù)學(xué)家歐拉 - Leornhard?Euler解決了柯尼斯堡問(wèn)題。由此圖論誕生。歐拉也成為圖論的創(chuàng)始人。

1859年，英國(guó)數(shù)學(xué)家漢密爾頓發(fā)明了一種游戲：用一個(gè)規(guī)則的實(shí)心十二面體，它的20個(gè)頂點(diǎn)標(biāo)出世界著名的20個(gè)城市，要求游戲者找一條沿著各邊通過(guò)每個(gè)頂點(diǎn)剛好一次的閉回路，即“繞行世界”。用圖論的語(yǔ)言來(lái)說(shuō)，游戲的目的是在十二面體的圖中找出一個(gè)生成圈。這個(gè)生成圈后來(lái)被稱為漢密爾頓回路。這個(gè)問(wèn)題后來(lái)就叫做漢密爾頓問(wèn)題。由于運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)和編碼理論中的很多問(wèn)題都可以化為漢密爾頓問(wèn)題，從而引起廣泛的注意和研究。

猜想

在圖論的歷史中，還有一個(gè)最著名的問(wèn)題－－四色猜想。這個(gè)猜想說(shuō)，在一個(gè)平面或球面上的任何地圖能夠只用四種顏色來(lái)著色，使得沒(méi)有兩個(gè)相鄰的國(guó)家有相同的顏色。每個(gè)國(guó)家必須由一個(gè)單連通域構(gòu)成，而兩個(gè)國(guó)家相鄰是指它們有一段公共的邊界，而不僅僅只有一個(gè)公共點(diǎn)。這一問(wèn)題最早于1852年由Francis?Guthrie提出，最早的文字記載則現(xiàn)于德摩根于同一年寫給哈密頓的信上。包括凱萊、肯普等在內(nèi)的許多人都曾給出過(guò)錯(cuò)誤的證明。

泰特 - Tait、希伍德 - Heawood、拉姆齊和哈德維格 - Hadwiger對(duì)此問(wèn)題的研究與推廣引發(fā)了對(duì)嵌入具有不同虧格的曲面的圖的著色問(wèn)題的研究。一百多年后，四色問(wèn)題仍未解決。1969年，Heinrich?Heesch發(fā)表了一個(gè)用計(jì)算機(jī)解決此問(wèn)題的方法。1976年，阿佩爾 - Appel和哈肯 - Haken借助計(jì)算機(jī)給出了一個(gè)證明，此方法按某些性質(zhì)將所有地圖分為1936類并利用計(jì)算機(jī)，運(yùn)行了1200個(gè)小時(shí)，驗(yàn)正了它們可以用四種顏色染色。

四色定理是第一個(gè)主要由電腦證明的理論，這一證明并不被所有的數(shù)學(xué)家接受，因?yàn)椴捎玫姆椒ú荒苡扇斯ぶ苯域?yàn)證。最終，人們必須對(duì)電腦編譯的正確性以及運(yùn)行這一程序的硬件設(shè)備充分信任。主要是因?yàn)榇俗C明缺乏數(shù)學(xué)應(yīng)有的規(guī)范，以至于有人這樣評(píng)論“一個(gè)好的數(shù)學(xué)證明應(yīng)當(dāng)像一首詩(shī)——而這純粹是一本電話簿！”

雖然四色定理證明了任何地圖可以只用四個(gè)顏色著色，但是這個(gè)結(jié)論對(duì)于現(xiàn)實(shí)上的應(yīng)用卻相當(dāng)有限?，F(xiàn)實(shí)中的地圖常會(huì)出現(xiàn)飛地，即兩個(gè)不連通的區(qū)域?qū)儆谕粋€(gè)國(guó)家的情況（例如美國(guó)的阿拉斯加州），而制作地圖時(shí)我們?nèi)詴?huì)要求這兩個(gè)區(qū)域被涂上同樣的顏色，在這種情況下，四個(gè)顏色將會(huì)是不夠用的。

20世紀(jì)80-90年代曾邦哲的綜合系統(tǒng)論（結(jié)構(gòu)論）觀將“四色猜想”命題轉(zhuǎn)換等價(jià)為“互鄰面最大的多面體是四面體”。每個(gè)地圖可以導(dǎo)出一個(gè)圖，其中國(guó)家都是點(diǎn)，當(dāng)相應(yīng)的兩個(gè)國(guó)家相鄰時(shí)這兩個(gè)點(diǎn)用一條線來(lái)連接。所以四色猜想是圖論中的一個(gè)問(wèn)題。它對(duì)圖的著色理論、平面圖理論、代數(shù)拓?fù)鋱D論等分支的發(fā)展起到推動(dòng)作用。

（下圖是在上下對(duì)折再左右對(duì)折以后形成一個(gè)輪胎形狀，有7個(gè)區(qū)域兩兩相連，就是說(shuō)在一個(gè)環(huán)面上作圖，需要7種顏色，外國(guó)數(shù)學(xué)家構(gòu)造林格證明：Np=[ - 7+√1+48p/2]，p=1，N1=7。

圖論的廣泛應(yīng)用，促進(jìn)了它自身的發(fā)展。20世紀(jì)40-60年代，擬陣?yán)碚?、超圖理論、極圖理論，以及代數(shù)圖論、拓?fù)鋱D論等都有很大的發(fā)展。

拓?fù)鋵W(xué)

幾何拓?fù)鋵W(xué)是十九世紀(jì)形成的一門數(shù)學(xué)分支，它屬于幾何學(xué)的范疇。有關(guān)拓?fù)鋵W(xué)的一些內(nèi)容早在十八世紀(jì)就出現(xiàn)了。那時(shí)候發(fā)現(xiàn)一些孤立的問(wèn)題，后來(lái)在拓?fù)鋵W(xué)的形成中占著重要的地位。

在數(shù)學(xué)上，關(guān)于哥尼斯堡七橋問(wèn)題、多面體的歐拉定理、四色問(wèn)題等都是拓?fù)鋵W(xué)發(fā)展史的重要問(wèn)題。

哥尼斯堡（今俄羅斯加里寧格勒）是東普魯士的首都，普萊格爾河橫貫其中。十八世紀(jì)在這條河上建有七座橋，將河中間的兩個(gè)島和河岸聯(lián)結(jié)起來(lái)。人們閑暇時(shí)經(jīng)常在這上邊散步，一天有人提出：能不能每座橋都只走一遍，最后又回到原來(lái)的位置。這個(gè)問(wèn)題看起來(lái)很簡(jiǎn)單有很有趣的問(wèn)題吸引了大家，很多人在嘗試各種各樣的走法，但誰(shuí)也沒(méi)有做到?？磥?lái)要得到一個(gè)明確、理想的答案還不那么容易。

1736年，有人帶著這個(gè)問(wèn)題找到了當(dāng)時(shí)的大數(shù)學(xué)家歐拉，歐拉經(jīng)過(guò)一番思考，很快就用一種獨(dú)特的方法給出了解答。歐拉把這個(gè)問(wèn)題首先簡(jiǎn)化，他把兩座小島和河的兩岸分別看作四個(gè)點(diǎn)，而把七座橋看作這四個(gè)點(diǎn)之間的連線。那么這個(gè)問(wèn)題就簡(jiǎn)化成，能不能用一筆就把這個(gè)圖形畫出來(lái)。經(jīng)過(guò)進(jìn)一步的分析，歐拉得出結(jié)論－－不可能每座橋都走一遍，最后回到原來(lái)的位置。并且給出了所有能夠一筆畫出來(lái)的圖形所應(yīng)具有的條件。這是拓?fù)鋵W(xué)的“先聲”。

在拓?fù)鋵W(xué)的發(fā)展歷史中，還有一個(gè)著名而且重要的關(guān)于多面體的定理也和歐拉有關(guān)。這個(gè)定理內(nèi)容是：如果一個(gè)凸多面體的頂點(diǎn)數(shù)是v、棱數(shù)是e、面數(shù)是f，那么它們總有這樣的關(guān)系：f+v-e=2。

根據(jù)多面體的歐拉定理，可以得出這樣一個(gè)有趣的事實(shí)：只存在五種正多面體。它們是正四面體、正六面體、正八面體、正十二面體、正二十面體。