有向图的理论、算法和应用

第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章 一些重要的专题

参考文献

记号索引

术语索引

译后记

《现代数学译丛》已出版书目

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