第六节 中国邮递员问题       (1) (2) (3)
    ⑴最优方案中，每一条边上最多有一条重复边。
    如果可行方案中，某条边重复边多于一条，则可以成对减去重复边，直至满足该性质。
    ⑵最优方案的图中，每个圈上的重复边权数之和不大于该圈总权数的一半。否则，将该圈上的重复边去掉，给圈上原来没有重复边的边加上重复边，则图中仍无奇点，而且重复边的总权数下降。
    例7 求如下图所示的街路的中国邮递员问题。
        
    解：图中有四个奇点，将它们配对， 为一对， 为一对。沿[，]增加重复边，沿[，]增加重复边，得可行方案如下图所示 。
        
    在圈（）上，重复边权数之和为5，大于该圈总权数8的一半。故按性质⑵调整，将该圈上的重复边去掉，给圈上原来没有重复边的边[，]，[，]加上重复边，调整结果如下图所示 。
        
    检查上图，该方案无奇点，而且满足最优解的性质⑴、⑵，于是上图已是最优方案，重复边总权数为3。
    以上介绍的求最优邮递路线的方法，通常称为奇偶点图上作业法。该方法的困难在于检查图中的每一个圈，当图中点数、边数较大时，圈的个数将会很多。