基本信息
作者：王海英 等 著出
版社：北京航空航天大學出版社
ISBN：9787811249408
出版時間：2010-02-01
版次：1
頁數：154裝
幀：平裝開
本：16開
所屬分類：圖書 > 計算機與網際網路 > 輔助設計與工程計算
內容簡介
《圖論算法及其MATLAB實現》系統介紹了圖論重要算法的思想及其MATLAB實現。全書分為相對獨立的9章，每章都是解決一類問題的算法思想及其MATLAB實現，首先介紹有關基礎知識，然後給出相關著名實際問題及解決此問題的算法思想，最後給出MATLAB實現。第1章主要介紹圖論的基礎知識，同時也給出了可達矩陣的計算，以及關聯矩陣和鄰接矩陣的相互轉換等重要算法及其MATLAB實現；第2～8章分別介紹最短路、連通圖、樹、Euler圖和Hamilton圖、匹配、網路中的流、最小費用流等相關問題，而且均給出了有關問題的解決算法及其MATLAB實現；第9章主要介紹染色問題，本章不僅介紹了幾種傳統的染色思想，而且還給出了當今研究領域中非常活躍的非傳統染色思想，並分別給出其MATLAB實現。
圖書目錄
第1章 圖論的基礎知識1
1.1圖論的起源1
1.2著名的圖論學者——歐拉1
1.3圖2
1.4特殊圖類3
1.5有向圖4
1.6圖的矩陣表示5
1.6.1鄰接矩陣5
1.6.2關聯矩陣5
1.7圖論的基本性質和定理6
1.8計算有向圖的可達矩陣的算法及其MATLAB實現6
1.9關聯矩陣和鄰接矩陣的相互轉換算法及其MATLAB實現7
習題一11
第2章 最短路12
2.1路12
2.2最短路問題13
2.3求連通圖最短距離矩陣的算法及其MATLAB實現14
2.4求兩點間最短路的Dijkstra算法及其MATLAB實現15
2.4.1 Dijkstra算法16
2.4.2 Dijkstra算法的MATLAB實現16
2.5求兩點間最短路的改進的Dijkstra算法及其MATLAB實現18
2.5.1 Dijkstra矩陣算法Ⅰ18
2.5.2 Dijkstra矩陣算法Ⅱ18
2.6 求兩點間最短路的WarshallFloyd算法及其MATLAB實現21
2.6.1 Floyd算法的基本思想22
2.6.2 Floyd算法的基本步驟22
2.6.3 WarshallFloyd算法的MATLAB實現22
2.7求任意兩點間最短路的算法及其MATLAB實現25
2.8求從一固定點到其他所有點最短路的算法及其MATLAB實現27
2.9求必須通過指定兩個點的最短路的算法及其MATLAB實現29
2.10求圖的兩頂點間最短路與次短路的算法及其MATLAB實現32
2.11求最大可靠路的算法及其MATLAB實現34
2.12求最大期望容量路的算法及其MATLAB實現36
習題二38
第3章 連通圖40
3.1判斷圖的連通性算法及其MATLAB實現40
3.2連通圖的中心和加權中心的算法及其MATLAB實現42
3.3連通無向圖一般中心的算法及其MATLAB實現44
習題三46
第4章 樹48
4.1樹及其性質48
4.2割點、割邊、割集50
4.3二元樹與Huffman樹51
4.3.1有序二元樹51
4.3.2 Huffman樹51
4.4求Huffman樹及其MATLAB實現52
4.5廣度優先搜尋算法及其MATLAB實現55
4.6深度優先搜尋算法及其MATLAB實現57
4.7求割點算法及其MATLAB實現61
4.8生成樹及其個數65
4.9求無向圖的生成樹算法及其MATLAB實現67
4.10求有向圖的生成樹算法及其MATLAB實現69
4.11求有向連通圖的外向樹與內向樹數目的算法及其MATLAB實現71
4.12最小生成樹問題73
4.13求最小生成樹的kruskal算法及其MATLAB實現74
4.13.1 Kruskal算法的基本思想74
4.13.2 Kruskal算法的MATLAB實現74
4.14求最小生成樹的Prim算法及其MATLAB實現76
4.14.1 Prim算法的基本思想76
4.14.2 Prim算法的MATLAB實現77
習題四79
第5章Euler圖和Hamilton圖81
5.1 Euler圖81
5.2“一筆畫”問題及其理論81
5.3中國郵遞員問題82
5.4 Fleury算法及其MATLAB實現82
5.4.1 Fleury算法的步驟82
5.4.2 Fleury算法的MATLAB實現82
5.5 Hamilton圖87
5.6旅行售貨員問題88
5.7改良圈算法及其MATLAB實現89
習題五92
第6章 匹配問題及其算法93
6.1問題起源——婚配問題93
6.2二分圖的有關知識93
6.3匹配、完美匹配、最大匹配93
6.4匹配的基本定理94
6.5套用案例——BernolliEuler錯放信箋問題95
6.6尋求圖的一個較大基數匹配算法及其MATLAB實現95
6.7人員分配問題97
6.8匈牙利算法及其MATLAB實現97
6.8.1匈牙利算法基本步驟97
6.8.2匈牙利算法的MATLAB實現98
6.8.3案例及其MATLAB實現100
6.9最優分配問題101
6.10 KuhnMunkres算法及其MATLAB實現101
6.10.1 KuhnMunkres算法的基本思想101
6.10.2利用可行頂點標記求最佳匹配的KuhnMunkras算法步驟102
6.10.3 KuhnMunkres算法的MATLAB實現102
6.10.4簡單實驗105
習題六107
第7章 網路流的算法108
7.1網路、流和割108
7.1.1網路和流108
7.1.2割109
7.2網路的最大流問題110
7.3最大流最小割定理110
7.4 FordFulkerson標號算法及其MATLAB實現111
7.4.1 FordFulkerson標號算法的基本步驟111
7.4.2 FordFulkerson 標號算法的MATLAB實現112
7.4.3案例及其MATLAB實現113
7.5 Dinic算法及其MATLAB實現114
7.5.1 Dinic算法的基本思想114
7.5.2 Dinic算法的MATLAB實現115
7.5.3案例
圖書前言
圖論算法廣泛套用於物理、化學、運籌學、計算機科學、電子學、資訊理論、控制論、網路理論、管理科學、社會科學等眾多學科領域。隨著這些學科的發展，特別是計算機科學的快速發展，又大大促進了圖論和其他學科的發展。
圖論算法是計算機科學的核心。近幾年，隨著強有力的MATLAB等數學軟體的迅速發展，圖論算法在數學和計算機等各學科方面的套用越來越廣泛，從而使各學科的研究者越來越多地重視圖論算法及其MATLAB實現和典型案例，而市場上又缺少這方面的指導性書籍。
本書將圖論的基礎知識、圖論的著名問題以及相應的MATLAB程式代碼和簡單實例完美地結合在一起，力求語言簡潔易懂，問題廣泛有趣，算法科學，實例淺顯，增強MATLAB實現的技巧性和操作性。讀者可以通過簡單案例，把圖論的重要算法與MATLAB編程完美結合。
本書力求內容豐富，各章節相互聯繫，具備指導性書籍的系統性、科學性、實用性和引導性；同時，各章又相對獨立，自成體系，為讀者提供極大方便。
本書的創新之處在於，每一章均以著名實際問題為引入點，以圖論算法為指導線，運用簡單案例達到與MATLAB實現的完美結合，真正讓各層次的讀者學會運用圖論理論解決實際問題，從而培養讀者的圖論思維，使讀者驚嘆圖論方法的美妙與魅力。最後還為讀者提供了當今圖論標號方面等未解決的問題。
本書將在每一章節中給出著名圖論的算法步驟及其一般MATLAB程式；同時，緊隨每個案例分析，均給出解決問題的MATLAB源程式，這樣對於初學者來說，具有很強的編程操作性。
本書是在中國地質大學（北京）王海英多年專業講義的基礎上重新修訂編寫而成，其中，山東體育學院體育運動學校的李傳濤完成了本書程式的編寫工作；中國科學院數學與系統科學院的黃強完成了本書全部程式的調試、修改和圖形繪製等工作，
