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

第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章 一些重要的专题参考文献记号索引术语索引译后记《现代数学译丛》已出版书目