《离散数学习题集 图论分册》

第一章 图的基本概念1

1.1 无向图与有向图1

1.2 通路、回路、图的连通性10

1.3 带权图中的路径问题19

1.4 综合题24

第二章 欧拉图与哈密尔顿图28

2.1 欧拉图28

2.2 哈密尔顿图32

2.3 综合题37

第三章 树42

3.1 树与生成树42

3.2 生成树与基本回路系统和基本割集系统47

3.3 根树及其应用50

3.4 综合题54

第四章 平面图58

4.1 平面图的概念、欧拉公式及平面图的判断58

4.2 平面图的对偶图63

4.3 综合题67

第五章 图的可着色性69

5.1 图的可着色性69

第六章 图中顶点集、边集的特殊子集74

6.1 覆盖集、独立集和匹配74

解答与提示81

第一章81

1.181

1.291

1.3108

1.4117

第二章136

2.1136

2.2140

2.3148

第三章162

3.1162

3.2172

3.3175

3.4182

第四章189

4.1189

4.2207

4.3213

第五章218

5.1218

第六章232

6.1232

参考书目247