赋权欧拉图 ■ 赋权欧拉图的最优邮递路线是什么？ ■非欧拉图的邮递路线一定重复经过边 ■对于一条邮递路线，其每次重复经过一条边，便将一条权相同 的重边增加到赋权图G中 ·最终形成的赋权图记作G,添加的重边的集合记作EM ●G有什么特征？它的最优邮递路线是什么？ 3 Vg V6 2023/4/10
n 赋权欧拉图的最优邮递路线是什么？ n 非欧拉图的邮递路线一定重复经过边 n 对于一条邮递路线，其每次重复经过一条边，便将一条权相同 的重边增加到赋权图G中 l 最终形成的赋权图记作GE，添加的重边的集合记作EM l GE有什么特征？它的最优邮递路线是什么？ 2023/4/10 26 赋权欧拉图
赋权欧拉图 ■中国邮递员问题可以转化为下述问题 ●如何向赋权图G中添加重边的集合形成赋权欧拉图G乎， 且EM的权和最小？ Vo 2 V6 2023/4/10 27
n 中国邮递员问题可以转化为下述问题 l 如何向赋权图G中添加重边的集合EM形成赋权欧拉图GE， 且EM的权和最小？ 2023/4/10 27 赋权欧拉图
赋权欧拉图 ■中国邮递员问题可以转化为下述问题 ●如何向赋权图G冲添加重边的集合形成赋权欧拉图G, 且M的权和最小？ 存在一条最优邮递路线，其对应的重边的集合是 以赋权图G中所有2k个(k≥0)度为奇数的顶点为起点和终点 的k条无公共边的最短路经过的边的集合 3 V6 2023/4/10
n 中国邮递员问题可以转化为下述问题 l 如何向赋权图G中添加重边的集合EM形成赋权欧拉图GE， 且EM的权和最小？ n 存在一条最优邮递路线，其对应的重边的集合EM是： 以赋权图G中所有2k个（k ≥ 0）度为奇数的顶点为起点和终点 的k条无公共边的最短路经过的边的集合 2023/4/10 28 赋权欧拉图
赋权欧拉图 ■中国邮递员问题可以转化为下述问题 ●如何向赋权图G中添加重边的集合E形成赋权欧拉图G平， 且E的权和最小？ ■存在一条最优邮递路线，其对应的重边的集合是 以赋权图G中所有2k个(k≥0)度为奇数的顶点为起点和终点 的k条无公共边的最短路经过的边的集合 ●关键：2k个顶点如何配对？ Vo 2 V6 2023/4/10 29
n 中国邮递员问题可以转化为下述问题 l 如何向赋权图G中添加重边的集合EM形成赋权欧拉图GE， 且EM的权和最小？ n 存在一条最优邮递路线，其对应的重边的集合EM是： 以赋权图G中所有2k个（k ≥ 0）度为奇数的顶点为起点和终点 的k条无公共边的最短路经过的边的集合 l 关键： 2k个顶点如何配对？ 2023/4/10 29 赋权欧拉图
赋权欧拉图 ■埃德蒙兹-约翰逊算法 ●找出2k个度为奇数的顶点间长度之和最小的k条最短路 ●将其经过的边作为重边增加到图中 ●再找一条欧拉回路 2 2 3 3 2 Vs 2 2 V6 6 2023/4/10
n 埃德蒙兹-约翰逊算法 l 找出2k个度为奇数的顶点间长度之和最小的k条最短路 l 将其经过的边作为重边增加到图中 l 再找一条欧拉回路 2023/4/10 30 赋权欧拉图