原書(shū)前言我們常常認(rèn)為數(shù)學(xué)理應(yīng)享有較高的聲譽(yù)，但事實(shí)并非如此。數(shù)學(xué)中的很多領(lǐng)域都讓人感覺(jué)枯燥，需要花費(fèi)大量的精力去學(xué)習(xí)和理解。近年來(lái)，有許多學(xué)術(shù)文章對(duì)美國(guó)高中生和其他國(guó)家的學(xué)生在數(shù)學(xué)和科學(xué)方面加以比較，得出了獲得數(shù)學(xué)專業(yè)研究生學(xué)位的學(xué)生越來(lái)越少的報(bào)告。無(wú)論什么原因，事實(shí)是沒(méi)有足夠多的有天賦的美國(guó)學(xué)生對(duì)學(xué)習(xí)數(shù)學(xué)感到很開(kāi)心。許多美國(guó)學(xué)生都在錯(cuò)失學(xué)習(xí)數(shù)學(xué)的機(jī)會(huì)。事實(shí)上，有許多數(shù)學(xué)分支是很有意思的。在這些領(lǐng)域內(nèi)的許多有趣的定理背后都包含著一段這個(gè)定理由來(lái)的歷史，一個(gè)關(guān)于那些甘于奉獻(xiàn)的數(shù)學(xué)家們?nèi)绾伟l(fā)現(xiàn)這些有趣和重要定理的故事。這些定理不一定是被專門鉆研這個(gè)方向的人們發(fā)現(xiàn)，還有許多時(shí)候是意外收獲。這些定理的證明對(duì)數(shù)學(xué)及其他領(lǐng)域是十分有用的，本書(shū)十分榮幸能給您介紹這樣一個(gè)數(shù)學(xué)領(lǐng)域，歡迎來(lái)到圖論的迷人世界。 像其他專業(yè)領(lǐng)域一樣，數(shù)學(xué)由許多方向組成，它們之間有共性，但也有自己特有的鮮明特征。有些方向可能你很熟悉，比如代數(shù)、幾何、三角函數(shù)和微積分，學(xué)習(xí)和理解這些學(xué)科可能會(huì)需要你努力研習(xí)，當(dāng)然這些領(lǐng)域也很有趣。事實(shí)上，學(xué)習(xí)任何學(xué)科都很有趣。但是，這些有趣的數(shù)學(xué)領(lǐng)域從哪里來(lái)呢？答案是它來(lái)自于人們本身，來(lái)自于他們的好奇心、他們的想象力、他們的聰明才智。雖然有些人是數(shù)學(xué)家，但也有些人不是，其中有些就是學(xué)生就像你我，或者當(dāng)年的你我。 我們的目的是在這里向您介紹一個(gè)也許比較陌生的圖論領(lǐng)域。我們希望向您展示數(shù)學(xué)的樂(lè)趣所在。我們相信您能感覺(jué)到數(shù)學(xué)不僅有趣而且還會(huì)為之激動(dòng)。我們不僅要介紹這些有趣的結(jié)果，同樣期待能和您分享發(fā)現(xiàn)和解決這些問(wèn)題的方法。 在這里我們可以看到，一個(gè)有趣的問(wèn)題往往不是用數(shù)學(xué)方法解決完就完成了任務(wù)，而是經(jīng)常會(huì)引出一整套數(shù)學(xué)理論。盡管本書(shū)不打算深入鉆研一些太高深的數(shù)學(xué)問(wèn)題，但是我們會(huì)給出其中的一些思想或者思路來(lái)說(shuō)明其正確性。 第一章以一些好玩的問(wèn)題作為引子，這些問(wèn)題給出了這本以圖論為主題的數(shù)學(xué)書(shū)中的主要概念。其中的一些問(wèn)題具有歷史性意義，當(dāng)我們擁有足夠多的信息來(lái)解決它們時(shí)，我們會(huì)重新拾起它們。這一部分初步探討了圖論中的一些基本數(shù)學(xué)概念。在這一章的最后，我們給出了一個(gè)通常被稱為圖論第一定理的定理，用來(lái)處理一個(gè)所有頂點(diǎn)都賦予了度數(shù)的圖的問(wèn)題。第二章從一場(chǎng)數(shù)學(xué)領(lǐng)域中的定理選美大賽來(lái)展開(kāi)。我們看到，在最美麗的數(shù)學(xué)定理列表中不僅出現(xiàn)了關(guān)于圖論的定理，而且一個(gè)在圖論方面地位尤其特殊的數(shù)學(xué)家出現(xiàn)了。其中的一個(gè)定理引導(dǎo)我們步入圖論中研究較多的一類圖，即正則圖。從這時(shí)開(kāi)始，圖的頂點(diǎn)的度數(shù)和長(zhǎng)度都將加以討論。本章的其余部分是關(guān)于圖的結(jié)構(gòu)的一些概念和思想。這章以圖論中一個(gè)尚未解決的問(wèn)題結(jié)束。 第三章討論了一個(gè)圖所具備的最基本性質(zhì)，在任何兩個(gè)地點(diǎn)之間都可以互相旅行。這產(chǎn)生了圖中的各點(diǎn)之間的距離問(wèn)題，這個(gè)位置對(duì)應(yīng)于所給定的位置是近還是遠(yuǎn)。這章還有一個(gè)幽默的概念，即厄多斯數(shù)，這個(gè)概念是在描述與厄多斯合作過(guò)的數(shù)學(xué)家以及與與厄多斯合作過(guò)的數(shù)學(xué)家合作過(guò)的數(shù)學(xué)家以及……第四章介紹了一個(gè)連通圖擁有的最簡(jiǎn)單的結(jié)構(gòu)，引導(dǎo)我們認(rèn)識(shí)樹(shù)形圖因?yàn)樗鼈兛雌饋?lái)像樹(shù)。這類圖可以和化學(xué)聯(lián)系在一起，也能夠幫助我們解決一些需要做一系列決斷的決策問(wèn)題。本章最后討論了一個(gè)實(shí)際問(wèn)題，就是設(shè)計(jì)一個(gè)成本最低的公路系統(tǒng)，使我們?cè)谙到y(tǒng)中任何兩個(gè)位置之間可以旅行。 圖論有一個(gè)相當(dāng)奇特的歷史。這一領(lǐng)域的大部分知識(shí)開(kāi)始于18世紀(jì)，那是天才的數(shù)學(xué)家萊昂哈德·歐拉提出和解決哥尼斯堡七橋問(wèn)題，接著又描述了一個(gè)值得思考的更復(fù)雜的問(wèn)題的時(shí)代。這產(chǎn)生了一類圖形，我們以歐拉為之命名，并在第五章研究它，這一章還提起了另一個(gè)眾所周知的問(wèn)題中國(guó)郵遞員問(wèn)題，這是一個(gè)關(guān)于郵遞員進(jìn)行一次環(huán)形巡游的最短路程問(wèn)題。 第六章討論了以19世紀(jì)一個(gè)著名的物理學(xué)家和數(shù)學(xué)家命名的圖的問(wèn)題，這個(gè)人是威廉·羅恩·哈密爾頓爵士。雖然哈密爾頓很少處理圖論問(wèn)題，但是他提出了十二面體代數(shù)系統(tǒng)，這促使他發(fā)明了一個(gè)在十二面體中尋找環(huán)形路徑的游戲，且每個(gè)頂點(diǎn)恰好經(jīng)過(guò)一次。20世紀(jì)中期的知識(shí)大爆炸也包含了這方面的內(nèi)容。這章以一個(gè)重要的實(shí)際問(wèn)題結(jié)束，即找到一個(gè)最短的或者最省錢的環(huán)形路徑使其經(jīng)過(guò)這個(gè)系統(tǒng)中的每個(gè)地方。 有一個(gè)問(wèn)題是關(guān)于一些對(duì)象的集合是否足夠用以與另一個(gè)對(duì)象的集合匹配例如申請(qǐng)工作匹配或人與人之間的匹配。這種問(wèn)題會(huì)在第七章中討論。在19世紀(jì)末第一次提出將圖論作為數(shù)學(xué)的一個(gè)理論領(lǐng)域，并且確立了圖這個(gè)詞，也就是我們這本書(shū)所討論的主要內(nèi)容，從這章中我們可以了解到一個(gè)賽制安排有多少種不同的方案。第八章關(guān)注的問(wèn)題是一個(gè)圖能否被分為其他特定類型的圖，主要是圈。一些具體的完全圖是否能以某種方式被分為三角形圈，這種情況對(duì)應(yīng)了19世紀(jì)中期數(shù)學(xué)家托馬斯·柯克曼提出并解決的通常被冠以柯克曼女生問(wèn)題之后的問(wèn)題。還介紹了圖分解問(wèn)題和圖的頂點(diǎn)被整數(shù)適當(dāng)標(biāo)記并生成邊的標(biāo)記問(wèn)題之間的聯(lián)系。本章的最后以一個(gè)名為四色方柱的趣味游戲以及基于圖論知識(shí)的解決方案收尾。 通常會(huì)有這樣的情況發(fā)生，游歷中涉及單行道，為了在圖中將它模型化，在邊上標(biāo)明方向是有必要的。這產(chǎn)生了定向圖的概念，這樣的結(jié)構(gòu)也可以用于表示比賽中一支隊(duì)伍戰(zhàn)勝另一支隊(duì)伍。對(duì)于這類數(shù)學(xué)問(wèn)題會(huì)出現(xiàn)在第九章。這章還有一個(gè)大討論，即各種各樣的投票技術(shù)可以產(chǎn)生意想不到的結(jié)果。 一些有趣的問(wèn)題可以看作一個(gè)圖是否可以在平面上沒(méi)有交叉邊地被畫出。在第十章中借助可平面圖的概念可以處理這類問(wèn)題，其中討論了一個(gè)磚廠問(wèn)題，源自于第二次世界大戰(zhàn)時(shí)的一個(gè)集中營(yíng)。 數(shù)學(xué)中最著名的問(wèn)題之一就是任何一個(gè)地圖的區(qū)域能否用四種顏色區(qū)分，使得有相鄰邊界的兩個(gè)區(qū)域顏色不同？這個(gè)四色問(wèn)題是在19世紀(jì)中期一個(gè)年輕的英國(guó)數(shù)學(xué)家提出的，當(dāng)時(shí)三等分角和化圓為方的問(wèn)題已經(jīng)在社會(huì)上眾所周知，而四色問(wèn)題又悄悄地傳播開(kāi)來(lái)，問(wèn)題出名不僅是因?yàn)榻鉀Q這個(gè)問(wèn)題的時(shí)間跨度長(zhǎng)，還因?yàn)樗�的解決方法，在第十一章中我們會(huì)對(duì)其進(jìn)行討論。這引出了給一個(gè)圖的頂點(diǎn)著色，并且怎樣用其解決一系列問(wèn)題的討論，例如，從日程安排到交通指示燈階段變化的問(wèn)題。 有趣的不僅僅是給一個(gè)圖的頂點(diǎn)著色，無(wú)論是從實(shí)踐的觀點(diǎn)，還是理論的觀點(diǎn)，給它的邊著色都是值得關(guān)注的。這就是第十二章的主題。這也可以幫助我們解決一類日程安排問(wèn)題，這也引出了圖論中我們稱之為拉姆齊數(shù)的一系列數(shù)值。這章還包括一個(gè)有趣的問(wèn)題，叫作道路著色問(wèn)題，它告訴我們?cè)谀承┨囟ǖ膬H包含單行道的交通系統(tǒng)中，每個(gè)地方都有相同數(shù)目的道路出口，那么道路可以被著色使得給出的一系列方向就必然能到達(dá)指定地點(diǎn)。 而這本書(shū)的最主要的目的是為了說(shuō)明數(shù)學(xué)的一個(gè)分支可以如此有趣（有時(shí)還很神秘），這本書(shū)也可以用作習(xí)題集。本書(shū)最后有包括書(shū)中的所有章節(jié)的練習(xí)題。 最后，我很高興能夠得到非常專業(yè)的普林斯頓大學(xué)出版社員工的好評(píng)，尤其是維基·科恩（Vickie Kearn）、薩拉·勒納（Sara Lerner）、艾莉森·紐齊斯（Alison Anuzis）、奎因·法斯�。≦uinn Fusting），還有我們最初原稿的匿名審稿人，他們的評(píng)論、反饋以及對(duì)細(xì)節(jié)的關(guān)注對(duì)這本書(shū)的改進(jìn)十分有幫助。在此表示我們誠(chéng)摯的感謝。