☆☆☆☆☆
简体网页||繁体网页



点击这里下载

类似图书 点击查看全场最低价

---

内容简介

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

内页插图

目录

第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章 距离
2．1 关于距离的术语和记号
2．2 最短路结构
2．3 寻找有向图距离的算法
2．3．1 宽度优先搜索（BFS）
2．3．2 无圈有向图
2．3．3 Dijkstra算法
2．3．4 Bellman-Ford-Moore算法
2．3．5 Floyd-Warshall算法
2．4 半径、出半径和直径之间的不等式
2．4．1 强有向图的半径和直径
2．4．2 出半径和直径的极值
2．5 定向图的最大有限直径
2．6 多重图定向的最小直径
2．7 完全多重图的最小直径定向
2．8 图扩张的最小直径定向
2．9 笛卡儿积图的最小直径定向
2．10 有向图中的王
2．10．1 竞赛图的2王
2．10．2 半完全多部分有向图中的王
2．10．3 广义竞赛图中的王
2．11 应用：单行道问题和闲话问题
2．11．1 单行道问题和有向图的定向
2．11．2 闲话问题
2．12 应用：旅行售货员问题的指数邻集局部搜索
2．12．1 TSP局部搜索
2．12．2 TSP的线性时间可搜索指数邻集
2．12．3 分配邻集
2．12．4 关于TSP的邻集结构有向图的直径
2．13 习题

第3章 网络流
3．1 定义及基本性质
3．1．1 流及流平衡向量
3．1．2 剩余网络
3．2 网络模型的简约
3．2．1 消除下界
3．2．2 单源单收点网络
3．2．3 循环
3．2．4 顶点上有费用及下界的网络
3．3 流分解
3．4 讨论剩余网络
3．5 最大流问题
3．5．1 Ford-Fullkerson算法
3．5．2 最大流与线性规划
3．6 寻找最大（s，t）流的多项式算法
3．6．1 沿最短增广路的流增广
3．6．2 在分层网络和Dinic算法中的块化流
3．6．3 前置流推进算法
3．7 单位容量网络和简单网络
3．7．1 单位容量网络
3．7．2 简单网络
3．8 循环与可行流
3．9 最小值可行（s，t）流
3．10 最小费用流
3．10．1 刻画最小费用流
3．10．2 创建最优化解
3．11 流的应用
3．11．1 二部分图的最大匹配
3．11．2 有向中国邮递员问题
3．11．3 寻找具有预先指定度的有向子图
3．11．4 有向多重图的路圈因子
3．11．5 覆盖指定顶点的圈有向子图
3．12 分配问题和运输问题
3．13 习题

第4章 有向图类
第5章 哈密尔顿性及其相关问题
第6章 深入研究哈密尔顿性
第7章 全连通性
第8章 图的定向
第9章 不交路和不交树
第10章 有向图的圈结构
第11章 有向图的推广
第12章 一些重要的专题
参考文献
记号索引
术语索引
译后记
《现代数学译丛》已出版书目

前言/序言

