1、前言图论是研究离散对象二元关系系统中关系结构的一个数学分支，近几十年来十分活跃，它与拓扑，代数，组合数学等学科关系密切.网络最优化是运筹学中重要的组成部分，它有着深刻的实际背景和广泛的应用.本书的主要目的是介绍几种常用的网络最优化方法.由于图论是网络最优化的理论基础，故介绍最优化方法必须首先介绍有关的图论的基本概念和理论.为此，本书第一章首先介绍了图论的一些基本概念，在第二章至第六章分别介绍最小树，最短路，最优分派问题，中国邮递员问题和旅行售货员问题，网络流问题时，首先介绍有关的图论基础，掌握它们，可以帮助我们理解、掌握和应用这些方法.考虑到平面图理论在电子技术中有着广泛应用，在第七章介绍了平
2、面图的基本理论和平面性算法.本书第八章介绍了几个应用实例，读者可以从中得到一些利用网绍最优化方法解决实际问题的技巧，本书是在原同名讲义的基础上，根据多次教学实践重新整理而成的，它亦包含了一些基本而重要的研究成果.例如，优化劳动组合的数学模型，Hamilton图的充分条件和车辆调度问题的启发式算法等，任何一本书，很大一部分应归功于早期的研究者和著作者，这里特别要提到的是田丰和马仲蕃，刘家壮和王建方及Bondy和Murty的著作本书的出版得到许多人的支持和帮助，在此表示衷心的感谢.特别是山东大学谢力同和刘家壮先生，是他们引导我去研究图论；南京大学张克民先生，他仔细阅读了手稿，并提出了许多有价值的建议.宋增民1990年6月于南京2
