欧拉图与相关专题
2012-4
科学出版社
费莱施纳
485
642500
无
本书是迄今为止唯一的一本全面阐述欧拉图理论的主要研究成果和研究方法及其与其他图论问题之间的联系的专著。本书包含两卷共十章。第一卷从欧拉的哥尼斯堡七桥问题开始，由浅入深地介绍了欧拉问题的起源，给出图的基本概念和预备知识，然后相继地介绍了无向图、有向图以及混合图中欧拉迹的结构性定理，欧拉迹的若干推广，各种类型的欧拉迹，欧拉迹的变换。在第二卷中，详尽地介绍了著名的中国邮递员问题，欧拉迹的计数问题，最后讨论了与欧拉问题相关的算法和计算复杂性。每章后面配有习题，帮助读者理解和掌握本章的主要内容。
本书适合从事图论研究的研究生和科研工作者使用，也是其他数学和计算机科学研究人员很好的参考书。
作者：（美国）费莱施纳(Fleischner,H.) 译者：孙志人 李皓 刘桂真 刘振宏 等
第一卷第1章 引言第2章 欧拉图理论的三个支柱第3章 基本概念和预备知识3.1 混合图与它们的基本要素3.2 图与混合有向图的子图3.3 导出子图3.4 路径、迹、路、圈、树;连通度3.5 相容性,K*v的循环序和对应的欧拉迹3.6 匹配、1-因子、2-因子、1-因子分解、2-因子分解、二部图3.7 图的曲面嵌入、同构3.8 平面图的着色3.9 哈密顿圈3.10 关联矩阵和邻接矩阵、流和张力3.11 算法及其复杂性3.12 注记第4章 特征定理和推论4.1 图4.2 有向图4.3 混合图4.4 习题第5章 再论欧拉迹及其推广展望5.1 迹分解,路、圈分解5.2 奇偶性结果5.3 双迹5.4 交叉边界:图的分拆5.5 习题第6章 欧拉迹的各种类型6.1 回避特定转移的欧拉迹6.1.1 有向图中P(D)相容欧拉迹6.1.2 双欧拉有向图中的反欧拉迹和图的双欧拉定向6.1.3 有向图中的D0-偏好欧拉迹6.2 两两相容欧拉迹6.2.1 有向图中的两两相容欧拉迹6.3 平面欧拉图中的A-迹6.3.1 平面欧拉图中的A-迹和平面3-正则图中的哈密顿圈之间的对偶性6.3.2 欧拉图中的A-迹和哈密顿圈6.3.3 如何找出A-迹:一些复杂性讨论和算法的建议6.3.4 关于非交叉欧拉迹和A-迹的注记以及另一问题6.4 习题第7章 欧拉迹的变换7.1 图中任意欧拉迹的变换7.2 特殊的欧拉迹的变换7.2.1 特殊类型的欧拉迹和κ1-变换的应用7.3 有向图中的欧拉迹的变换7.4 最终注解及一些未解决的问题7.5 习题参考文献第二卷第8章 各种类型的闭覆盖途径8.1 双迹8.2 图中的值-真途径和整流8.3 中国邮递员问题8.3.1 关于图上的中国邮递员问题8.3.2 有向邮递员问题8.3.3 混合邮递员问题8.3.4 带风向的邮递员问题和最后注记8.4 习题第9章 欧拉迹及其数目9.1 有向图和(混合)图的奇偶性的结果9.1.1 矩阵代数的一个应用9.2 计数初涉9.2.1 矩阵树定理9.2.2 有向图和图的欧拉迹计数9.2.3 关于欧拉定向的数目9.2.4 拜斯特定理的应用和推广9.2.5 其他说明9.3 习题第10章 欧拉迹和圈分解的算法及迷宫搜索算法10.1 欧拉迹的算法10.2 圈分解算法10.3 迷宫10.4 习题参考文献对第一卷的更正和补录人名译名表
版权页：插图：第1章 引言 冠尼希（D′enesK¨onig）的书Theoriederendichenund Unendlichen Graphen（《有限图与无限图的理论》）[K¨ ONI36a]于1936年第一次出版时，只用248页（不包括前言、目录和参考文献）就囊括了自欧拉（L。Euler）发表哥尼斯堡七桥问题的解的文章以来，200年中图论领域的大部分内容。 实际上，欧拉把他的文章提交给圣彼得堡科学院是在1735年8月26日，但 他的文章“Solutioproblematisadgeometriamsituspertinentis”一直到1741年才发表在Commentarii Academiae Scientiarum Imperialis Petropolitanae上。由于这个Commentarii注明的日期是1736年，所以图论作为数学的一个分支一般被认为诞生在1736年。 然而，D。K¨onig在他的前言中指出：他的书中所考虑的图论仅限制在所谓的绝对图中（现在称为抽象图），除几个例外的情形，他没有讨论拓扑图论（他称为相对图论）和计数图论。 D。K¨onig的书问世以后，特别是第二次世界大战结束以后，图论得到了飞速发展。专门发表组合论文的期刊越来越多，它们所涉及的文章中大约有一半是图论文章。例如，《图论杂志》创刊于1977年。图论研究的繁荣不仅反映在图论书籍数目的增长上，而且反映在这些书籍的内容上。它们中有很多都聚焦于图论的一些特殊专题，如拓扑图论、代数图论以及近年来具有强劲势头的算法图论（该方向的研究是出于计算机科学的需要）。由此可见，图论也遵循着科学发展的一般过程。最初，它从一般领域中脱离出来（D。K¨onig的书的子标题是“Kombinatorische Topologieder Strekkenkomplexe”――一维复形组合拓扑）。然后它又按照所得的结果和所用的方法分化为若干不同的分支。图论的这种发展可以被Selected Topicsin GraphTheory和Selected Topicsin Graph Theory2（[BEIN78a]，[BEIN83a]）（《图论专题精选》和《图论专题精选2》）的出版所见证，其主编是本尼克（L。W。Beineke）和威尔逊（R。J。Wilson）。书中包含了不同作者撰写的22篇综述文章。现在《图论专题精选3》也已出版。《图论应用》包含了12篇综述文章，涉及的是图论在各学科的应用，编者同上。 欧拉解决哥尼斯堡（现为加里宁格勒）七桥问题的文章并未把功劳归于自己，他在文章中提到了Leibniz（Leibniz）： 几何学中除了与数量有关并且为人们极为重视的那个分支外，还有 一个目前几乎一无所知的分支这就是Leibniz首先提出的位置几何学（ge- ometria situs）。 这个分支只涉及位置的确定及其性质，它不涉及度量，也 不作计算。。 欧拉继续说明：目前还不十分清楚哪些问题与位置几何学有关，也不清楚解决它们要用什么方法。但是他肯定，哥尼斯堡七桥问题就是这样一个问题，因为它的解只涉及位置，而没有用任何计算[WILS85a]。 事实上，早在1679年，Leibniz在他给惠更斯（Huygens）的信（摘自[WILS85a]）中说：“我不满足于代数，因为代数里既没有几何中最简短的证明，也没有几何中最漂亮的构造。因此，我认为需要另外一种类型的分析，几何的或线性的，它能像代数处理数量大小一样直接处理位置。” 通过引进术语“位置分析”（analysissitus），Leibniz并没有奠定一个新的数学研究领域，而是指出了一个可能取得进展的总的研究方向（对“位置分析”这个术语的历史感兴趣的读者，可以参见Wilson的文章[WILS85a]）。在第2章，我们将对图论的历史作更多评述。在这里值得一提的是，K¨onig的书大概是图论早期最丰富的专著（这里“早期”是指1936年K¨onig的书出版以前图论的发展时期）。 但为什么要出一本关于欧拉图的书？是不是因为最近举行了图论（特别是欧拉的文章）250周年的纪念活动？本书的出版和图论250周年纪念日接近纯粹是一种巧合（我原计划在1985年3月底完稿）。但是，正如前言中指出的，欧拉图方面的文章不仅在数量上增长极快，而且该专题的统一理论也趋向成熟。这两个事实成为写《欧拉图与相关专题》一书的必要条件。许多同事也对这件事表示出了兴趣，本书和图论发展的大趋势是一致的。虽然这个过程是缓慢的，但是图论在过去的20多年里确实分化出一些不同分支。 第2章将给出三篇文章的原始版本。大多数图论学家认为它们构成了欧拉图理论的主要根基。本书大部分内容都致力于与这三篇文章中提出的概念有直接关系的一些结果。但与现在图论的发展相比，我认为只限于欧拉图的这部分内容会太狭隘。这一观点也体现在我的综述文章“欧拉图”里（见[BEIN83a]）。另一方面，这一观点提出了一个问题：如何确定这样一本书的材料选择问题。 由于本书是第一次集中讨论欧拉图，所以我决定尽可能广地覆盖这一领域的问题。某些专题我讨论得很详细，而另一些专题像综述一样点到为止。当然，这样做也有一些缺点。在某些情况下，读者要想了解该专题更多的内容，常常不得不去查阅其他的书或本书所引用的原始文献。另外，本书的某些内容会与图论中的其他分支相重叠，如在中国邮递员那一章，在1-因子分解起重要作用的地方，以及在计数、着色和一些其他地方，都有明显重叠。但是一般来说，恰恰由于现代图论的发展，这样或多或少的重叠是不可避免的。 为了选取恰当的材料，我查阅了数百篇文献。许多参考文献在本书中并没有进行广泛的讨论。不过本书的目的之一是指出目前研究的各种不同方向。可能有的读者会感到参考文献的数量远远多于本书讨论过的问题，但是书后的参考文献可以有利于帮助感兴趣的读者延伸到本书内容以外的各个研究方向。我查阅了众多的文献，希望不要漏掉欧拉图理论方面的重要内容，以弥补我的综述文章在这方面的不足。 最后的一项要点是，本书是自封闭的，因为我希望它的读者尽可能多一些。因此，第3章论述了图论的基础理论，以满足后面几章的需要。要读懂某些专题，或多或少还需要更广泛的数学知识，这有点使人困扰。因此，本书中尽可能避免使用 “容易导出”，“显而易见”等语句。许多数学家（包括我自己），不止一次地遇到过这种情况：要看明白一个“容易”，还需要笔和纸，并花掉半个小时，甚至更长的时间。因此，在使用了大量图形来阐明情况的同时，我并未用图形去代替逻辑证明。但是在某些情形下，某些结果的完整证明还是留给了读者，作为不太困难的练习。因此，本书的内容，无论对大学生还是对研究生来说，作为欧拉图理论的课程是都已足够了，即使不熟悉图论的数学家也可以参考。由于本书包含了许多最新的结果（其中有些结果只是部分地解决了某些未决问题）、相当多的猜想，故图论方面的研究者们也会感兴趣。 再说说算法和复杂性研究的问题。许多问题（如欧拉迹、圈分解、邮递员路线和迷宫通路等问题）是用算法陈述的。但是，本书的目的不是要理论化提出一个算法。复杂性问题也是如此。从理论的观点来看，问题是否多项式时间可解是很重要的。但在本书中，一个算法的复杂性是O（n）还是O（n2）是属于次要的事。我知道许多同事（特别是有这方面倾向的计算机科学家和图论学家）会对此不满。 我愿意接受任何人的批判性的意见（肯定的、否定的或是混合的），因为这可以帮助我改进工作。我将对所有给我提出意见的各位作出回应。 第2章 欧拉图理论的三个支柱 欧拉关于哥尼斯堡七桥问题的文章[EULER36a]和Hierholzer关于构造连通欧拉图的欧拉迹的文章[HIER73a]都有许多不同的译本。但是，接下来我还是要给出我自己的译文①。决定这样做是因为我发现这些译本中有一个缺点：它们是“时新”的译本，多多少少地忽略了文章发表时的写作风格。因此，从历史的观点来看，这些译本是不够准确的，它们无意中曲解了认知之路，我的译本并非一个学了6年拉丁文的高中生递交的家庭作业，也并非出于对版权的担心。 关于欧拉文章的历史说明，有兴趣的读者可参见文献[WILS85a，WILS86a]和[SACH86a，SACH86b]。 一个位置几何问题的解。 1.几何学中有一部分内容与数量有关，人们对其颇感兴趣。除此之外，还有一部分内容，人们对它都知之甚少。这部分几何首先由Leibniz提出，称为位置几何。它研究仅由位置就可确定的几何，并研究位置的性质。在这种几何中，人们不关心数量，也不关心计算。然而，什么问题属于位置几何？求解它们要使用什么方法？一直没有明确的界定。当最近有一个问题被提出来时，我确信它属于位置几何。它看上去是一个几何问题，同时又具有这样的性质：不需要确定数量关系，通过量的计算也无法解决它。特别地，其求解只需要位置关系就可以，而计算是无益于事的。因此，作为位置几何的一个例子，决定在此介绍我解决这类问题的一个方法。 2.据说这个问题是相当有名的，并且与以下叙述有关：哥尼斯堡是普鲁士的一个岛，称为derKneiphof。围绕它的河被其分为两支（图1）。河上架有7座桥a，b，c，d，e，f，g。问题是一个人能否经过每座桥一次且恰好一次。据说有的人否认这件事的可能性，而另一些人表示怀疑，但是没有人能给出确定的答案。我将这一问题推广到了一般情形：不管河的形状和支流分布如何，也不管河上多少座桥。 3.下述方法肯定能解哥尼斯堡七桥问题：列出所有可能的行走路线，由此就可以知道是否有某条路线满足要求。但是由于组合的数目太大，这种方法是极端困难和辛苦的，而且这种方法很难应用于桥数更多的情形。这种方法会导致许多无关①感谢维也纳奥地利科学院的H。Reitterer先生，他核对了我对欧拉文章的译文。 。 原书II。2～II。11是欧拉文章的影印件，共10页，摘自于欧拉全集，I7，代数研究）。这里是欧拉文章的译文。――译者 因素的讨论，包括复杂度。排除了这种方法后，我力求寻找其他途径，一种只判断符合要求的路线是否存在的途径，我猜想应该存在这样一个简单的方法。 4.我的方法基于表示路线的适当方式。大写字母A，B，C，D表示被河分割的区域。如果一个人从区域A经过桥a或者桥b走到区域B，就用字母AB表示这个转移。第一个字母表示旅行者从何而来，第二个字母表示穿过桥后到达的区域。如果旅行者接着由区域B经过桥f到达区域D，这个转移用BD表示。ABD表示这两个相继的转移AB和BD，字母B是第一次转移到达的区域，也是第二次转移离开的区域。 5.类似地，若旅行者由区域D继续穿过桥g到达区域C，就用4个字母ABDC表示这三个相继的转移。从ABDC这4个字母中可以看出，旅行者首先出现在区域A，然后到达区域B，再前行到达区域D，接着又到达区域C。因为这些区域是被河流分开的，所以旅行者必须穿过三座桥。类似地，相继穿过4座桥将用5个字母表示。无论旅行者穿过多少座桥，这条路都将用一串字母表示，其中字母数比穿过的桥数多1。因此，穿过7座桥将用8个字母来描述。 6.这种记法并不需要考虑穿过的是哪座桥。当一个人可以穿过多座桥从一个区域到达另一区域时，他走哪座桥是无关紧要的。因此，若一个人能穿过7座桥且每座桥恰好穿过一次，则他的走法可以用8个字母表示。它们的顺序必须满足：前后相继的A和B将出现两次，这是因为区域A和B间有两座桥a和b相连。类似地，前后相继的A和C出现两次，而前后相继的A和D，B和D，C和D各出现一次。 7.因此，这个问题约化为能否用4个字母A，B，C，D构成8个字母的序列，使得序列中相继字母出现的次数满足上述要求。但在试图找出这样一个序列之前，需要先考察这种安排是否可能。因为如果能证明这样的安排是不可能的，那么构造此序列的一切努力都是无效的。因此，我研究了一个简单的规则，以判断这个问题和所有类似的问题是否有效。 8.为了发现这样的规则，我考虑了一个具体的区域A，通向A的桥可能有任意多座（图2）。在这些桥中，先考虑了一座具体的桥a。如果旅行者穿过桥a，那么他或者跨越这座桥之前在区域A里，或者跨越桥之后到达区域A。因此，为了如上 所述地记录这次转移，字母A必须出现一次。如果有三座桥a，b，c通向区域A，并且旅行者要穿过所有这三座桥，那么不管他开始是否在区域 A里，在他的走法的描述中，字母A都将出现两次。如果桥的数目是任一奇数，那么字母A出现的次数就为桥数加1的一半。 9.在哥尼斯堡七桥问题（图1）中，因为有5座桥通向区域A，因此，在遍历这些桥的描述中，字母A必须出现三次。由于有三座桥通向区域B，故字母B必须出现两次。类似地，字母D和C都出现两次。在描述经过7座桥的8个字母的序列中，字母A要出现三次，字母B，C，D各要出现两次，这样的序列是不存在的。因此，按上述要求通过哥尼斯堡七桥的路线也是不存在的。 10.其他这类问题，假定通向每一个区域的桥数都为奇数，按类似的方法也能够判断是否有一条通过每座桥恰好一次的路线。如果字母出现的总数等于桥数加1，那么这样的路线是可能的。但是如果像上述例子一样，字母出现的总数大于桥数加1，那这样的路线就不存在了。我提出的字母A的出现次数的法则，不管这些桥是从一个区域通向A的，还是从不同区域通向A的，都是有效的。 11.然而，如果通向A的桥数为偶数，那就必须考虑旅行者是否是从区域A出发的。如果有两座桥通向区域A，并且旅行者是从区域A出发的，那么字母A就必须出现两次。第一次表示他穿过一座桥离开区域A，而第二次表示他穿过另一座桥返回区域A。但是如果旅行者是从另一区域出发的，那么字母A只出现一次，它既表示到达区域A，也表示从区域A离开。 12.假设有4座桥通向A，并且旅行者从区域A出发，那么字母A就在整条路线中出现三次。但是如果旅行者是从另一区域出发的，那么字母A只出现两次。假设有6座桥通向区域A，并且旅行者从区域A出发，那么字母A就在整条路线中出现4次。但是如果旅行者是从另一区域出发的，那么字母A只出现三次。一般地，如果假设有2n（n∈N）座桥通向区域A，并且旅行者从区域A出发，那么字母A就在整条路线中出现n+1次。但是如果旅行者从另一区域出发，那么字母A只出现n次。 13.在这样一条路线里，其出发地只能有一个区域。由通向一个区域的桥数，就能算出该区域出现的次数。如果桥数为奇数，那么这个奇数加1的一半就是这个区域出现的次数；如果桥数为偶数，那么这个偶数的一半就是这个区域出现的次数。
《欧拉图与相关专题》是赫伯特•费莱施纳先生的重要学术著作。在这本书中，费莱施纳结合他多年的研究和对图论学科的深刻理解，对欧拉问题进行了全面和深刻的阐述，可以说这是欧拉图唯一的一本高水平专著。《欧拉图与相关专题》适合从事图论研究的研究生和科研工作者使用，也是其他数学和计算机科学研究人员很好的参考书。
无
欧拉是我最向往的大数学家,所以要不断地去了解他的思想!
在看之中，比较深入。。。。