《图与网络流理论》求取 ⇩

第一章图的基本概念1

1.1 图与子图1

1.2 链、圈和连通分图4

1.3 图的运算5

1.4 一些特殊图类8

1.5 反圈11

习题12

2.1 树的基本性质15

第二章树15

2.2 图的支撑树19

2.3 树的基本变换24

2.4 最小支撑树26

2.5 Cayley 定理29

习题33

第三章图的连通性35

3.1 连通度35

3.2 截点、截边和块41

3.3 Menger 型定理44

3.4 极小 k 点连通图48

3.5 最短链问题56

习题58

第四章无关集与覆盖集60

4.1 边无关集60

4.2 二部图的最大边无关集算法及 K?nig 定理61

4.3 一般图的最大边无关集算法66

4.4 完美边无关集73

4.5 点无关集和边覆盖集77

4.6 Ramsey 数85

习题89

第五章Euler 问题和 Hamilton 问题92

5.1 Euler 问题92

5.2 中国邮递员问题94

5.3 Hamilton 问题96

习题110

第六章平面图114

6.1 图的可平面性114

6.2 Euler 公式119

6.3 Kuratowski 定理120

习题124

第七章染色126

7.1 边染色126

7.2 点染色132

7.3 平面图的染色137

7.4 色多项式139

7.5 完美图144

习题152

8.1 有向图155

第八章有向图155

8.2 树形图162

8.3 有向图中的路和回路169

习题179

第九章网络最大流问题182

9.1 基本概念和基本定理182

9.2 最大流算法186

9.3 相容性定理193

9.4 循环流198

9.5 流量矩阵202

习题205

第十章最小费用流问题207

10.1 基本定理207

10.2 最小费用最大流212

10.3 最小费用循环流217

习题221

第十一章覆盖与装填223

11.1 链覆盖集223

11.2 路覆盖集229

11.3 树的装填问题232

11.4 有向图中的最大最小定理236

习题247

第十二章图的空间与矩阵249

12.1 图的向量空间249

12.2 图的矩阵252

12.3 有向图的矩阵256

12.4 矩阵-树定理258

习题261

参考文献262