运筹学 Operations Research 奇偶点图上作业法: 适用性:仅对半欧拉图和非欧拉图G通.图G中必有奇度顶点 步骤: 1确定初始可行投递路线 找出图G的所有奇度顶点,将其一一配对 找出每一对奇度顶点之间的任一条路,将路上各边重复一次,权不变 取新图(已变为欧拉图)中唯一的一条欧拉环游作为初始可行投递路线 转2 2检查图的每条边 若某条边的重复边的条数≥2,则从中去掉偶数条,使得此边至多有一条重复边; 否则,转3. 3检查图的每个图 若每个圈上的重复边的权之和不大于该圆的权的一半(即重复边的权之和不大于未 重复边的权之和),则得最优投递路线; 否则,转4 4投递路线的调整 去掉圈上的重复边,而将未重复边均重复一次 其它圆不变 转2 2021/2/20 172021/2/20 17 运 筹 学 Operations Research