欧拉图与相关专题PDF电子书下载

第 一卷 3

第1章 引言 3

第2章 欧拉图理论的三个支柱 6

第3章 基本概念和预备知识 14

3.1混合图与它们的基本要素 14

3.2图与混合有向图的子图 19

3.3导出子图 22

3.4路径、迹、路、圈、树；连通度 25

3.5相容性，Kv的循环序和对应的欧拉迹 40

3.6匹配、1-因子、2-因子、1-因子分解、2-因子分解、二部图 42

3.7图的曲面嵌入、同构 47

3.8平面图的着色 54

3.9哈密顿圈 57

3.10关联矩阵和邻接矩阵、流和张力 61

3.11算法及其复杂性 63

3.12注记 65

第4章 特征定理和推论 66

4.1图 66

4.2有向图 71

4.3混合图 73

4.4习题 78

第5章 再论欧拉迹及其推广展望 80

5.1迹分解，路、圈分解 80

5.2奇偶性结果 81

5.3双迹 82

5.4交叉边界：图的分拆 83

5.5习题 84

第6章 欧拉迹的各种类型 85

6.1回避特定转移的欧拉迹 85

6.1.1有向图中P（D）相容欧拉迹 89

6.1.2双欧拉有向图中的反欧拉迹和图的双欧拉定向 95

6.1.3有向图中的Do-偏好欧拉迹 100

6.2两两相容欧拉迹 106

6.2.1有向图中的两两相容欧拉迹 124

6.3平面欧拉图中的A-迹 130

6.3.1平面欧拉图中的A-迹和平面3-正则图中的哈密顿圈之间的对偶性 160

6.3.2欧拉图中的A-迹和哈密顿圈 182

6.3.3如何找出A-迹：一些复杂性讨论和算法的建议 190

6.3.4关于非交叉欧拉迹和A-迹的注记以及另一问题 198

6.4习题 199

第7章 欧拉迹的变换 202

7.1图中任意欧拉迹的变换 203

7.2特殊的欧拉迹的变换 207

7.2.1特殊类型的欧拉迹和K1-变换的应用 218

7.3有向图中的欧拉迹的变换 233

7.4最终注解及一些未解决的问题 237

7.5习题 239

参考文献 240

第 二卷 253

第8章 各种类型的闭覆盖途径 253

8.1双迹 253

8.2图中的值-真途径和整流 262

8.3中国邮递员问题 313

8.3.1关于图上的中国邮递员问题 314

8.3.2有向邮递员问题 337

8.3.3混合邮递员问题 345

8.3.4带风向的邮递员问题和最后注记 353

8.4习题 358

第9章 欧拉迹及其数目 360

9.1有向图和（混合）图的奇偶性的结果 360

9.1.1矩阵代数的一个应用 402

9.2计数初涉 412

9.2.1矩阵树定理 412

9.2.2有向图和图的欧拉迹计数 416

9.2.3关于欧拉定向的数目 425

9.2.4拜斯特定理的应用和推广 431

9.2.5其他说明 436

9.3习题 438

第10章 欧拉迹和圈分解的算法及迷宫搜索算法 440

10.1欧拉迹的算法 440

10.2圈分解算法 449

10.3迷宫 451

10.4习题 461

参考文献 463

对第一卷的更正和补录 481

人名译名表 483