圖論

前言

　　圖論是離散數(shù)學的骨干分支，離散數(shù)學則是計算機科學技術與網(wǎng)絡信息科學的理論基礎。多年來，為了實現(xiàn)高速計算的目的，數(shù)學促進了計算機科學的形成與發(fā)展。例如圖靈機的數(shù)學理論為計算機的誕生打下了基礎；另一方面，隨著計算機科學在社會發(fā)展中作用的日益提升，它又反過來促進數(shù)學的發(fā)展。例如1976年，伊利諾大學的Appel和Haken用計算機證明了四色猜想成立。我國著名數(shù)學家吳文俊、張景中等用計算機進行了幾何定理的機器證明，發(fā)展出一套成熟的機器證明的新理論與新方法。離散數(shù)學，特別是圖論，近年來如異軍突起般蓬勃發(fā)展，實乃數(shù)學與計算機科學交互作用的范例。圖論與計算機科學結盟解決了有關離散事物的結構與關系當中定性與定量的各種優(yōu)化問題。在信息科學與網(wǎng)絡技術迅猛發(fā)展的時代背景之下，接受圖論教育與進行圖論研究成了眾多相關的青年科學家與工程師的強烈追求。圖論自身的美好形象，諸如它的強有力的邏輯，漂亮的圖形，高明的數(shù)學技巧等等，也對每個愛好科學的年輕人產(chǎn)生了揮之不去的誘惑，在高等學校的教學當中，圖論課成了廣大大學生和研究生爭相選修的最受歡迎的熱門課程之一。　　學習圖論，除了能使我們采用它的成果與方法之外，同樣重要的是它能培養(yǎng)我們思考問題與解決問題的能力。圖論中的問題，看似通俗簡單，卻往往含有非平凡的難度，每個學習研究圖論的人在它面前必須全力以赴、嚴肅認真地思考問題，有時百思方得其解，有時則是百思仍不得其解的！

內(nèi)容概要

　　《圖論(第2版)》系統(tǒng)闡述圖論與算法圖論的基本概念、理論、算法及其應用，建立圖的重要矩陣與線性空間，論述計算復雜度理論中的NP完全性理論和著名的一些NPC問題等?！秷D論(第2版)》概念明確，立論嚴謹，語言流暢生動，注重算法分析及其有效性；內(nèi)容全面深入，可讀與可教性強，是一部理想的圖論基礎性著作?！　　秷D論(第2版)》讀者對象為高等院校數(shù)學、計算機科學、信息與網(wǎng)絡等專業(yè)的大學生與研究生，以及科研工作者與圖論愛好者。

書籍目錄

第一章　圖1.1　從哥尼斯堡七橋問題談起1.2　圖的基本概念1.3　軌道和圈*1.4　Brouwer不動點定理1.5　求最短軌長度的算法*1.6　圖上博弈習題第二章　樹2.1　樹的定義與性質(zhì)2.2　生成樹的個數(shù)2.3　求生成樹的算法2.4　求最優(yōu)樹的算法2.5　有序二元樹2.6　n頂有序編碼二元樹的數(shù)目*2.7　最佳追捕問題習題第三章　平面圖3.1　平面圖及其平面嵌入3.2　平面圖Euler公式3.3　極大平面圖3.4　平面圖的充要條件*3.5　平面嵌入的灌木生長算法習題第四章　匹配理論及其應用4.1　匹配與許配4.2　匹配定理4.3　匹配的應用4.4　圖的因子分解習題第五章　著色理論5.1　圖的邊著色5.2　圖的頂著色*5.3　四色猜想為真的機器證明5.4　顏色多項式5.5　獨立集5.6　Ramsey數(shù)習題第六章　Euler圖和Hamilton圖6.1　Euler圖6.2　中國郵遞員問題6.3　Hamilton圖習題第七章　有向圖7.1　弱連通、單連通與強連通7.2　循環(huán)賽圖、有向軌和王7.3　有向Hamilton圖習題第八章　最大流的算法8.1　2F算法*8.2　Dinic分層算法8.3　有上下界網(wǎng)絡最大流的算法8.4　有供需要求的網(wǎng)絡流算法8.5　關于PERT的兩個問題習題第九章連通度9.1　頂連通度9.2　邊連通度*9.3　一種邊數(shù)最少的κ連通圖習題第十章　圖的線性空間與矩陣10.1　圖的線性空間10.2　圖矩陣10.3　開關網(wǎng)絡習題第十一章　圖論中的NPC問題11.1　問題、實例和算法的時間復雜度11.2　Turing機和NPC11.3　滿足問題和Cook定理11.4　圖論中的一些NPC問題習題習題解答與提示參考文獻

章節(jié)摘錄

　　當時數(shù)學界并未對歐拉解決七橋問題的意義有足夠的認識，甚至僅僅視其為一個數(shù)學游戲而已，圖論誕生后并未及時獲得足夠的發(fā)展。1936年，匈牙利數(shù)學家柯尼希（Konig）出版《有限圖與無限圖理論》，這是圖論的第一部專著，它總結了圖論200年的成果，是圖論發(fā)展的第一座里程碑。此后，圖論進入發(fā)展與突破的快車道，又經(jīng)過半個多世紀的發(fā)展，現(xiàn)已成長為數(shù)學科學的一個獨立的重要學科。它的分支很多，例如圖論、算法圖論、極值圖論、網(wǎng)絡圖論、代數(shù)圖論、隨機圖論、模糊圖論、超圖論等等。由于現(xiàn)代科技尤其是大型計算機的迅猛發(fā)展，使圖論大有用武之地，無論是數(shù)學、物理、化學、天文、地理、生物等基礎科學，還是信息、交通、戰(zhàn)爭、經(jīng)濟乃至社會科學的眾多問題，都可以應用圖論方法予以解決。圖論又是計算機科學最重要的基礎之一?！　?976年世界上發(fā)生了不少大事，其中有一件是美國數(shù)學家Appel和Haken在Koch的協(xié)作之下，用計算機證明了圖論難題——四色猜想（4CC）：　　任何地圖，用四種顏色，可以把每國領土染上一種顏色，使鄰國異色?！　?CC的提法和內(nèi)容十分簡樸，以至于可以向隨便一個人（哪怕他不識字）在幾分鐘之內(nèi)講清楚。1852年英國的一個大學生格思里（Guthrie）向他的老師德·摩根（DeMorgan）請教這個問題。德·摩根是當時十分有名的數(shù)學家，他不能判斷這個猜想是否成立，于是很快在數(shù)學界流傳開來。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    圖論 PDF格式下載

---