《图论及其应用习题解答》

第一章 图与子图1

1.1 图与单图1

1.2 图的同构4

1.3 邻接矩阵和关联矩阵13

1.4 子图16

1.5 顶点的度21

1.6 路和连通性28

1.7 圈34

1.8 最短路问题38

1.9 Sperner引理44

第二章 树49

2.1 树49

2.2 割边和键54

2.3 割点63

2.4 Cayley公式65

2.5 连接问题71

第三章 连通性76

3.1 连通性76

3.3 可靠通讯网络的构造80

3.2 块80

第四章 Euler游历和Hamilton圈93

4.1 Euler游历93

4.2 Hamilton圈96

4.3 中国邮递员员问题113

4.4 旅行售货员问题116

第五章 匹配118

5.1 匹配118

5.2 2-部图的匹配和覆盖123

5.3 完美匹配129

5.4 人员工作分配问题138

5.5 最优分配问题139

第六章 边着色144

6.1 边色数144

6.2 Vizing定理149

6.3 时间表问题159

第七章 独立集和团161

7.1 独立集161

7.2 Ramsey定理165

7.3 Turán定理174

7.4 Schur定理179

7.5 一个几何问题182

第八章 顶点差色185

8.1 色数185

8.2 Bro′oks定理193

8.3 Haj′os猜测195

8.4 色多项式198

8.5 围长和色数205

8.6 存储问题207

第九章 平面图209

9.1 平面图和可平面图209

9.2 对偶图212

9.3 Euler公式219

9.4 桥223

9.5 Kuratowski定理226

9.6 5-色定理和4-色猜测228

9.7 非Hamilton可平面图236

9.8 平面性算法241

10.1 有向图243

第十章 有向图243

10.2 有向路249

10.3 有向圈254

10.4 工作排序问题259

10.5 高效率计算机磁鼓的设计261

10.6 单向道路系统的构造262

10.7 比赛参加者的名次评定264

11.1 流268

第十一章 网络268

11.2 截272

11.3 最大流最小截定理274

11.4 Menger定理284

11.5 可行流288

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

12.1 环流和势差296

12.2 生成树的数目300

12.3 完美正方形305