中国邮路问题

中国邮路问题，中国学者于20世纪50年代提出的一种典型的组合优化问题，后在国际上被称为中国邮路问题(Chinese postman problem)。已知图G=(V，E)，对于每条边e∈E，有距离d(e)，从G的某节点出发，走过G的所有边(允许重复穿过)，回到原出发点，使其总行程最短，这个问题是P问题。一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应按怎样的路线走，他所走的路程才会最短呢?如果将这个问题抽象成图论的语言，就是给定一个连通图，连通图的每条边的权值为对应的街道的长度(距离)，要在图中求一回路，使得回路的总权值最小。显然，若图为欧拉图，只要求出图中的一条欧拉回路即可。否则，邮递员要完成任务就得在某些街道上重复走若干次。如果重复走一次，就加一条平行边，于是原来对应的图就变成了多重图。只是要求加进的平行边的总权值最小就行了。于是问题就转化为：在一个有奇度数结点的赋权连通图中，增加一些平行边，使得新图不含奇度数结点，并且增加的边的总权值最小。