算法分析(解决问國的方法):图论,分而治 若G为欧拉图,最优投递路线就是从指定 顶点出发的一条欧拉回路。 若G不是欧拉图,则最优投递路线必须要 有重复边出现,而要求重复边权之和达到最小。 G必有奇顶点,为了消除奇顶点,必须加若 干条重复边,使得重复边的权与原边的权相同 设所得图为G*,则最优投递路线等价于求G*的 条欧拉回路,使得重复边权之和0(e)最小, 其中F=E(G*)-E(G)
3）算法分析（解决问题的方法）：图论，分而治 之 若G为欧拉图，最优投递路线就是从指定 顶点出发的一条欧拉回路。 若G不是欧拉图，则最优投递路线必须要 有重复边出现，而要求重复边权之和达到最小。 G必有奇顶点，为了消除奇顶点，必须加若 干条重复边，使得重复边的权与原边的权相同， 设所得图为G*，则最优投递路线等价于求G*的 一条欧拉回路，使得重复边权之和 最小， 其中F=E(G*)-E(G)。 ( ) e F e
4)G不是欧拉图的最优投递路线算法 当G中只有两个奇顶点u,p时,可先 用标号法求出从u到ν的最短路,然后将 最短路上的边连其权各重复一次,得欧 拉图,再走一条欧拉回路,就是G中的 条最优投递路线
4） G不是欧拉图的最优投递路线算法 当G中只有两个奇顶点u, v时，可先 用标号法求出从u到v的最短路，然后将 最短路上的边连其权各重复一次，得欧 拉图，再走一条欧拉回路，就是G中的一 条最优投递路线
5)理论基础 定理1 C是带权无向连通图G=VE,O中 的最优投递路线当且仅当对应的欧拉图 G*应满足: (1)G的每条边在G*中至多重复出现一次; (2)G的每个圈在G*中重复出现的边的权 之和不超过该圈权的一半
5）理论基础 定理 1 ： C是带权无向连通图G=(V, E, ) 中 的最优投递路线当且仅当对应的欧拉图 G*应满足： (1) G的每条边在G*中至多重复出现一次； (2) G的每个圈在G*中重复出现的边的权 之和不超过该圈权的一半
证明:必要性 ■(1)设C是最优投递路线,即C是G*中的欧拉 回路,满足∑w(e)最小,F=E(G*)-E(G)。设G中 边e在G*中重复度为m(e),即在G中的e的两个 端点u,ν之间添加了me)-1条重复边,若m(e)>3, 在G*中,ν之间的边中随便删除两条,不改变u, v度数的奇偶性,因而所得图G*仍为欧拉图 由于G中各边的权均为正,因而W(F2)<W(F少, 其中F2=E(G*)-EG,而F1=E(G*)-E(G,这 与C是最优投递路线矛盾
证明：必要性 （ 1）设 C是最优投递路线，即 C 是G*中的欧拉 回路，满足 w(e)最小，F=E(G*)-E(G)。设 G 中 边 e 在G*中重复度为m(e)，即在 G中的 e的两个 端点u, v之间添加了m(e)-1条重复边，若m(e) 3 ， 在G* 中u, v之间的边中随便删除两条，不改变u, v度数的奇偶性，因而所得图G**仍为欧拉图， 由于 G中各边的权均为正，因而W(F2)<W(F1) ， 其中 F2=E(G**)-E(G)，而 F1=E(G*)-E(G)，这 与 C是最优投递路线矛盾
定理2: 设带权无向连通图G=(V,E,W,V 为G中奇度顶点集,设|=2k休≌0), F={ele∈E∧在求G的最优回路时加了 重复边},则F的导出子图G[F可以表示 为以V中顶点为起点与终点的k条不交的 最短路径之并
定理 2 ： 设带权无向连通图G=(V, E, W) ，V’ 为 G中奇度顶点集，设|V’|=2k (k0) ， F={ e | e E 在求 G的最优回路时加了 重复边 }，则 F的导出子图 G [ F]可以表示 为以V’中顶点为起点与终点的 k条不交的 最短路径之并