图的可嵌入性理论

出版时间：2010-3  出版社：科学出版社  作者：刘彦佩  页数：379  
Tag标签：无  

前言

图的可嵌入性的概念导源于平面性。关于后者，至少组合学工作者深知，它是图论中重要的研究课题之一。早在20世纪30年代初，首先是波兰的数学家K. Kuratowski，其后不久，还有美国的数学家H.Whitney和S.MacLane都作过精湛的研究，他们在这方面都创立了各自的理论。时至今日，仍不减其生命力。这些均已被世人所承认。然而，本书则打算提供另一种看来在文献中还是新鲜的理论。在20世纪50年代，中国数学家吴文俊基于代数拓扑学中的上同调理论，揭示了判定图的平面性的一个判准。另一方面，十多年之后，生于英国的加拿大数学家W.T.Tutte，基于在50年代他本人引进的实域上链群的理论，也发现了一个判准。然后，于80年代，本书作者基于二元域（GF（2））上的空间理论，将这两个判准简化为一个。这就是在5.2节中所说的吴（文俊）Tutte定理。于20世纪60年代初，从L. Ausla，nder-和v.Pai-ter发表用计算机的算法思想判定图的平面性方面的第一篇文章，直到J.：Hopcroft和R.Tarian的第一个线性时间算法的出现，在文献中讨论这一经典课题的文章竞有数百篇之多。在70年代，吴文俊也构造了一种算法，将它转化为解一组模2方程的问题。接着，本书作者把这一结果改进到每个方程至多含有两个模2变量。然后，他又得到了一些新的判准，表明从算法复杂性的角度来看，平面性的问题相当于在5.3节中引进的平面性辅助图上求一个支撑树，5.4节中的主要定理就是这些判准。第7章提供了第5章中所描述的基本理论的进一步发展，对于平面性和平面嵌入，揭示了基于确向树与确向嵌入的禁用构形的完备集。这就使我们能够求出节点数和边数均为原图的节点数和边数的线性函数的平面性辅助图，从而在算法复杂性上也达到了线性的顶峰。第2-4章是第5章和第7章的基础。在第2章中，引进了确向树和确向上树，以及它们的一些将会用到的性质。第3章是关于图中的空间。其中包括循环空间，上循环空间，双循环空间，以及它们的结构。第4章处理平面图的至关重要的结果。例如，那些由：Euler公式能导出的，唯一性，直线和凸表示等。特别是还讨论了Jordan曲线定理的多面形模式。当然，第1章简述了全书所必需的有关集合、序、图、群以及曲面的基本知识。

内容概要

本书在第一版的基础上修订再版，主要增添了有关图在亏格非零曲面上的可嵌入性方面的一批新结果，主要内容包括：多面形与曲面、联树模型、图上的空间、平面上的图、平面可嵌入性、高斯交叉问题、平面嵌入、纵横曲面嵌入、网格可嵌入性、嵌入的同构、图的分解、曲面可嵌入性，曲面上的图、极嵌入问题、图和上图拟阵、纽结不变量等。本书在第一版的基础上，除文字上的更改与精简和结果的简化与改进外，还充实了许多新的内容，例如增添了图的扩充树，提供了Jordan定理第一多面形式的充分性，增添了一般曲面的纵横表示，使得可以将平面情形拓广到曲面的情形，提供了更有效地识别嵌入同构的算法，以及对嵌入非对称化的过程等。    本书可供数学(包括纯粹数学与应用数学)、理论物理(统计力学与量子物理)、计算机科学(逻辑设计、算法及其复杂性)、电子工程(集成电路的布局与布线)等专业的大学生、研究生、教师及科研工作者参考阅读。

书籍目录

《现代数学基础丛书》序第二版序第一版序第1章  预备知识  1.1  集合与关系  1.2  剖分与置换  1.3  图与网络  1.4  群与空间  1.5  注记第2章  多面形与曲面  2.1  多面形  2.2  支柱  2.3  支架  2.4  初等等价  2.5  曲面的分类  2.6  图的曲面嵌入  2.7  注记第3章  联树模型  3.1  树与上树  3.2  确向树  3.3  扩张树  3.4  注记第4章  图上的空间  4.1  循环，上循环和双循环  4.2  循环空间  4.3  上循环空间  4.4  双循环空间  4.5  注记第5章  平面上的图  5.1  Euler公式的利用  5.2  Jordan曲线定理  5.3  唯一性  5.4  表示  5.5  注记第6章  平面性  6.1  浸入  6.2  吴(文俊)-Tutte定理  6.3  平面性辅助图  6.4  主要定理  6.5  注记第7章  高斯交叉问题  7.1  交叉序列  7.2  Dehn变换  7.3  代数原理  7.4  交叉问题  7.5  注记第8章  平面嵌入  8.1  左和右确定  8.2  禁用构形  8.3  基本序表征  8.4  数平面嵌入  8.5  注记第9章  纵横曲面嵌入  9.1  纵横曲面模型  9.2  纵横嵌入  9.3  叁可嵌入性  9.4  双可嵌入性  9.5  单可嵌入性  9.6  非平面扩张  9.7  注记第10章  网格可嵌入性  10.1  许可性  10.2  隅序列  10.3  一般判准  10.4  特殊判准  10.5  注记.第11章  嵌入的同构  11.1  嵌入的自同构  11.2  Euler和非Euler码  11.3  同构的确定  11.4  注记第12章  图的分解  12.1  二连通分解  12.2  三连通分解  12.3  平面分解  12.4  页分解  12.5  纵横分解  12.6  注记第13章  曲面可嵌入性  13.1  树迂定理  13.2  代数判准  13：3  组合判准  13.4  构形判准  13.5  注记.第14章  曲面上的图  14.1  必要条件  14.2  上可嵌入性  14.3  商嵌入  14.4  下可嵌入性  14.5  注记第15章  极嵌入问题  15.1  最优凸嵌入  15.2  最短三角剖分  15.3  极少折数嵌入  15.4  极小面积嵌入  15.5  注记第16章  图和上图拟阵  16.1  二分拟阵  16.2  正则性  16.3  图性与上图性  16.4  注记第17章  纽结不变量  17.1  纽结类型  17.2  图的模型  17.3  Tutte多项式  17.4  泛多项式  17.5  Jonse多项式  17.6  注记参考文献术语索引作者索引《现代数学基础丛书》已出版书目

章节摘录

插图：

编辑推荐

《图的可嵌入性理论(第2版)》是现代数学基础丛书之一。

用户评论 (总计1条)

•   这是我们祖师爷的书，相信会对自己有帮助的。没来得及看完，仔细翻了翻，还是很好地。