设为首页 - 加入收藏
广告 1000x90
您的当前位置:金沙9001链接 > 金沙js官网 > 正文

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

来源:未知 编辑:admin 时间:2019-09-11

  声明:百科词条人人可编辑,词条创建和修改均免费,绝不存在官方及代理商付费代编,请勿上当受骗。详情

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

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

  译稿交付出版社,我们却没有如释重负之感。《有向图的理论、算法及其应用》一书的容量十分庞大:书中引用的论文和书籍762篇(本),还不包括书中涉及的私人通信里未发表的文章等。全书12章,共有151个引理,465个定理,100个推论,89个命题,26个问题,54个猜想以圾三十余个算法。书中有很多没有用正规格式表述的结论、未解决的问题和猜想,还有那些嵌入在证明内的算法等,我们均没有一一进行统计。值得注意的是,在700多道习题中,部分习题是正文中没有提及的结论、算法和问题等。

  本书中的有向图理论几乎涵盖了当今有向图理论的主要研究专题,如哈密尔顿圈问题、最短路问题、网络流理论等。书中关于哈密尔顿圈问题的深入研究,为读者介绍了各种各样关联到哈密尔顿问题及其推广的专题;Mengel定理在研究K(弧)强有向图的应用和推广,如Edmonds分枝定理和K链接问题等,将十分有助于启发我们研究问题的思路和认识研究对象的方式,有益于我们设计研究方案或提出进攻困难问题的方向。

  本书作者南丹麦大学数学与计算机科学系J。邦詹森教授和伦敦大学皇家霍洛威学院计算机科学系G.古廷(Gregory Gutin)教授在内容编排和写作设计方面独具匠心,由浅显基本的结论逐步过渡到当今有向图理论中某些专题研究的前沿。他们力图使读者不仅理解、掌握有向图的成熟理论,而且有能力投入到有向图中未解决问题的研究主流里。加上书后的参考文献、精炼的记号和一详尽的术语,我们认为这是一本兼顾教学和研究双重任务的高度专业性书籍。

  本书的重要特色之一是提供了大量的证明技巧和方法。例如,Madei的撕裂技巧、多重插入技巧、两类问题之间的简约或等价转换、算法式论证、网络流模型、集合函数的子模流、拟阵算法等。书中使用了一些代数、组合、概率和线性规划等学科中的部分方法,如Ramsey定理、ErdSs Szekeres定理、阿贝尔群、布尔变量、对偶定理等,为读者的自行研究提供了大量的工具。作者指出,无向图在一定程度上是有向图的一个特殊类(对称有向图)。所以,无向图理论和有向图理论的有机结合也是值得我们考虑和研究的一个方面。

  图论是离散数学中普及最广的学科之一,不仅是由于它自身理论的迅速发展,而且是因为它在实际中有着大量的重要应用。近几十年来的许多深刻的理论结果也导致了图论学科的快速成长。然而,作为一个研究领域,图论仍然还是一门相对年轻的学科。

  图的理论可以分为无向图理论和有向图理论两大分支。虽然这两大理论分支有着大量且重要的应用,但由于诸多的原因,无向图比有向图得到更为广泛的研究。首先因为无向图在一定程度上是有向图的一个特殊类(对称有向图),所以,凡能够表述为无向图和有向图的问题通常用有向图的方法解决较为容易;另一个原因是,不像无向图的情形,除了几本重要的书包含两类图的传统和近期的结果,近25年来没有一本专门介绍关于有向图研究的完整结果的著作。在一般的教科书中,大多数作者用一章来讲述有向图,或者只有少量的有向图基本知识与结论。

  尽管如此,在近30年中,有向图理论还是得到了长足的发展。超过3000篇的研究论文不仅涵盖了具有理论意义的结果,而且包括了重要的算法及其应用。为了实际的需要,本书概括了有向图的基本知识,并从深层次的角度介绍了理论和算法这两个方面的研究成果及应用。

  本书竭力为专题研究填补文献与实用手册间的沟壑。书中的基本内容是针对具有大学数学基础知识的读者,然后在几个研究领域(包括连通性、图的定向、子模流、有向图的路和圈、竞赛图的推广以及有向图的推广等)的主要方向上逐步到达最新的研究成果。我们为本书配备了超过700道练习题、大量应用以及适宜讨论的专题。对于我们所期望的不同群体的读者(研究生、本科生、离散数学研究者、计算机科学中各个领域的研究者、运筹学研究、人工智能、社会科学以及工程技术人员等)来说,书中所有的专题不可能对全体读者均有同等的意义。然而,我们相信,每位读者都能从这本书里找到吸引自己的有趣专题。

  显然,本书不可能是关于有向图的百科全书,但是,我们尽可能地提供了许多有意义的结论。书中数量众多的证明和技巧为读者详细地说明了有向图理论和算法中所使用的各种各样的方法和手段。

最新文章
热门文章

模板天下 金沙9001链接 联系QQ:000001 邮箱:0000001@qq.com

Copyright © 2002-2011 金沙9001链接 版权所有

Top