有向图的理论、算法及其应用
点此进入淘宝搜索页搜索分類: 图书,自然科学,数学,代数 数论 组合理论,
作者： （丹）J.邦詹森，（英）G.古廷著，姚兵，张忠辅译
出 版 社： 科学出版社
出版时间： 2009-1-1字数：版次： 1页数： 608印刷时间：开本： 16开印次： 1纸张：I S B N ： 9787030228048包装： 平装编辑推荐
本书概括了有向图的基本知识，并从深层次的角度介绍了理论和算法这两个方面的研究成果及应用。书中的基本内容是针对具有大学数学基础知识的读者，然后在几个研究领域(包括连通性、图的定向、子模流、有向图的路和圈、竞赛图的推广以及有向图的推广等)的主要方向上逐步到达最新的研究成果。本书配备了超过700道练习题、大量应用以及适宜讨论的专题。
内容简介
本书作者从近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章 距离
第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可满足性问题的一个应用。
……
