有向图的理论、算法及其应用

2009-1  

科学出版社  

J.邦詹森  

608  

G.古廷  

无  

图论是离散数学中普及最广的学科之一，不仅是由于它自身理论的迅速发展，而且是因为它在实际中有着大量的重要应用。近几十年来的许多深刻的理论结果也导致了图论学科的快速成长。然而，作为一个研究领域，图论仍然还是一门相对年轻的学科。图的理论可以分为无向图理论和有向图理论两大分支。虽然这两大理论分支有着大量且重要的应用，但由于诸多的原因，无向图比有向图得到更为广泛的研究。首先因为无向图在一定程度上是有向图的一个特殊类（对称有向图），所以，凡能够表述为无向图和有向图的问题通常用有向图的方法解决较为容易；另一个原因是，不像无向图的情形，除了几本重要的书包含两类图的传统和近期的结果，近25年来没有一本专门介绍关于有向图研究的完整结果的著作。在一般的教科书中，大多数作者用一章来讲述有向图，或者只有少量的有向图基本知识与结论。尽管如此，在近30年中，有向图理论还是得到了长足的发展。超过3000篇的研究论文不仅涵盖了具有理论意义的结果，而且包括了重要的算法及其应用。为了实际的需要，本书概括了有向图的基本知识，并从深层次的角度介绍了理论和算法这两个方面的研究成果及应用。本书竭力为专题研究填补文献与实用手册间的沟壑。书中的基本内容是针对具有大学数学基础知识的读者，然后在几个研究领域（包括连通性、图的定向、子模流、有向图的路和圈、竞赛图的推广以及有向图的推广等）的主要方向上逐步到达最新的研究成果。我们为本书配备了超过700道练习题、大量应用以及适宜讨论的专题。对于我们所期望的不同群体的读者（研究生、本科生、离散数学研究者、计算机科学中各个领域的研究者、运筹学研究、人工智能、社会科学以及工程技术人员等）来说，书中所有的专题不可能对全体读者均有同等的意义。然而，我们相信，每位读者都能从这本书里找到吸引自己的有趣专题。显然，本书不可能是关于有向图的百科全书，但是，我们尽可能地提供了许多有意义的结论。书中数量众多的证明和技巧为读者详细地说明了有向图理论和算法中所使用的各种各样的方法和手段。

本书作者从近30年关于有向图理论研究的数千篇论文中精选了具有理论意义、重要算法及其实际应用的结果，涵盖了有向图理论中从最基本到较为高深的重要专题。主要内容有：有向图的基本知识和理论、连通性、图的定向、网络流、哈密尔顿性的深入研究、有向图的路和圈、子模流、竞赛图的推广以及有向图的推广、Menger定理和NP完全问题等。书中介绍了有向图研究中数十个未解决的问题和猜想，尽可能为读者在主要方向上提供最新的研究成果。对于计算机科学领域的学者来说，书中的大量算法以及实际应用的例子提供了难得的帮助。此外，配备了练习题700多道、方便查询的参考文献762篇，以及记号和术语索引等。 本书适合数学及应用数学、离散数学、运筹学、计算机科学等专业的本科生、研究生、教师及研究人员阅读，也可供人工智能、社会科学以及工程技术人员参考。

作者：(丹麦)J.邦詹森 译者：(英国)G.古廷

第1章 基本术语及结论 1.1 集合、子集、矩阵和向量 1.2 有向图、有向子图、邻集和度数 1.3 有向图的同构及其基本运算 1.4 途径、迹、路、圈和路圈有向子图 1.5 强连通性和单侧连通性 1.6 无向图、双定向和定向性 1.7 混合图和超图 1.8 有向图和无向图的分类 1.9 算法简介 1.9.1 算法及其复杂性 1.9.2 NP完全问题和NP困难问题 1.10 应用：求解2可满足性问题 1.11 习题第2章 距离第3章 网络流第4章 有向图类第5章 哈密尔顿性及其相关问题第6章 深入研究哈密尔顿性第7章 全连通性第8章 图的定向第9章 不交路和不交树第10章 有向图的圈结构第11章 有向图的推广第12章 一些重要的专题参考文献记号索引术语索引译后记《现代数学译丛》已出版书目

