《图论及其算法》求取 ⇩

第一章 绪论1

1.1 图的图形描述1

1.2 图的拓扑变换3

1.3 图的计算复杂性4

习题与思考题7

第二章 图的基本概念9

2.1 图与子图9

2.2 图的连通性14

2.3 图的矩阵表示19

2.4 图在计算机里的存贮32

2.5 图的遍历34

习题与思考题39

第三章 树与割集44

3.1 无向树44

3.2 生成树46

3.3 有向树52

3.4 有向树的应用55

3.5 树的存贮结构60

3.6 树的遍历64

3.7 图的中心和中位点67

3.8 图的块划分70

3.9 割集82

3.10 基本割集88

习题与思考题92

第四章 平面图97

4.1 可平面图的概念97

4.2 平面图的性质99

4.3 平面图的判别101

4.4 平面性算法106

4.5 图的交叉和厚度112

4.6 对偶图114

习题与思考题120

第五章 偶图与匹配问题124

5.1 偶图的定义及性质124

5.2 匹配的概念126

5.3 偶图的完全匹配128

5.4 偶图的最大权匹配134

5.5 一般图的最大基数匹配142

5.6 一般图的最大权匹配148

习题与思考题155

第六章 图的着色158

6.1 地图的着色158

6.2 五色定理159

6.3 边的着色161

6.4 独立集、支配集、覆盖和团165

6.5 点的着色172

6.6 着色多项式176

习题与思考题179

第七章 路径问题183

7.1 从指定点到其他点的最短路径183

7.2 任意两点间的最短路径186

7.3 最优路径193

7.4 关键路径197

习题与思考题200

第八章 回路问题203

8.1 E图和M图203

8.2 欧拉图的寻迹207

8.3 中国邮路问题211

8.4 有向欧拉图215

8.5 H图221

8.6 有向H图228

8.7 H图的寻迹230

8.8 货郎担问题234

8.9 货郎担问题的近似解法236

8.10 用分枝定界法解货郎担问题241

习题与思考题247

第九章 网络的流251

9.1 流与切割251

9.2 最大流最小切割定理254

9.3 标记法257

9.4 最短路径法260

9.5 最大流最小切割定理的应用推广265

9.6 最小费用流267

9.7 有向图的中国邮路问题273

9.8 无向网络的流275

习题与思考题281

符号表283

参考文献284