《图论》求取 ⇩

第一章 图1

1.1 图的概念1

1.1.1 引例1

1.1.2 集合的积与二元关系4

1.1.3 图的定义5

1.2 完全图 二分图 补图7

1.3 顶点的度9

1.4 图的同构10

1.5 子图13

1.6 图的运算15

1.7 道路和回路17

1.8 图的向量空间23

第二章 E图和H图32

2.1 E图32

2.2 H图40

第三章 道路集合与最短道路52

3.1 道路集合52

3.2 最短道路56

3.3 最优化原则71

3.4 中国邮路问题75

第四章 树79

4.1 树的特性79

4.2 生成树84

4.3 基本回路与环路空间86

4.4 最优树93

5.1 割集104

第五章 割集104

5.2 关联集109

5.3 基本割集与断集空间117

第六章 图的矩阵表示125

6.1 关联矩阵125

6.2 回路矩阵133

6.3 割集矩阵141

6.4 矩阵间的关系144

6.5 图的邻接矩阵152

7.1 (点)连通度和边连通度166

第七章 图的连通度166

7.2 不可分图171

第八章 平面图176

8.2 平面图的概念176

8.2 欧拉公式182

8.3 图的可平面性188

8.4 平面性算法199

8.5 对偶图213

8.6 五色定理216

第九章 匹配222

9.1 最大匹配222

9.2 二分图的匹配和覆盖224

9.3 完美匹配229

第十章 色数240

10.1 顶点着色240

10.2 色多项式245

第十一章 有向图249

11.1 有向图249

11.2 有向道路和有向回路251

11.3 有向树257

第十二章 有向图的矩阵表示268

12.1 关联矩阵268

12.2 回路矩阵273

12.3 割集矩阵281

第十三章 网络的流291

13.1 流291

13.2 割295

13.3 最大流最小割定理297

13.4 标记法300

第十四章 信号流图311

14.1 信号流图311

14.2 Coates流图322

第十五章 生成树的生成336

15.1 基本树变换336

15.2 生成树的生成340

习题解答356

参考资料394

名词索引395