圖論算法及其MATLAB實現(xiàn)

前言

　　圖論算法廣泛應(yīng)用于物理、化學、運籌學、計算機科學、電子學、信息論、控制論、網(wǎng)絡(luò)理論、管理科學、社會科學等眾多學科領(lǐng)域。隨著這些學科的發(fā)展，特別是計算機科學的快速發(fā)展，又大大促進了圖論和其他學科的發(fā)展?！　D論算法是計算機科學的核心。近幾年，隨著強有力的MATLAB等數(shù)學軟件的迅速發(fā)展，圖論算法在數(shù)學和計算機等各學科方面的應(yīng)用越來越廣泛，從而使各學科的研究者越來越多地重視圖論算法及其MATLAB實現(xiàn)和典型案例，而市場上又缺少這方面的指導性書籍。　　本書將圖論的基礎(chǔ)知識、圖論的著名問題以及相應(yīng)的MATI.AB程序代碼和簡單實例完美地結(jié)合在一起，力求語言簡潔易懂，問題廣泛有趣，算法科學，實例淺顯，增強MATLAB實現(xiàn)的技巧性和操作性。讀者可以通過簡單案例，把圖論的重要算法與MALLAB編程完美結(jié)合?！　”緯η髢?nèi)容豐富，各章節(jié)相互聯(lián)系，具備指導性書籍的系統(tǒng)性、科學性、實用性和引導性；同時，各章又相對獨立，自成體系，為讀者提供極大方便?！　”緯膭?chuàng)新之處在于，每一章均以著名實際問題為引入點，以圖論算法為指導線，運用簡單案例達到與MATLAB實現(xiàn)的完美結(jié)合，真正讓各層次的讀者學會運用圖論理論解決實際問題，從而培養(yǎng)讀者的圖論思維，使讀者驚嘆圖論方法的美妙與魅力。最后還為讀者提供了當今圖論標號方面等未解決的問題。　　本書將在每一章節(jié)中給出著名圖論的算法步驟及其一般MATLAB程序；同時，緊隨每個案例分析，均給出解決問題的。MATLAB源程序，這樣對于初學者來說，具有很強的編程操作性?！　”緯窃谥袊刭|(zhì)大學（北京）王海英多年專業(yè)講義的基礎(chǔ)上重新修訂編寫而成，其中，山東體育學院體育運動學校的李傳濤完成了本書程序的編寫工作；中國科學院數(shù)學與系統(tǒng)科學院的黃強完成了本書全部程序的調(diào)試、修改和圖形繪制等工作，褚寶增教授完成全書的定稿和校正工作。作者相信，此書將開啟圖論算法與MATLAB完美結(jié)合的首頁，也將為更多有實際需求的讀者提供更多的指導?！　∈指兄x中國地質(zhì)大學（北京）2008年教學研究與教學改革立項的支持（項目題目：數(shù)學知識、數(shù)學建模與MATIAB等數(shù)學軟件在實踐中相互結(jié)合的理論研究）！感謝北京航空航天大學出版社的認可、建議和關(guān)心！此外，本文的算法思想均離不開古今中外圖論算法研究的完美理論與應(yīng)用，感謝這些圖論研究者們！

內(nèi)容概要

本書系統(tǒng)介紹了圖論重要算法的思想及其MATLAB實現(xiàn)。    全書分為相對獨立的9章，每章都是解決一類問題的算法思想及其MATLAB實現(xiàn)，首先介紹有關(guān)基礎(chǔ)知識，然后給出相關(guān)著名實際問題及解決此問題的算法思想，最后給出MATLAB實現(xiàn)。第1章主要介紹圖論的基礎(chǔ)知識，同時也給出了可達矩陣的計算，以及關(guān)聯(lián)矩陣和鄰接矩陣的相互轉(zhuǎn)換等重要算法及其MATLAB實現(xiàn)；第2～8章分別介紹最短路、連通圖、樹、Euler圖和Hamilton圖、匹配、網(wǎng)絡(luò)中的流、最小費用流等相關(guān)問題，而且均給出了有關(guān)問題的解決算法及其MATLAB實現(xiàn)；第9章主要介紹染色問題，本章不僅介紹了幾種傳統(tǒng)的染色思想，而且還給出了當今研究領(lǐng)域中非?；钴S的非傳統(tǒng)染色思想，并分別給出其MATLAB實現(xiàn)。    本書可供數(shù)學、計算機科學、工程科學等學科中相關(guān)專業(yè)的大學生、研究生閱讀，也可供相關(guān)專業(yè)研究人員參考。

