摘要
本文建立多投递员中国邮路问题的几种数学模型,对于右侧通行的情形,给出有效算法,对于一般情形的各种多投递员中国邮路问题,证明它们是NPC的.
Presented in this paper are mathemaical models of many postmen Chinese postmen problems(MPCPP),and the efficient algorithms for the Chinese practice of keeping to the right side of the road,to efficiently solve the MPCPP in the case.For the general case,tnis paper proves different MPCPP ∈NPC.
关键词
欧拉图
NPC问题
邮递员问题
kPCPP
many postmen chinese postman problem
Euler graph
time complexity
NP-Complete problem.