《图论》

第一章图1

1 基本概念1

2 度11

3 n 部图18

4 图的自同构群26

第二章图的矩阵表示32

1 邻接矩阵32

2 特征多项式与谱38

3 关联矩阵和线邻接矩阵47

4 图的重构54

1 树61

第三章树和有关结构61

2 圈空间和余圈空间71

3 线性网络分析81

4 有向树86

第四章通道91

1 最短道路问题91

2 欧拉迹96

3 哈密顿圈105

第五章连通性116

1 连通度116

2 h-连通性126

3 最大流定理131

4 求最大流的算法140

5 局部连通性144

6 有向图的连通性150

第六章独立集和覆盖157

1 匹配157

2 双图中的匹配168

3 独立点集173

4 覆盖180

5 拉姆齐(Ramsey)数185

第七章可平面性191

1 图的曲面嵌入191

2 欧拉公式198

3 可平面性的特征209

4 平面嵌入的实现217

第八章图的着色222

1 色数222

2 线色数231

3 平面图的着色241

4 色多项式247

第九章超图和拟阵259

1 超图的基本概念259

2 超图的着色271

3 拟阵的基本概念277

参考文献286

名词索引288

记号索引293