图论导引PDF电子书下载

前言 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