图论及其应用PDF电子书下载

第一章 引论 1

1 Konisberg桥问题(或Euler回路问题) 1

2 路径问题 2

3 应用举例 6

4 Hamilton回路问题 10

5 Ramsey问题 11

习题 12

第三章 基本概念 13

1 图的概念 13

2 同形 14

3 点与边的关联关系 15

4 道路与回路 17

5 Euler回路 17

6 Hamilton道路 19

7 图的矩阵表示法 22

2 例 24

8 道路矩阵 25

9 道路矩阵的Warshall算法 27

10 强连通概念与递归概念 29

习题 31

第三章 树 33

1 树的概念 33

3 基本性质 37

4 基本关联矩阵 40

5 树的数目 41

6 内向树与外向树 46

7 二元树 50

8 Huffman树 52

9 搜索树 55

10 DFS算法 56

11 旅行商问题 59

12 最佳匹配问题 62

习题 65

第四章 最佳路径问题 67

1 最佳路径问题 67

2 求最短路径的Dijkstra算法 68

3 最短树问题 70

4 最短树的Kruskal算法 72

5 求任意两点间的最短距离 73

6 求任意两点距离的Warshall算法 77

7 关键路径法 78

1 平面图 81

2 Euler公式 81

习题 81

第五章 平面图 81

3 极大平面图 82

4 Kuratowski图 83

5 Kuratowski定理 84

6 对偶图 88

7 五色问题 90

8 Minty引理 91

习题 92

第六章 电路网络 93

1 回路矩阵 93

2 回路矩阵的若干性质 95

3 基本关联矩阵Bk与基本回路矩阵C？的关系 97

4 割集矩阵 99

5 克希荷夫定律 103

6 电路问题 104

7 状态变量法理论基础 106

8 状态变量法 107

9 状态变量法举例 114

10 若干特殊性形 127

11 图论在电路中的其它应用 137

习题 144

第七章 图与代数方程组 145

1 矩阵的Cates图 145

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

3 图的运算 147

4 行列式的展开法 151

5 代数方程组的Coates解法 153

6 Mason公式 154

7 Mason公式的证明 158

习题 165

第八章 匹配理论 167

1 基本概念 167

2 关于匹配的基本定理 169

3 Hall定理 170

4 匈牙利算法与例 170

5 Konig定理 172

6 最佳匹配 173

7 最佳匹配的算法与例 177

习题 181

1 网络流问题与最大流 182

第九章 运输网络与开关网络 182

2 割切 183

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

4 标号法 186

5 开关函数 190

6 传输矩阵与连接矩阵 191

7 简单接触网络的实现和算法 192

习题 200

第十章 图的算法 201

1 图的连通性判断 201

2 树的生成 202

3 Minty算法和Mayeda-Seshu算法 207

4 DFS算法的基本思想 212

5 无向图的DFS算法 213

6 有向图的DFS算法 215

7 图的块划分 216

8 强连通块的划分 220

第十一章 色数问题 225

1 问题的提出 225

3 独立集概念及其应用 227

4 求极大独立集的布尔代数算法 229

5 支配集 232

6 色数的一种求法 233

7 色数多项式 235

2 色数及其性质 236

8 应用举例 237

习题 238