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