中国邮递员问题是图论中的经典问题，指邮递员从邮局出发遍历所有街道并返回，寻求总路程最短的路径方案。该问题由管梅谷于1960年首次提出，其解法“奇偶点图上作业法”被国际学界命名为中国邮递员问题 。
其数学模型为在非负权连通图中寻找权最小的环游。若图为欧拉图可用弗勒里算法求解；若非欧拉图需添加重复边构造欧拉母图并求最小权 。1973年埃德蒙兹与约翰逊提出有向图的多项式时间算法，而混合路径场景下该问题被证明为NP困难。
该问题起源于管梅谷的研究，后续发展包括1973年有向图解法和1976年混合路径复杂度的证明。其应用领域涵盖道路维护与防疫消毒路径规划 。
想要了解更多“中国邮递员问题”的信息，请点击：中国邮递员问题百科
