论文部分内容阅读
分层中国邮递员问题具有重要的现实意义，具有广阔的应用背景。本论文研究了中国邮递员路问题，即在图中寻找从固定顶点到固定顶点的一条经过图中所有边的最短路，设计了解决此问题的一个最优的多项式时间算法，其时间复杂性为O（n3）。进一步，本文研究无向图上的分层中国邮递员问题，每一层都是一个边的优先集（边划分），每个优先集都是连通的无向图，优先集与优先集之间是有路相连。在这种情况下，要求邮递员从一初始点出发，依次经过各优先集的边，然后回到初始点，形成了一条欧拉回路。本论文设计了最优的多项式时间算法来解决分层中国邮递员问题，其时间复杂性为O（kn5），利用Matlab实现算法。