中国邮政员问题

中国邮政员问题CPP（Chinese Postman Problem）

问题描述

给定一个连通图G，每边e有非负权，要求一条回路经过每条边至少一次（环游），且满足总权最小。

问题分析

根据G是否为欧拉图可分为两种情况：
\begin{enumerate}
\item G是欧拉图，则G的任意欧拉回路都是最优解；
\item G不是欧拉图，则G的任意环游必定通过某些边多次，将多次通过的边e(u,v)的两端点再连一条重边，边权为w(e)。则CPP问题等价于：用添加重边的方法求G的一个欧拉赋权母图G^*
\end{enumerate}