《图论及其应用》求取 ⇩

第一章图和子图1

1.1 图和简单图1

1.2 图的同构4

1.3 关联矩阵和邻接矩阵7

1.4 子图8

1.5 顶点的度11

1.6 路和连通12

1.7 圈15

应用17

1.8 最短路问题17

1.9 Sperner 引理23

第二章树27

2.1 树27

2.2 割边和键29

2.3 割点33

2.4 Cayley 公式34

应用38

2.5 连线问题38

第三章连通度45

3.1 连通度45

3.2 块47

3.3 可靠通讯网络的构造51

应用51

第四章Euler 环游和 Hamilton 圈55

4.1 Euler 环游55

4.2 Hamilton 圈57

应用66

4.3 中国邮递员问题66

4.4 旅行售货员问题69

第五章对集74

5.1 对集74

5.2 偶图的对集和覆盖76

5.3 完美对集80

5.4 人员分派问题85

应用85

5.5 最优分派问题91

第六章边着色97

6.1 边色数97

6.2 Vizing 定理100

应用103

6.3 排课表问题103

第七章独立集和团108

7.1 独立集108

7.2 Ramsey 定理110

7.3 Turan 定理117

7.4 Schur 定理120

应用120

7.5 一个几何问题121

第八章顶点着色126

8.1 色数126

8.2 Brooks 定理131

8.3 Hajós 猜想132

8.4 色多项式134

8.5 围长和色数139

应用141

8.6 贮藏问题141

9.1 平图和平面图145

第九章平面图145

9.2 对偶图149

9.3 Euler 公式153

9.4 桥156

9.5 Kuratowski 定理161

9.6 五色定理和四色猜想166

9.7 非 Hamilton 平面图171

应用173

9.8 平面性算法173

第十章有向图181

10.1 有向图181

10.2 有向路184

10.3 有向圈187

应用191

10.4 工件排序问题191

10.5 高效率计算机鼓轮的设计192

10.6 单行道路系统的构造195

10.7 竞赛参加者名次的排列197

第十一章网络203

11.1 流203

11.2 割206

11.3 最大流最小割定理209

应用216

11.4 Menger 定理216

11.5 可行流219

第十二章圈空间和键空间226

12.1 环流和势差226

12.2 生成树的数目232

应用234

12.3 完美正方形234

附录Ⅰ 带星号习题的提示241

附录Ⅱ 四个图及其特性表248

附录Ⅲ 一些有趣的图250

附录Ⅳ 尚未解决的问题262

附录Ⅴ 进一步阅读的建议271

符号汇编274

译名对照表276