插图：第1章 基本术语及结论本书的大部分术语和记号在这一章中介绍，其中大量的例子、图示和结论将有助于读者更好地理解这些术语和记号。本章中简单而又重要的结论形成有向图的一组基本定理，我们使用常规标准的术语和记号。因此，读者在快速阅读本章之后就可以学习其他章节，对于那些不熟悉的术语和记号均可以在所阅读的章节或者从书后的索引里找到。1.1节复习集合和矩阵的基本术语和记号。1.2节介绍有向图、有向伪图、有向子图、赋权有向伪图、邻集、半度以及其他关于有向图理论的若干基本概念。1.3节介绍有向图的同构和有向图之间的运算。在1.4节中，我们要认识途径、迹、路和圈，并学习竞赛图和无圈图的一些性质。强连通、单侧连通的概念和无向图将分别放在1.5节和l。6节中介绍。此外，欧拉有向多重图、具有入（出）分支的有向图以及具有强有向性的图也放在1.6节中介绍。1.7节学习混合图和超图。1.8节介绍几类重要的有向图和无向图。在1.9节中给出算法的初步认识。最后一节的内容是介绍求解2可满足性问题的一个应用。

译稿交付出版社，我们却没有如释重负之感。《有向图的理论、算法及其应用》一书的容量十分庞大：书中引用的论文和书籍762篇（本），还不包括书中涉及的私人通信里未发表的文章等。全书12章，共有151个引理，465个定理，100个推论，89个命题，26个问题，54个猜想以圾三十余个算法。书中有很多没有用正规格式表述的结论、未解决的问题和猜想，还有那些嵌入在证明内的算法等，我们均没有一一进行统计。值得注意的是，在700多道习题中，部分习题是正文中没有提及的结论、算法和问题等。本书中的有向图理论几乎涵盖了当今有向图理论的主要研究专题，如哈密尔顿圈问题、最短路问题、网络流理论等。书中关于哈密尔顿圈问题的深入研究，为读者介绍了各种各样关联到哈密尔顿问题及其推广的专题；Mengel定理在研究K（弧）强有向图的应用和推广，如Edmonds分枝定理和K链接问题等，将十分有助于启发我们研究问题的思路和认识研究对象的方式，有益于我们设计研究方案或提出进攻困难问题的方向。本书作者南丹麦大学数学与计算机科学系J。邦詹森教授和伦敦大学皇家霍洛威学院计算机科学系G.古廷（Gregory Gutin）教授在内容编排和写作设计方面独具匠心，由浅显基本的结论逐步过渡到当今有向图理论中某些专题研究的前沿。他们力图使读者不仅理解、掌握有向图的成熟理论，而且有能力投入到有向图中未解决问题的研究主流里。加上书后的参考文献、精炼的记号和一详尽的术语，我们认为这是一本兼顾教学和研究双重任务的高度专业性书籍。本书的重要特色之一是提供了大量的证明技巧和方法。例如，Madei的撕裂技巧、多重插入技巧、两类问题之间的简约或等价转换、算法式论证、网络流模型、集合函数的子模流、拟阵算法等。书中使用了一些代数、组合、概率和线性规划等学科中的部分方法，如Ramsey定理、ErdSs Szekeres定理、阿贝尔群、布尔变量、对偶定理等，为读者的自行研究提供了大量的工具。作者指出，无向图在一定程度上是有向图的一个特殊类（对称有向图）。所以，无向图理论和有向图理论的有机结合也是值得我们考虑和研究的一个方面。

《有向图的理论算法及其应用》概括了有向图的基本知识，并从深层次的角度介绍了理论和算法这两个方面的研究成果及应用。书中的基本内容是针对具有大学数学基础知识的读者，然后在几个研究领域（包括连通性、图的定向、子模流、有向图的路和圈、竞赛图的推广以及有向图的推广等）的主要方向上逐步到达最新的研究成果。《有向图的理论算法及其应用》配备了超过700道练习题、大量应用以及适宜讨论的专题。

无

有向图的理论、算法及其应用 PDF格式下载

服务态度好概括了有向图的基本知识，并从深层次的角度介绍了理论和算法这两个方面的研究成果及应用。书中的基本内容是针对具有大学数学基础知识的读者，然后在几个研究领域(包括连通性、图的定向、子模流、有向图的路和圈、竞赛图的推广以及有向图的推广等)的主要方向上逐步到达最新的研究成果。本书配备了超过700道练习题、大量应用以及适宜讨论的专题。

确实像之前的朋友说的，国内有向图的研究一塌糊涂，这本书简直是挽救众多学习图论的学子的利器啊！

配送速度很快，书也不错，有参考价值，很喜欢。

给朋友买的，估计不错的

有向图方面的好书。E文不好的推荐参考。有向图哈密顿回路方面没有几本像样的中文书籍。

作为算法党总是感觉书里面的标记和符号的用法跟习惯不符……比较偏理论，比较高深，不够通俗，算法的实现不太简洁