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

第一章　图的基本概念 1

1.1　图 1

1.2　子图 6

1.3　图的运算 13

1.4　图的同构 17

习题 18

第二章　路径、回路和割集 22

2.1　边序列、边列、路径和回路 22

2.2　连通图和非连通图 25

2.3　可分图和不可分图 27

2.4　E图和M图 29

2.5　最小化运算、回路集体和路径集体 35

2.6　中国邮递员问题 37

2.7　H图 40

2.8　旅行推销员问题 47

2.9　用分枝定界法解旅行推销员问题 49

2.10　割集 57

2.11　分离两个指定点的割集 65

习题 70

3.1　树及其性质 79

第三章　树 79

3.2　根树、二元树和生成树 86

3.3　树的编码 91

3.4　生成树的算法 94

3.5　最小生成树的算法 99

3.6　所有生成树的算法 103

3.7　基本回路和基本割集 109

3.8　边连通度和点连通度 112

3.91-同构和2-同构 117

习题 121

4.1　关联矩阵 126

第四章　图的短阵表示 126

4.2　回路矩阵 136

4.3　割集矩阵 144

4.4　邻接矩阵和路径矩阵 153

习题 163

第五章　平面图和对偶图 170

5.1　平面图 170

5.2　欧拉公式 174

5.3　平面性检测 177

5.4　对偶图 181

5.5自对偶图 190

5.6　厚度与交叉 195

习题 199

第六章　着色、匹配和覆盖 205

6.1　色数 205

6.2　独立集、支配集和色划分 207

6.3　计算色数的一种方法 214

6.4　着色多项式 215

6.5　匹配与最大匹配 219

6.6　覆盖 236

6.7　五色问题 240

习题 242

第七章　有向图 245

7.1　有向图的特性和类型 245

7.2　有向子图 246

7.3　有向欧拉图 248

7.4　有向树 251

7.5　有向图的关联矩阵、回路矩阵和割集矩阵 262

7.6　生成树的计数 272

7.7　有向图的邻接矩阵 274

7.8　有向图中的H回路 282

7.9　非循环有向图及最小消环法 289

习题 295

第八章　图论在开关网络中的应用 298

8.1　开关函数 298

8.2　开关网络分析 299

8.3　开关网络综合 303

8.4　割集矩阵的可实现性 310

8.5　SP网络 313

习题 316

9.1　具有独立源的RLC网络分析 319

第九章　图论在电网络分析中的应用 319

9.2　有源网络的拓扑分析 331

习题 341

第十章　图论在运筹学中的应用 345

10.1　最短路径问题 345

10.2　运输网络 361

10.3　最小费用流 371

10.4　工程规划中的任务网络 374

习题 384

参考文献 388