《图论基础》求取 ⇩

第一章图和子图1

1.1 基本概念1

1.2 子图及其运算7

1.3 通路和回路10

1.4 最短通路问题13

1.5 子图集合的代数结构17

1.6 关联矩阵与邻接矩阵20

1.7 服务点设置问题23

习题28

第二章树34

2.1 定义和例子34

2.2 树的基本特征37

2.3 生成树40

2.4 连接问题44

习题49

第三章连通性53

3.1 (点)连通度和边连通度53

3.2 块57

3.3 Menger 定理61

3.4 极小 k—连通图63

习题65

第四章边无关集和点独立集67

4.1 边无关集(匹配)67

4.2 二分图的边无关集70

4.3 独立集和覆盖72

4.4 Ramsey 数77

习题84

5.1 七桥问题与 Euler 图88

第五章E 图和 H 图88

5.2 Hamilton 图91

5.3 中国邮递员问题100

5.4 旅行售货员问题103

习题106

第六章图的染色110

6.1 边染色110

6.2 点染色116

6.3 色多项式122

习题127

第七章平面图129

7.1 平面图和可平面图129

7.2 Euler 公式132

7.3 Kuratowski 定理137

7.4 四色问题与五色定理141

习题144

第八章有向图146

8.1 有向图的概念146

8.2 单向通路148

8.3 单向回路152

8.4 有向树与有序树156

习题162

第九章网络最大流165

9.1 网络的流与割165

9.2 最大流最小割定理170

9.3 标记法173

习题177

[附录] 数学竞赛中的图论问题180

参考书目201