论文部分内容阅读
研究了混合图上两类中国邮递员问题的推广问题--混合图上有容量限制的中国邮递员问题和混合图上有长度限制的中国邮递员问题，它们是中国邮递员问题的推广形式.该论文主要研究下面两种问题：
在混合图上中，考虑邮递员经过街道的次数不超过其容量限制，而且必须经过给定街道至少一次，提出了有容量限制的中国邮递员问题.
如果在混合图中考虑邮递员走遍给定的街道的总路程不超过某个固定的常数L，在这种情况下，要求邮递员经过次数最多的那条边的次数尽可能的小，那么就得到了混合图上有长度限制的中国邮递员问题.
这两个问题是经典中国邮递员问题的两种推广.本文主要研究了这两个问题的两种模式，即当给定的边子集和弧子集是否为空集时的设计出了相应的算法，分析了算法复杂性.
该论文包括以下四章：
第一章：回顾了问题的由来，给出了最近的一些相关研究成果.
第二章：给出了文中所出现的定义、概念和符号。
第三章：讨论了混合图上有容量限制的中国邮递员问题，当给定子集构成的诱导子图为连通时，研究两种模型，并设计相应算法。
第四章：讨论了混合图上有长度限制的中国邮递员问题，当给定子集构成的诱导子图为连通时，研究两种模型，并设计相应算法。
最后，给出了相关结论以及未来的研究方向。