圖論

前言

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

內(nèi)容概要

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

書籍目錄

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

章節(jié)摘錄

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

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    圖論 PDF格式下載

---