图、网络与算法PDF电子书下载

第一篇 图论 1

第一章 基本概念 1

1.1 基本定义 1

1.2 子图和补图 3

1.3 通道、轨迹、路径和回路 5

1.4 图的连通性和片 7

1.5 图的运算 8

1.6 特殊图 11

1.7 割点和可分图 13

1.8 同构和2-同构 14

1.9 进一步阅读 17

1.10 习题 17

1.11 参考文献 19

第二章 树、割集和回路 20

2.1 树、生成树和补生成树 20

2.2 K-树、K-生成树和林 25

2.3 秩和零度 27

2.4 基本回路 27

2.5 割集 28

2.6 切割 29

2.7 基本割集 31

2.8 生成树、回路和割集 32

2.9 进一步阅读 34

2.10 习题 34

2.11 参考文献 36

第三章 欧拉图和哈密顿图 37

3.1 欧拉图 38

3.2 哈密顿图 42

3.4 习题 46

3.2 进一步阅读 46

3.5 参考文献 47

第四章 图和矢量空间 49

4.1 群和域 49

4.2 矢量空间 51

4.3 图的矢量空间 54

4.4 回路和割集子空间的维数 58

4.5 回路和割集子空间的关系 60

4.6 回路和割集子空间的正交性 61

4.8 习题 63

4.7 进一步阅读 63

4.9 参考文献 64

第五章 有向图 65

5.1 基本定义和概念 65

5.2 图和关系 69

5.3 有向树或单向树 70

5.4 有向欧拉图 73

5.5 有向生成树和有向欧拉轨迹 75

5.6 有向哈密顿图 77

5.7 无圈有向图 79

5.8 比赛图 80

5.9 进一上阅读 81

5.10 习题 81

5.11 参考文献 82

第六章 图的矩阵 84

6.1 关联矩阵 84

6.2 切割矩阵 86

6.3 回路矩阵 89

6.4 正交关系 91

6.5 切割、关联和回路矩阵的子矩阵 92

6.6 单位模矩阵 96

6.7 生成树的数目 98

6.8 生成2-树的数目 101

6.9 有向图中有向生成树的数目 103

6.10 邻接矩阵 106

6.11 考茨(Coates)图和梅森(Mason)图 109

6.12 进一上阅读 116

6.13 习题 116

6.14 参考文献 118

7.1 平面图 120

第七章 平面性和对偶性 120

7.2 欧拉公式 122

7.3 Kuratowski定理和平面性的另一些特征 124

7.4 对偶图 126

7.5 平面性和对偶性 129

7.6 进一步阅读 131

7.7 习题 131

7.8 参考文献 132

第八章 连通度和匹配 134

8.1 连通度或顶点连通度 134

8.2 边连通度 138

8.3 规定度的图 139

8.4 Menger定理 142

8.5 匹配 144

8.6 二分图中的匹配 145

8.7 一般图中的匹配 150

8.8 进一步阅读 155

8.9 习题 155

8.10 参考文献 157

第九章 覆盖和着色 159

9.1 独立集和顶点覆盖 159

9.2 边覆盖 164

9.3 边着色和色指数 165

9.4 顶点着色和色数 169

9.5 色多顶式 171

9.6 四色问题 173

9.7 进一步阅读 174

9.8 习题 175

9.9 参考文献 176

第十章 拟阵 179

10.1 基本定义 179

10.2 基本性质 181

10.3 等价公理系统 184

10.4 拟阵的对偶性和拟图 186

10.5 约束、收缩和拟阵的子式 191

10.6 拟阵的可表达性 193

10.7 二元拟阵 194

10.8 可定向拟阵 197

10.9 拟阵和Greedy算法 199

10.10 进一步阅读 201

10.11 习题 202

10.12 参考文献 204

第二篇 电网络理论 207

第十一章 图和网络 207

11.1 回路和割集变换 208

11.2 回路和割集系统方程组 211

11.3 混合-变量法 216

11.4 图的主划分 218

11.5 状态方程 223

11.6 电阻网络的无增益特性 228

11.7 进一步阅读 229

11.8 习题 229

11.9 参考文献 231

12.1 引言 234

第十二章 N端口电阻网络 234

12.2 秩为n的n端口电阻网络的Y矩阵 240

12.3 (n+1)节点n端口电阻网络的实现-I 249

12.4 割集和回路矩阵的实现 254

12.5 (n+1)节点n端口电阻网络的实现-II 263

12.6 进一步阅读 268

12.7 习题 268

12.8 参考文献 270

13.1 无互感RLC网络的拓扑公式 273

第十三章 网络函数和网络灵敏度 273

13.2 一般线性网络的拓扑公式 278

13.3 伴随网络和网络灵敏度的计算 284

13.4 进一步阅读 290

13.5 习题 291

13.6 参考文献 291

第三篇 算法图论 293

第十四章 算法分析 293

14.1 传递闭包 294

14.2 传递定向 299

14.3 深度优先搜索 308

14.4 2-连通性与强连通性 313

14.5 程序图的简化 319

14.6 程序图的控主 325

14.7 进一步阅读 332

14.8 习题 333

14.9 参考文献 334

第十五章 算法优化 338

15.1 最短路径 338

15.2 最小加权路径长度树 344

15.3 最优二元搜索树 351

15.4 图的最大匹配 355

15.5 二分图中的最大匹配 363

15.6 完美匹配、最优分配和时间表的安排 369

15.7 运输网络中的流 375

15.8 最优分支 388

15.9 进一步阅读 392

15.10 习题 393

15.11 参考文献 394

名词索引 401