欧拉回路避桥法的扩展：遍历无向图里的所有边，当这个图不是欧拉回路时，怎样使得走过的重复边最少？

Question

遍历所有点的问题是tsp问题，但是如果需要遍历所有的边呢？


欧拉回路的避桥法可以对于欧拉回路，实现不重复的遍历所有边，
但是如果该图不是欧拉回路，该怎样在最短行驶路径下遍历所有边呢？

问题：

给定一个无向连通图，不是欧拉图，需要遍历其中所有**边**，

可以重复走边，问：怎样使得走过的重复路径最少？



做课设需要解决这个问题，有相关的算法吗，


如果没有，该怎样修改对于欧拉回路的避桥法呢？

Answer 1

这个叫做 中国邮递员问题，你可以google下
https://www.cnblogs.com/WABoss/p/5140531.html