程序員的數學4：圖論入門

宫崎修一（作者）

1998年毕业于日本九州大学研究生院系统信息学研究科，获工学博士学位。现任日本京都大学学术信息媒体中心副教授，主要研究算法和计算复杂性理论。著作有《我的第一本算法书》（合著）。

卢晓南（译者）

本科就读于西安交通大学少年班、数学系。名古屋大学博士（信息科学）。现于山梨大学计算机系任助理教授。主要研究方向包括组合数学（离散数学）及其在信息科学、计算机科学、统计学中的应用。译著有《程序员的数学3：线性代数》。

第 1章 圖的基礎知識 1

1.1 什麽是圖 1

1.2 圖的表示法 6

1.3 其他圖論術語 9

1.4 幾類特殊的圖 17

1.5 圖的度序列 26

章末習題 31

 

第 2章 最小生成樹 33

2.1 什麽是最小生成樹 33

2.2 克魯斯卡爾算法 35

2.3 普里姆算法 39

2.4 最小斯坦納樹問題 41

章末習題 43

 

第3章 最短路徑問題 45

3.1 什麽是最短路徑問題 45

3.2 迪傑斯特拉算法 46

章末習題 52

 

第4章 歐拉迴路與哈密頓圈 53

4.1 定義 53

4.2 歐拉迴路 56

4.3 哈密頓圈 59

章末習題 63

 

第5章 圖著色 65

5.1 頂點著色 65

5.2 邊著色 79

章末習題 84

 

第6章最大流問題 85

6.1 什麽是最大流問題 85

6.2 福特- 富爾克森算法 89

6.3 最大流最小割定理 96

章末習題 99

 

第7章 匹配問題 101

7.1 什麽是匹配 101

7.2 二部圖中的匹配 104

7.3 匈牙利算法 108

7.4 用求解最大流問題的算法求解匹配問題 115

章末習題 118

 

第8章 章末習題解答 119

 

索引 131