《图论》

前言页1

第一章 图与子图1

1.1 图1

1.1.1 图的概念1

1.1.2 集合的积与二元关系3

1.1.3 图的定义5

1.1.4 图的同构6

1.1.5 完全图 二分图 补图8

1.1.6 顶点的度9

1.2 子图11

1.2.1 子图11

1.2.2 图的运算12

1.3 通路和回路14

1.4 图的代数表示20

第二章 E图和H图27

2.1 E图27

2.2 H图34

第三章 通路的集合与最短通路45

3.1 通路的集合45

3.2 最短通路49

3.3 最优化原则59

3.4 中国邮路问题62

第四章 树66

4.1 树66

4.2 生成树71

4.3 基本回路与环路空间73

4.4 最优树79

第五章 割集89

5.1 割集89

5.2 断集空间95

5.3 基本割集102

第六章 图的连通度109

6.1 (点)连通度和边连通度109

6.2 不可分图113

第七章 图在矩阵表示116

7.1 关联矩阵116

7.2 回路矩阵124

7.3 割集矩阵135

7.4 割集矩阵的可实现性141

7.5 图的同调146

第八章 平面图153

8.1 平面图153

8.2 欧拉公式157

8.3 图的可平面性162

8.4 平面性算法172

8.5 对偶图183

8.6 图的厚度190

第九章 有向图196

9.1 有向图196

9.2 有向通路和有向回路198

9.3 有向树和有序树204

第十章 有向图的矩阵表示211

10.1 关联矩阵和回路矩阵211

10.2 割集矩阵219

10.3 回路矩阵和割集矩阵的非零大行列式的值225

10.4 电网络方程229

第十一章 生成树的生成242

11.1 基本树变换242

11.2 生成树的生成246

11.3 生成树的计数257

第十二章 网络的流263

12.1 流263

12.2 割266

12.3 最大流最小割定理269

12.4 标记法272

第十三章 信号流图280

13.1 信号流图280

13.2 Coates流图290