《图论及其应用 第2版》

第一部分 基础理论篇3

第一章 图的基本概念3

1 引论3

2 图的概念14

3 道路与回路17

4 图的矩阵表示法23

5 中国邮路问题26

6 平面图29

7 Petri网33

第二章 树41

1 树的概念41

2 基本性质45

3 关联矩阵与基本关联矩阵46

4 回路矩阵与基本回路矩阵48

5 关联矩阵与回路矩阵的关系51

6 割集矩阵与基本割集矩阵53

7 树的数目56

8 内向树与外向树61

9 二元树64

10 Huffman树66

11 搜索树69

12 流动商人问题与分支定界法70

13 最佳匹配问题77

第三章 图的算法81

1 最佳路径问题及其算法81

2 最短树问题及其算法85

3 任意两点间最短距离及其算法90

4 图的连通性判断94

5 树的生成95

6 DFS算法102

7 图的块划分109

8 强连通块的划分112

2 电路问题119

1 克希荷夫定律119

第四章 电路网络问题119

第二部分 应用篇119

3 状态变量法理论基础121

4 状态变量法122

5 状态变量法举例128

6 若干特殊情形140

第五章 信号流图问题150

1 矩阵与Coates流图150

2 代数方程组与Mason信号流图151

3 信号流图的运算152

4 行列式的展开法158

5 代数方程组的Coates图解法160

6 Mason公式162

7 Mason公式的证明166

第六章 网络流图问题174

1 网络流图问题与最大流174

2 割切175

3 Ford-Fulkerson最大流最小割切定理176

4 标号法178

5 Edmcnds-Karp修正算法.Dinic算法及其它181

6 开关网络简介185

第七章 匹配理论、色数问题及其它189

1 最大匹配189

2 Hall定理191

3 匈牙利算法及例192

4 最佳匹配194

5 最佳匹配的算法及例198

6 色数问题202

7 独立集概念及其应用206

8 支配集210

9 色数的一种求法211

10 色多项式213

11 色数问题应用举例214

12 PERT图法216

13 强连通化问题219