《图论导引》

前言1

第一章基本概念3

1 图3

2 有向图与无向图4

3 图的顶与边(弧)5

4 1—图5

5 平面图与非平面图6

6 顶点次数7

7 部分图与子图8

8 图的矩阵表示9

9 链与圈，路与回路11

10 图的同构13

习题14

1 树19

第二章树与树形图19

2 跨顶树21

3 树形图24

4 联接图上的最短路28

习题36

第三章？和？维数40

1 尤拉圈40

2 环和44

3 余圈45

4 向量空间49

5 圈维数50

6 圈的矩阵表示53

7 数树58

习题68

2 平面图的面72

1 测地变换72

第四章平面图72

3 尤拉公式74

4 对偶图78

5 库拉图斯基定理80

6 库拉图斯基定理充分性的证明82

习题86

第五章两分图(偶图)89

1 基本概念与基本定理89

2 两分图的矩阵表示92

3 两分图的并列集99

习题101

第六章网络上的流103

1 网络103

2 流量的调整106

3 极大流量——极小截量定理109

4 极大流量——极小截量定理的简单应用113

5 供求定理116

6 对称的供求定理119

7 环流问题124

8 环流与势差130

习题136

第七章网络流理论在图论上的应用(具已知半次的图的存在性)143

1 蒙格尔定理143

2 具已知半次的 p——图的存在性146

3 具已知半次的对称 p——图的存在性151

4 具已知半次的无环 p——图的存在性154

5 具已知半次的竞赛图的存在性160

习题163

1 断集、断量与断量的基本性质167

第八章图的联接性167

2 集块173

3 蒙格尔定理在图的联接性上的应用176

4 断量与边数181

5 极小2——联图的结构185

6 3——联图的结构193

习题200

第九章尤拉圈与哈密尔顿图203

1 尤拉圈203

2 哈密尔顿问题204

3 图成 H——型的充分条件206

4 图成 H——型的必要条件217

5 有向图的哈密尔顿回路223

6 哈密尔顿链与哈密尔顿路231

7 竞赛图上 H——路的求法237

习题244

第十章并列集(对集)248

1 极大并列集248

2 极小覆盖253

3 两分图上的极大并列集255

4 两分图上顶点的配对257

5 最优安排问题262

6 完美并列集266

习题276

第十一章稳固集(独立集)280

1 稳固集与径集280

2 极大稳固集281

3 涂兰定理及其有关问题288

习题295

1 着色指数298

第十二章图的着色298

(一)边的着色298

2 图的分类313

3 边临界图318

(二)点的着色319

1 图的色数319

2 临界图327

3 着色多项式333

4 平面图的可——5着色337

习题339

第十三章拉姆绥定理与拉姆绥数344

1 拉姆绥定理344

2 拉姆绥定理的应用349

3 拉姆绥定理在图论上的应用352

4 N(3，3，3，…，3；2)?的确定359

习题362

第十四章超图364

1 基本概念364

2 超图的链和圈367

3 超图的代表图371

4 超图的并列集375

5 超图的径集376

6 超图的着色385

7 超图的集团390

8 平衡超图393

习题405

参考书目408

名词索引408