《图、网络与算法》求取 ⇩

第一篇 图论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端口电阻网络的实现-I249

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

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

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