运筹学 Operations Research 奇偶点图上作业法:1962年, Kuan M-K 基本思想: 若G是欧拉图,则G含有一条欧拉环游.显然,此欧拉环游即 为唯一最优投递路线; 若G不是欧拉图(包括半欧拉图和非欧拉图),则G不含有 欧拉环游,故可行投递路线中必含有某些重复边,而且这 些重复边显然必仅与G的奇度顶点相关联.为使得投递路线 最优,应设法使这些重复边的权之和最短 在算法上,奇偶点图上作业法要求从某一个可行投递路线 开始,不断修正之,直到满足最优性判断标准,即得最优 投递路线 2021/2/20 122021/2/20 12 运 筹 学 Operations Research 奇偶点图上作业法：1962年，Kuan M-K 基本思想： 若G是欧拉图，则G含有一条欧拉环游.显然，此欧拉环游即 为唯一最优投递路线； 若G不是欧拉图（包括半欧拉图和非欧拉图），则G不含有 欧拉环游，故可行投递路线中必含有某些重复边，而且这 些重复边显然必仅与G的奇度顶点相关联.为使得投递路线 最优，应设法使这些重复边的权之和最短. 在算法上，奇偶点图上作业法要求从某一个可行投递路线 开始，不断修正之，直到满足最优性判断标准，即得最优 投递路线