论文部分内容阅读
与中国邮递员问题相比，限制的中国邮递员问题的研究具有更为重要的现实应用意义，在实际生活中有很广阔的应用背景，比如运输系统，网络通信等复杂领域。在该问题中，每个图均为有向图，任意两个点之间至少有一条路，即该有向路是强连通的。本文从研究中国邮递员问题入手，分析并解决了这些问题。
本文简要地介绍了中国邮递员问题的历史由来，数学模型及已有的算法，给出并解决了有向图中有容量限制的中国邮递员问题，有长度限制的中国邮递员问题及带投递时间的中国邮递员问题的算法，证明了这些算法是最优的，并且还对算法的复杂性做出了分析。
本论文包括以下五章：
第一章：简要介绍了中国邮递员问题的背景，理论形成，并给出了目前为止的一些研究成果。
第二章：对文中所出现的定义，概念和符号等给出说明。
第三章：介绍了有向图中有容量限制的中国邮递员问题，利用最小费用流算法建立了一个算法，分析了其时间复杂性。
第四章：介绍了有向图中有长度限制的中国邮递员问题，利用；分方法建立了一个最优算法，分析了其时间复杂性，第五章：介绍了有向图中带投递时间的中国邮递员问题，利用匹配方法建立了一个最优算法，分析了其时间复杂性。
第六章：给出了相关结论及未来研究的方向。