內容簡介
本書介紹瞭圖論的基本概念,解釋瞭圖論中各種經典問題。例如,熄燈的問題、小生成樹問題、哥尼斯堡七橋問題、中國郵遞員問題、國際象棋中馬的遍曆問題和路的著色問題等等。書中也給齣瞭各種類型的圖,例如,二部圖、歐拉圖、彼得森圖和樹;等等。每一章都為讀者設置瞭練習題,包含瞭具有挑戰性的探索性問題。
目錄
原書內容簡介
原書前言
原書序言
第一章圖論簡介
第二章圖的分類
第三章距離分析
第四章生成樹
第五章遍曆圖
第六章巡迴圖
第七章因子圖
第八章分解圖
第九章定嚮圖
第十章畫法圖
第十一章著色圖
第十二章同步圖
迴顧
練習
參考文獻
姓名索引
數學術語索引
前言/序言
原書前言我們常常認為數學理應享有較高的聲譽,但事實並非如此。數學中的很多領域都讓人感覺枯燥,需要花費大量的精力去學習和理解。近年來,有許多學術文章對美國高中生和其他國傢的學生在數學和科學方麵加以比較,得齣瞭獲得數學專業研究生學位的學生越來越少的報告。無論什麼原因,事實是沒有足夠多的有天賦的美國學生對學習數學感到很開心。許多美國學生都在錯失學習數學的機會。事實上,有許多數學分支是很有意思的。在這些領域內的許多有趣的定理背後都包含著一段這個定理由來的曆史,一個關於那些甘於奉獻的數學傢們如何發現這些有趣和重要定理的故事。這些定理不一定是被專門鑽研這個方嚮的人們發現,還有許多時候是意外收獲。這些定理的證明對數學及其他領域是十分有用的,本書十分榮幸能給您介紹這樣一個數學領域,歡迎來到圖論的迷人世界。
像其他專業領域一樣,數學由許多方嚮組成,它們之間有共性,但也有自己特有的鮮明特徵。有些方嚮可能你很熟悉,比如代數、幾何、三角函數和微積分,學習和理解這些學科可能會需要你努力研習,當然這些領域也很有趣。事實上,學習任何學科都很有趣。但是,這些有趣的數學領域從哪裏來呢?答案是它來自於人們本身,來自於他們的好奇心、他們的想象力、他們的聰明纔智。雖然有些人是數學傢,但也有些人不是,其中有些就是學生——就像你我,或者當年的你我。
我們的目的是在這裏嚮您介紹一個也許比較陌生的圖論領域。我們希望嚮您展示數學的樂趣所在。我們相信您能感覺到數學不僅有趣而且還會為之激動。我們不僅要介紹這些有趣的結果,同樣期待能和您分享發現和解決這些問題的方法。
在這裏我們可以看到,一個有趣的問題往往不是用數學方法解決完就完成瞭任務,而是經常會引齣一整套數學理論。盡管本書不打算深入鑽研一些太高深的數學問題,但是我們會給齣其中的一些思想或者思路來說明其正確性。
第一章以一些好玩的問題作為引子,這些問題給齣瞭這本以圖論為主題的數學書中的主要概念。其中的一些問題具有曆史性意義,當我們擁有足夠多的信息來解決它們時,我們會重新拾起它們。這一部分初步探討瞭圖論中的一些基本數學概念。在這一章的最後,我們給齣瞭一個通常被稱為圖論第一定理的定理,用來處理一個所有頂點都賦予瞭度數的圖的問題。第二章從一場數學領域中的定理選美大賽來展開。我們看到,在最美麗的數學定理列錶中不僅齣現瞭關於圖論的定理,而且一個在圖論方麵地位尤其特殊的數學傢齣現瞭。其中的一個定理引導我們步入圖論中研究較多的一類圖,即正則圖。從這時開始,圖的頂點的度數和長度都將加以討論。本章的其餘部分是關於圖的結構的一些概念和思想。這章以圖論中一個尚未解決的問題結束。
第三章討論瞭一個圖所具備的最基本性質,在任何兩個地點之間都可以互相旅行。這産生瞭圖中的各點之間的距離問題,這個位置對應於所給定的位置是近還是遠。這章還有一個幽默的概念,即厄多斯數,這個概念是在描述與厄多斯閤作過的數學傢以及與“與厄多斯閤作過的數學傢”閤作過的數學傢以及……第四章介紹瞭一個連通圖擁有的最簡單的結構,引導我們認識樹形圖——因為它們看起來像樹。這類圖可以和化學聯係在一起,也能夠幫助我們解決一些需要做一係列決斷的決策問題。本章最後討論瞭一個實際問題,就是設計一個成本最低的公路係統,使我們在係統中任何兩個位置之間可以旅行。
圖論有一個相當奇特的曆史。這一領域的大部分知識開始於18世紀,那是天纔的數學傢萊昂哈德·歐拉提齣和解決哥尼斯堡七橋問題,接著又描述瞭一個值得思考的更復雜的問題的時代。這産生瞭一類圖形,我們以歐拉為之命名,並在第五章研究它,這一章還提起瞭另一個眾所周知的問題——中國郵遞員問題,這是一個關於郵遞員進行一次環形巡遊的最短路程問題。
第六章討論瞭以19世紀一個著名的物理學傢和數學傢命名的圖的問題,這個人是威廉·羅恩·哈密爾頓爵士。雖然哈密爾頓很少處理圖論問題,但是他提齣瞭“十二麵體代數係統”,這促使他發明瞭一個在十二麵體中尋找環形路徑的遊戲,且每個頂點恰好經過一次。20世紀中期的知識大爆炸也包含瞭這方麵的內容。這章以一個重要的實際問題結束,即找到一個最短的或者最省錢的環形路徑使其經過這個係統中的每個地方。
有一個問題是關於一些對象的集閤是否足夠用以與另一個對象的集閤匹配——例如申請工作匹配或人與人之間的匹配。這種問題會在第七章中討論。在19世紀末第一次提齣將圖論作為數學的一個理論領域,並且確立瞭“圖”這個詞,也就是我們這本書所討論的主要內容,從這章中我們可以瞭解到一個賽製安排有多少種不同的方案。第八章關注的問題是一個圖能否被分為其他特定類型的圖,主要是圈。一些具體的完全圖是否能以某種方式被分為三角形圈,這種情況對應瞭19世紀中期數學傢托馬斯·柯剋曼提齣並解決的通常被冠以“柯剋曼女生問題”之後的問題。還介紹瞭圖分解問題和圖的頂點被整數適當標記並生成邊的標記問題之間的聯係。本章的最後以一個名為四色方柱的趣味遊戲以及基於圖論知識的解決方案收尾。
通常會有這樣的情況發生,遊曆中涉及單行道,為瞭在圖中將它模型化,在邊上標明方嚮是有必要的。這産生瞭定嚮圖的概念,這樣的結構也可以用於錶示比賽中一支隊伍戰勝另一支隊伍。對於這類數學問題會齣現在第九章。這章還有一個大討論,即各種各樣的投票技術可以産生意想不到的結果。
一些有趣的問題可以看作一個圖是否可以在平麵上沒有交叉邊地被畫齣。在第十章中藉助可平麵圖的概念可以處理這類問題,其中討論瞭一個磚廠問題,源自於第二次世界大戰時的一個集中營。
數學中最著名的問題之一就是任何一個地圖的區域能否用四種顔色區分,使得有相鄰邊界的兩個區域顔色不同?這個四色問題是在19世紀中期一個年輕的英國數學傢提齣的,當時三等分角和化圓為方的問題已經在社會上眾所周知,而四色問題又悄悄地傳播開來,問題齣名不僅是因為解決這個問題的時間跨度長,還因為它的解決方法,在第十一章中我們會對其進行討論。這引齣瞭給一個圖的頂點著色,並且怎樣用其解決一係列問題的討論,例如,從日程安排到交通指示燈階段變化的問題。
有趣的不僅僅是給一個圖的頂點著色,無論是從實踐的觀點,還是理論的觀點,給它的邊著色都是值得關注的。這就是第十二章的主題。這也可以幫助我們解決一類日程安排問題,這也引齣瞭圖論中我們稱之為拉姆齊數的一係列數值。這章還包括一個有趣的問題,叫作道路著色問題,它告訴我們在某些特定的僅包含單行道的交通係統中,每個地方都有相同數目的道路齣口,那麼道路可以被著色使得給齣的一係列方嚮就必然能到達指定地點。
而這本書的最主要的目的是為瞭說明數學的一個分支可以如此有趣(有時還很神秘),這本書也可以用作習題集。本書最後有包括書中的所有章節的練習題。
最後,我很高興能夠得到非常專業的普林斯頓大學齣版社員工的好評,尤其是維基·科恩(Vickie Kearn)、薩拉·勒納(Sara Lerner)、艾莉森·紐齊斯(Alison Anuzis)、奎因·法斯汀(Quinn Fusting),還有我們最初原稿的匿名審稿人,他們的評論、反饋以及對細節的關注對這本書的改進十分有幫助。在此錶示我們誠摯的感謝。
在傳統的數學書中,典型的寫法是作者從最簡單的、最容易的結論逐步引嚮更為具體並具有挑戰和復雜的結論。這不是我們將在這裏做的,我們的意圖是展示我們以一定順序思考的有趣的、漂亮的素材,讓我們相信這將保持讀者對這門學科的興趣以及對即將發生的事感到驚奇。有時我們會證明這個結論,有時我們齣於某些原因不給證明。當我們沒有給齣證明時,我們將提供給讀者一個直觀感覺或者一個參考,這個參考是已經被發現的一些結論。說到這裏,在這本書的最後附有每個章節的練習題,這也是教授們拿這本書當練習冊的一個原因。
因此,懷著對著名作麯傢和作詞傢斯蒂芬·桑德海姆的愧疚與感激,下麵的詩改編自他的作品:我們將嚮你介紹一些熟悉的,一些特彆的,一些適用於每個人的圖論之夜。
有時定嚮的,經常有關聯的,有意義和超乎意料的圖論之夜。
沒有復雜的,一些完整的,你能確定我們是離散的,方嚮,新應用,四色問題搞定它,微積分的明天,圖論之夜。
圖論 一個迷人的世界 epub pdf mobi txt 電子書 下載 2024
圖論 一個迷人的世界 下載 epub mobi pdf txt 電子書