《图论 第2版》

第一章图1

1.1 图的概念1

1.2 子图12

1.3 顶点的度15

1.4 道路与连通性16

1.5 图的运算20

习题一23

第二章树26

2.1 树的特性26

2.2 割边与割点29

2.3 生成树33

习题二35

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

3.1 环路38

3.2 欧拉图41

3.3 哈密顿图42

习题三51

第四章割集53

4.1 割集与断集53

4.2 关联集59

习题四65

5.1 图的向量空间66

第五章圈空间与割集空间66

5.2 圈空间70

5.3 割集空间75

习题五80

第六章图的矩阵表示83

6.1 关联矩阵83

6.2 圈矩阵90

6.3 割集矩阵96

6.4 矩阵间的关系98

6.5 图的邻接矩阵105

6.6 割集矩阵的可实现性113

习题六117

第七章连通性121

7.1 连通度和边连通度121

7.2 2-连通图126

习题七129

第八章匹配130

8.1 最大匹配130

8.2 二部图的匹配与覆盖133

8.3 完美匹配138

8.4 二部图完美匹配的算法142

习题八146

第九章色数148

9.1 独立集148

9.2 顶点着色149

9.3 边着色154

9.4 色多项式155

习题九159

第十章平面图160

10.1 平面图的概念160

10.2 欧拉公式167

10.3 库拉图斯基定理171

10.4 平面性算法182

10.5 对偶图195

10.6 五色定理197

习题十200

11.1 道路的集合202

第十一章最短通路与最小树202

11.2 最短道路206

11.3 最优化原则219

11.4 中国邮路问题222

11.5 最小树224

11.6 最小树算法226

习题十一235

第十二章有向图238

12.1 有向图238

12.2 有向道路和有向圈240

12.3 有向树和有序树246

13.1 关联矩阵255

第十三章有向图的矩阵表示255

13.2 圈矩阵259

13.3 割集矩阵266

第十四章运输网络275

14.1 网络的流275

14.2 割279

14.3 最大流最小割定理282

14.4 标记法285

习题十四292

附录A流图和信号流图294

A.1 流图294

A.2 信号流图300

A.3 流图公式309

附录B开关网络317

B.1 道路集合(续)317

B.2 开关网络分析322

B.3 开关网络综合329

附录C电网络341

C.1 引言341

C.2 节点变换346

C.3 网孔变换353

C.4 守纳矩阵行列式358

习题解答365