第八讲 图论概念和一笔画问题
（教材：第八 章 图论概念和一笔画问题）
对于一个具有非负权的网络 N， 添重复边的方法：
点数较多时，可用Edmonds和Johnson算法（这一算法较为复杂，这里不作介绍）；
点数较少时，可用奇偶点图上作业法求解。
先给出两个结论：
结论1. 网络N有欧拉环游当且仅当N中每一点的次为偶数。
结论2. 最优环游具有这样的性质：
(1)每条边至多重复一次
(2)每一圈上重复边的长度不超过该圈总长的一半。
从而得奇偶点图上作业法如下:
若 N 的每一点的次均为偶数，则用弗莱里算法求得其欧拉环游，此即 N 的最优环游。
若不然，则用添重复边的办法得到
N 的添加重复边后的的网络 
。求得 的欧拉环游
（用弗莱里算法)，然后逐一检查 的每一个圈，并按结论 2
进行调整，直到满足结论 2 为止。
奇偶点图上作业法口诀：（详见书
）
先分奇偶点，奇点对对连；
连线不重迭，重迭需改变；
圈上连线长，不得过半圈。
〔例 2〕设某邮递员负责投递邮件的街道如图所示，求出该邮递员的最短投递路线。
图3