本书全面系统地介绍了网络优化中的基本问题和基本算法以及计算复杂性的基本内容和近似算法。取材恰当，叙述清晰，论证严谨，深入浅出。
　　全书共十二章，分为两部分：第一部分包括前十章，主要介绍小树，大匹配，大权匹配和中国邮递员问题等基本问题的各种多项式算法，以及线性规划、整数线性规划的基本理论；第二部分包括后两章，讨论计算复杂性中的基本概念，NP完全理论及重要的NP完全问题，还介绍了装箱问题，平行机排序问题，旅行商问题，背包问题等NP难问题的近似算法。
　　本书可作为运筹学专业研究生教材，也可供应用数学、系统科学、管理科学、计算机科学和军事运筹学等有关专业的教师、研究生和大学高年级学生参考。

《运筹与管理科学丛书》序
前言

第1章 图与算法
1．1 图的基本概念
1．2 有向图的基本概念
1．3 几类重要的图
1．4 图与网络的表示形式
1．5 网络最优化问题
1．6 算法及其复杂性
1．7 排序算法
习题1

第2章 最小树
2．1 树的基本性质
2．2 最小树的基本性质
2．3 求最小树的算法
2．4 最小度限制树
2．5 支撑树的排序．
2．6 过指定顶点的最小单圈子图
习题2

第3章 最小树形图
3．1 有根图
3．2 树形图
3．3 求最小树形图的朱刘算法
3．4 分枝
习题3

第4章 线性规划
4．1 线性规划问题及其对偶规划问题
4．2 整数线性规划与全单位模矩阵
4．3 关联矩阵的一些性质
4．4 网络最优化问题的线性规划模型
习题4

第5章 最短路
5．1 引言
5．2 最短路方程
5．3 无回路网络中最短路的拓扑排序法
5．4 非负权网络中最短路的Dijkstra算法
5．5 解最短路问题的Ford算法
5．6 求所有顶点之间最短路的Floyd算法
5．7 回路的检测
5．8 第2最短路
5．9 最短路算法的应用
习题5

第6章 最大流
6．1 流与截
6．2 Ford Fulkerson算法
6．3 最短增广链算法
6．4 预流推进算法
6．5 双容量网络流
习题6

第7章 最小费用流
7．1 负费用回路算法
7．2 最小费用路算法
7．3 原始对偶算法
7．4 最小平均费用回路算法
7．5 求最小费用循环流的状态算法
7．6 最小凸费用流和最小凹费用流
习题7

第8章 二部图的匹配
8．1 图的匹配
8．2 求二部图中最大匹配的算法
8．3 求赋权二部图中最大权匹配的算法
8．4 最大最小匹配
习题8

第9章 一般图的匹配
9．1 交错树
9．2 求最大匹配的花算法
9．3 求最大权匹配的原始对偶算法
习题9

第10章 中国邮递员问题
10．1 Euler闭迹
10．2 有向Euler闭迹
10．3 赋权图上的邮递员问题
10．4 赋权有向图上的邮递员问题
10．5 赋权混合图上的邮递员问题
习题10

第11章 NP完全理论
11．1 最优化问题的判定形式
11．2 P类与NP类
11．3 NP完全类与c00k定理
11．4 Co-NP类
11．5 六个基本的NP完全问题
11．6 NP完全性证明技术
11．7 更多的NP完全问题
11．8 NP难问题
习题11

第12章 近似算法
12．1 近似算法的性能
12．2 装箱问题
12．3 平行机排序问题
12．4 旅行商问题
12．5 背包问题
12．6 一些否定结果
习题12
参考文献
索引
《运筹与管理科学丛书》已出版书目

　　网络是指由若干对象及其相互关系构成的一个系统。从数学上讲，网络是由若干个点及其点之间的带箭头连线表示的一个有向图，并且常常都赋以权。现代社会在很大程度上是一个由信息网络、通信网络、运输网络、能源和物资分配网络构成的巨大的复杂系统。网络最优化则是综合运用图论、线性规划和算法理论来解决图和网络上的最优化问题，因此它能为人们更有效地设计、控制和管理复杂的社会网络系统提供一套科学的方法。
　　由于其视角的独特性、模型的直观性、内容的趣味性和方法的技巧性，以及计算机科学和信息科学的有力推动，网络最优化业已成长为运筹学中引入入胜、富有挑战、充满活力的一个分支，它的理论和方法广泛地渗透于运筹学、信息论、控制论、管理科学和计算机科学等领域，并在工程技术、经济、军事等诸多方面都有着极为重要的应用。
　　随着大规模网络最优化问题的产生，寻找有效最优算法便成为网络最优化的重点，由于许多问题都难以找到有效最优算法，计算复杂性和近似算法的研究已成为网络最优化的热点，本书的编写正是兼顾以上重点和热点，力求突出三大特色：
　　一是化繁为简，激发学习热情。从实际应用问题引入网络最优化模型，直观、自然地建立基本概念，用通俗而又严谨的语言来描述基本理论和基本方法。
　　二是夯实基础，拓宽创新视野。将传统知识与现代技术进行有机融合，以经典内容为主，注重基础性和完备性，介绍学科的前沿研究成果。
　　三是注重应用，培养研究能力。从图论和线性规划两个不同的角度讨论网络最优化问题，介绍算法设计技巧和复杂性分析方法，强调模型、算法与计算复杂性的紧密结合，使读者能清楚地了解各种网络最优化问题之间的关系以及研究方法的本质。
　　本书根据作者2003年在国防科技大学出版社出版的《网络算法与复杂性理论》（第2版）修订而成，它全面地介绍了网络最优化的基本问题和基本方法，计算复杂性理论的基本概念和一些常见的NP完全问题及其近似算法。全书共十二章，分为两部分，第一部分包括前十章，主要介绍网络最优化的概念、模型和算法，并始终强调算法复杂性分析，第二部分包括后两章，介绍NP完全理论和近似算法。每章最后都配置一定数量的习题，其中一些难度较大的作为对正文内容的补充。
　　阅读本书只需具备线性规划的基本知识。