　　图论是离散数学中普及最广的学科之一，不仅是由于它自身理论的迅速发展，而且是因为它在实际中有着大量的重要应用。近几十年来的许多深刻的理论结果也导致了图论学科的快速成长。然而，作为一个研究领域，图论仍然还是一门相对年轻的学科，
　　图的理论可以分为无向图理论和有向图理论两大分支，虽然这两大理论分支有着大量且重要的应用，但由于诸多的原因，无向图比有向图得到更为广泛的研究。首先因为无向图在一定程度上是有向图的一个特殊类（对称有向图），所以，凡能够表述为无向图和有向图的问题通常用有向图的方法解决较为容易；另一个原因是，不像无向图的情形，除了几本重要的书包含两类图的传统和近期的结果，近25年来没有一本专门介绍关于有向图研究的完整结果的著作，在一般的教科书中，大多数作者用一章来讲述有向图，或者只有少量的有向图基本知识与结论。
　　尽管如此，在近30年中，有向图理论还是得到了长足的发展。超过3000篇的研究论文不仅涵盖了具有理论意义的结果，而且包括了重要的算法及其应用。为了实际的需要，本书概括了有向图的基本知识，并从深层次的角度介绍了理论和算法这两个方面的研究成果及应用。
　　本书竭力为专题研究填补文献与实用手册间的沟壑，书中的基本内容是针对具有大学数学基础知识的读者，然后在几个研究领域（包括连通性、图的定向、子模流、有向图的路和圈、竞赛图的推广以及有向图的推广等）的主要方向上逐步到达新的研究成果，我们为本书配备了超过700道练习题、大量应用以及适宜讨论的专题，对于我们所期望的不同群体的读者（研究生、本科生、离散数学研究者、计算机科学中各个领域的研究者、运筹学研究、人工智能、社会科学以及工程技术人员等）来说，书中所有的专题不可能对全体读者均有同等的意义。然而，我们相信，每位读者都能从这本书里找到吸引自己的有趣专题。
　　显然，本书不可能是关于有向图的百科全书，但是，我们尽可能地提供了许多有意义的结论，书中数量众多的证明和技巧为读者详细地说明了有向图理论和算法中所使用的各种各样的方法和手段。
　　强调算法是本书最主要的特色之一，而这一点却在一些图论书中被遗憾地省略。首先，算法常常在不少领域的研究中扮演着重要的角色，尤其是在计算机科学和数值计算的研究中。其次，（有向）图的许多问题本身就是算法问题，因此我们尽可能给出许多结论的构造性证明，利用这些构造性证明，读者就可以从所研究的问题中提取一些有效的算法，虽然本书描述了许多算法，但鉴于篇幅限制，我们没有提供全部必需的细节以使得读者能够正确地运用这些算法，这属于计算科学的范畴（常常是极为不平凡的工作），建议读者去阅读数据结构方面的书籍。
　　本书的另一个重要的特色是精选了数量可观的练习题，它们不仅可以帮助读者理解，而且可以使读者能够通过大量的材料吃透书中所介绍的内容。尝试解决这些习题（绝大部分是在本书中出现）将有助于读者掌握所学的专题以及主要的研究技巧，
　　通过从易到难的广泛而不间断地学习和训练，对于一些专门的问题，如（有向）图论、组合优化和图算法，读者将会发现本书的作用。此外，本书也可以应用于某些热门课题，如流、圈和连通性等。书中含有大量的解说，以帮助读者读懂不易理解的概念和深奥的证明。
　　出于使这本书成为一个便捷的研究参考书或大学教科书的考虑，我们增添了综合性的记号和术语索引，可以确信，详细的术语索引能够帮助读者找到所需要的对象而不必通读整个章节，特别地，书后的索引列出了许多关于公开问题和猜想的条目。本书所讨论的每一类有向图均拥有自己的条目，即在讨论这类图的主要页上。作为次条目，例如证明技巧条目，我们编制了不同证明技巧的索引，并标注出这些技巧所在的页码。
　　本书涵盖了有向图的从相当基本到较为高深范围的主要且重要的专题。根据我们的经验，这本书在今后的几十年内将有助于教学和参考文献搜索，我们在下面通过叙述一些重要的内容给出本书的轮廓，需要详细信息的读者可以参见目录或书后的术语索引。
　　第1章包括了本书所使用的大部分术语、记号以及一些基本结论，它们不仅在其他章节中被频繁地使用，而且被用作解释有向图的概念。进而，我们还将介绍几个基于这些结论的有向图的应用，并在本章的末尾处给出一个具体的应用。关于算法及其复杂性的基本概念也在这一章里一并介绍，依据综合性术语和记号索引，读者不必读完整个第1章后才进入其他章节的阅读与学习。
　　第2章和第3章讨论距离和网络中的流。尽管这两个专题的概念是基本的，然而，有向图中距离以及网络流的理论和算法特征却是相当重要的，因为它们对有向图的其他理论问题和大量实际问题有着高度的可应用性，尤其是作为强有力的模型工具。
　　关于距离，我们首先介绍赋权和未赋权有向图中最短路问题以及几个传统算法。第2章的主要内容是有向图中距离参数的最小化和大化，我们将用下列问题结束这一章：单行道问题、闲话问题、指数邻集局部搜索，并介绍一个关于组合优化问题寻找沂似优化懈的方法。
有向图的理论、算法及其应用 电子书 下载 mobi epub pdf txt

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

类似图书 点击查看全场最低价