本书系统介绍了网络优化的基本模型和基本算法,包括构造这些算法的基本思想以及相应算法在计算机上的一些具体实现技巧和复杂性分析。
全书由7章组成: 第1章为概论,第2章介绍关于算法的一些基本知识,第3章到第7章分别讨论树的问题、*短路问题、*大流问题、*小费用流问题和匹配问题.每章还安排了一些练习题。
本书可作为数学、应用数学、运筹学、管理科学、系统科学、信息科学、计算机科学与工程等专业的高年级大学生和研究生教材,也可供其他相关专业的学者和技术人员参考。

序言
前言
第1章 概论
1.1 网络优化问题的例子
1.2 图与网络
1.3 图与网络的数据结构
1.4 计算复杂性的概念
练习题
第2章 算法基础
2.1 NP,NPC和NP-hard概念
2.2 算法设计与分析
2.3 小结
练习题
第3章 *小树与*小树形图
3.1 树的基本概念
3.2 *小树算法
3.3 *小树形图
3.4 *大分枝
练习题
第4章 *短路问题
4.1 *短路问题的数学描述
4.2 无圈网络与正费用网络:标号设定算法
4.3 一般费用网络:标号修正算法
练习题
第5章 *大流问题
5.1 *大流问题的数学描述
5.2 增广路算法
5.3 *短增广路算法
5.4 一般的预流推进算法
5.5 *高标号预流推进算法
5.6 单位容量网络上的*大流算法
练习题
第6章 *小费用流问题
6.1 *小费用流问题的数学描述
6.2 消圈算法与*小费用路算法
6.3 原始-对偶算法
6.4 瑕疵算法
6.5 松弛算法
6.6 网络单纯形算法
练习题
第7章 匹配问题
7.1 匹配问题的数学描述
7.2 二部基数匹配问题
7.3 非二部基数匹配问题
7.4 二部赋权匹配问题
7.5 非二部赋权匹配问题
练习题
索引及英文关键词
参考文献

第1章 概论
我们生活在一个网络社会中。从某种意义上说,现代社会是一个由计算机信息网络、电话通信网络、运输服务网络、能源和物质分派网络等各种网络所组成的复杂的网络系统。网络优化就是研究如何有效地计划、管理和控制这个网络系统,使之发挥*大的社会和经济效益。
网络优化是运筹学(Operations Research)中的一个经典和重要的分支,所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。本书中将要讨论的*短路问题、*大流问题、*小费用流问题和匹配问题等都是网络优化的基本问题。
本章主要介绍网络优化问题的一些实际例子以及图与网络的基本概念,初步介绍计算复杂性理论,为后续章节的学习奠定基础。
1.1 网络优化问题的例子
我们首先通过一些例子来了解网络优化问题。
例1.1 公路连接问题
某地区有若干个主要城市,现准备修建高速公路把这些城市连接起来,使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本,那么应如何决定在哪些城市间修建高速公路,使得总成本*小?