書籍目錄

第1章　圖論的基礎(chǔ)知識　1.1　圖論的起源　1.2　著名的圖論學者——歐拉　1.3　圖　1.4　特殊圖類　1.5　有向圖　1.6　圖的矩陣表示　　1.6.1　鄰接矩陣　　1.6.2　關(guān)聯(lián)矩陣　1.7　圖論的基本性質(zhì)和定理　1.8　計算有向圖的可達矩陣的算法及其MATLAB實現(xiàn)　1.9　關(guān)聯(lián)矩陣和鄰接矩陣的相互轉(zhuǎn)換算法及其MATLAB實現(xiàn)　習題一第2章 最短路　2.1　路　2.2　最短路問題　2.3　求連通圖最短距離矩陣的算法及其MATLAB實現(xiàn)　2.4　求兩點間最短路的Dijkstra算法及其MATLAB實現(xiàn)　　2.4.1　Dijkstra算法　　2.4.2　Dijkstra算法的MATLAB實現(xiàn)　2.5　求兩點間最短路的改進的Dijkstra算法及其MATLAB實現(xiàn)　　2.5.1　Dijkstra矩陣算法Ⅰ　　2.5.2　Dijkstra矩陣算法Ⅱ　2.6　求兩點間最短路的WarshallFloyd算法及其MATLAB實現(xiàn)　　2.6.1　Floyd算法的基本思想　　2.6.2　Floyd算法的基本步驟　　2.6.3　WarshallFloyd算法的MATLAB實現(xiàn)　2.7　求任意兩點間最短路的算法及其MATLAB實現(xiàn)　2.8　求從一固定點到其他所有點最短路的算法及其MATLAB實現(xiàn)　2.9　求必須通過指定兩個點的最短路的算法及其MATLAB實現(xiàn)　2.10　求圖的兩頂點間最短路與次短路的算法及其MATLAB實現(xiàn)　2.11　求最大可靠路的算法及其MATLAB實現(xiàn)　2.12　求最大期望容量路的算法及其MATLAB實現(xiàn)　習題二第3章 連通圖　3.1　判斷圖的連通性算法及其MATLAB實現(xiàn)　3.2　連通圖的中心和加權(quán)中心的算法及其MATLAB實現(xiàn)　3.3　連通無向圖一般中心的算法及其MATLAB實現(xiàn)　習題三第4章　樹　4.1　樹及其性質(zhì)　4.2　割點、割邊、割集　4.3　二元樹與Huffman樹　　4.3.1　有序二元樹　　4.3.2　Huffman樹　4.4　求Huffman樹及其MATLAB實現(xiàn)　4.5　廣度優(yōu)先搜索算法及其MATLAB實現(xiàn)　4.6　深度優(yōu)先搜索算法及其MATLAB實現(xiàn)　4.7　求割點算法及其MATLAB實現(xiàn)　4.8　生成樹及其個數(shù)　4.9　求無向圖的生成樹算法及其MATLAB實現(xiàn)　4.10　求有向圖的生成樹算法及其MATLAB實現(xiàn)　4.11　求有向連通圖的外向樹與內(nèi)向樹數(shù)目的算法及其MATLAB實現(xiàn)　4.12　最小生成樹問題　4.13　求最小生成樹的Kruskal算法及其MATLAB實現(xiàn)　　4.13.1　Kruskal算法的基本思想　　4.13.2　Kruskal算法的MATLAB實現(xiàn)　4.14　求最小生成樹的Prim算法及其MATLAB實現(xiàn)　　4.14.1　Prim算法的基本思想　　4.14.2　Prim算法的MATLAB實現(xiàn)　習題四第5章　Euler圖和Hamilton圖第6章 匹配問題及其算法第7章 網(wǎng)絡(luò)流的算法第8章 最小費用流及BusackerGowan迭代算法第9章 圖的染色參考文獻

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    圖論算法及其MATLAB實現(xiàn) PDF格式下載

---