第八讲 图论概念和一笔画问题
（教材：第八 章 图论概念和一笔画问题）
弗莱里算法 可求得 N 的最优环游。
计算步骤：
1)任意选取N的一个顶点 
，置 
。
2)假设链 
已选定，从 
中按下述方法选取
:
(1) 
和 
相关联。
(2) 
尽量不选 
（ 是 
中去掉边 
而得到的图）的割边（即去掉此边后，图 
变为不连通），除非没有非割边可选择。
3)设 
另一关联点 
。若 
, 重复步骤2);否则
即为 N 的一条欧拉环游。
〔例 1〕：已知N（图 G）有欧拉环游，求 N 的欧拉环游 。
图 G
三． 中国邮递员问题
问题提出：（中国邮递员问题）
邮递员从邮局中取出邮件，递送到不同地点，然后再返回邮局。假设要求他至少一次走过他投递范围内的每一条街道，我们希望选择一条尽可能短的路线。
中国邮递员问题要求的是在具有非负权的网络中找出一条权最小的环游，即最优环游。
如果网络存在欧拉环游，我们可以按照上面的弗莱里算法求得其欧拉环游。对于一个没有欧拉环游的网络 N，可以通过添重复边的方法使得添加重复边后的网络具有欧拉环游。这里的关键问题是要求所添加重复边的权的和尽可能地小。