圖論及其套用(東南大學出版社出版的圖書)

《圖論及其套用》是2015年東南大學出版社出版的圖書，圖書作者是卜月華、王維凡、呂新忠。

基本介紹

• 書名：圖論及其套用
• 作者：卜月華、王維凡、呂新忠
• ISBN：9787564156749
• 定價：35
• 出版社：東南大學出版社
• 出版時間：2015年5月

內容簡介

圖論是組合數學的一個重要分支，與其他的數學分支，如群論、矩陣論、機率論、拓撲學、數值分析等有著密切的聯繫。凡有二元關係的系統，套用圖論均可建立一種合適的數學模型，因而圖論在許多學科領域，如計算機科學、通訊科學、運籌學、電網路分析、化學、物理、管理以及社會科學等領域具有重要地位和廣泛套用。此外，圖論的理論與方法也是數學競賽、數學建模等的理論基礎和工具。因此在本書的大部分章節中介紹了一些套用實例，特別在第9章收集了若干圖論在數學建模中的套用案例，讀者可以從中掌握利用圖論解決實際問題的基本方法和技巧。目前，圖論已成為計算機科學、運籌學、組合最佳化、機電等學科的基本課程之一，國內外許多高校不僅對數學系的本科學生開設了圖論課程，也面向其他專業學生開設了圖論選修課程。

目錄

1圖的基本概念1

1.1圖論發展史1

1.2圖的定義2

1.3頂點的度5

1.4子圖與圖的運算9

1.5一些特殊的圖11

1.6圖的矩陣表示15

1.7有向圖21

1.8Brouwer不動點定理24

習題126

2圖的連通性29

2.1路和圈29

2.2連通圖35

2.3連通度39

2.4可靠通訊網路的構造45

2.5最短路問題47

2.6單行道路系統的構造57

習題258

3樹61

3.1樹的基本性質61

3.2生成樹68

3.3最優生成樹73

3.4樹形圖76

習題386

4Euler環遊和Hamilton圈89

4.1Euler環遊89

4.2中國郵路問題95

4.3Hamilton圖99

4.4旅行售貨員問題108

習題4112

5圖的對集和獨立集116

5.1對集116

5.2二分圖的對集122

5.3二分圖最大對集算法128

5.4最優分派問題129

5.5獨立集和覆蓋132

5.6Ramsey數137

習題5144

6平面圖147

6.1平面圖及平面嵌入147

6.2平面圖性質149

6.3幾類特殊的平面圖158

6.4圖的曲面嵌入161

習題6164

7圖的染色166

7.1頂點染色167

7.2邊染色173

7.3列表染色181

7.4全染色186

7.5染色方法189

7.5.1權轉移方法189

7.5.2機率方法192

7.5.3代數方法193

習題7195

8網路流197

8.1基本概念和基本定理197

8.2最大流問題的算法201

8.3最小費用流問題205

8.4最小費用流的算法208

8.4.1原始算法208

8.4.2對偶算法209

8.5計畫評審方法和關鍵路線法211

8.5.1PERT網路圖的一些基本概念212

8.5.2建立PERT網路圖的準則和注意事項213

8.5.3 PERT網路圖的合併與簡化214

8.5.4PERT網路圖的計算215

習題8219

9圖論在數學建模中的套用220

9.1模型1：婚配問題220

9.1.1問題分析220

9.1.2模型建立220

9.1.3模型的求解221

9.2模型2:鎖具裝箱問題222

9.2.1分析與建模222

9.2.2模型的求解222

9.3模型3：最優截斷切割問題223

9.4模型4：賽程安排227

9.4.1問題分析227

9.4.2圖論模型的建立228

9.4.3完美賽程的編制方法230

9.4.4其他問題233

9.5模型5：桌球比賽隊員出場順序安排233

9.5.1實力強弱的理解233

9.5.2模型的建立與求解234

9.6模型6：災情巡視路線236

9.6.1問題假設237

9.6.2模型的建立與求解237

習題9241

參考文獻244