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