10-4中国邮递员问题一、一笔画问题定义（欧拉链）给定一.ppt

* 10-4 中国邮递员问题 一、一笔画问题 定义（欧拉链） 给定一个多重连通图G，若存在一条链，通过每边一次且仅一次，则称为这个链为欧拉链。 定义（欧拉圈） 给定一个多重连通图G，若存在一条圈，通过每边一次且仅一次，则称为这个圈为欧拉圈。 定义（欧拉图） 含有一条欧拉圈的图，称为欧拉图。 定理10-4 多重连通图G是欧拉图，当且仅当G中无奇顶点。 推论 多重连通图G有欧拉链的充分必要条件是G恰有两个奇顶点。 v1 v4 v3 v2 顶点的度d（v1）=4， d（v2）=2， d（v3）=4， d（v4）=2 全为偶数 v1 v4 v3 v2 是欧拉图，存在欧拉圈，可从任一点出发。 v1 v4 v3 v2 v1 v4 v3 v2 v1 v4 v3 v2 v1 v4 v3 v2 v1 v4 v3 v2 v1 v4 v3 v2 顶点的度d（v1）=3， d（v2）=2， d（v3）=3， d（v4）=2 两个奇顶点 v1 v4 v3 v2 存在欧拉链，且从其中一个奇顶点开始，结束在另一个奇顶点。 v1 v4 v3 v2 v1 v4 v3 v2 v1 v4 v3 v2 v1 v4 v3 v2 存在欧拉链，且从其中一个奇顶点开始，结束在另一个奇顶点。 中国邮递员问题：一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应如何选择行走路线，才能使所走的路线最短？ 如果街区图中没有奇顶点，则是一个欧拉图。如果有奇顶点，则某些边必定重复走一次或多次。我们要求重复走过边的总长最小。 奇偶点作业法步骤： 1 确定第一个可行方案。找到图中所有奇顶点（必有偶数点）将它们两两配对。新图中无奇顶点，得到第一个可行方案。 2 调整可行方案，使重复边总长度下降。 3 检查图中的每个圈，如果每个圈重复边总长度不超过该圈总长度的一半，则已求得最优解。否则进行调整：将这个圈的重复边去了，而将原来没有重复边的各边加上重复边，其他各圈的边不变，根据 2 再一次调整。 例10-13 设有街道图，各边均标出了街道的长（权）。假定邮递员从v1点出发，求他的最优投递路线。 v9 v1 v8 v7 v6 v5 v4 v3 v2 4 3 4 3 4 4 4 9 6 5 5 2 *