邮递员问题 ·数学模型 ·无向带权图G:E中元素对应于辖区内的街道，Vc中的元 素对应于街道的交叉点，街道长度用相应边的权表示。 ·问题的解：G中包含所有边的权最小的回路，称为最优回路 (注意：未必是简单回路)。 ·当G是欧拉图，则最优回路即欧拉回路。 ·若G不是欧拉图，则通过加边来消除G中的奇度顶点，要 求使加边得到的欧拉图G*中重复边的权和最小。邮递员问题 • 数学模型 • 无向带权图G: EG中元素对应于辖区内的街道，VG中的元 素对应于街道的交叉点，街道长度用相应边的权表示。 • 问题的解: G中包含所有边的权最小的回路，称为最优回路 (注意：未必是简单回路)。 • 当G是欧拉图，则最优回路即欧拉回路。 • 若G不是欧拉图，则通过加边来消除G中的奇度顶点，要 求使加边得到的欧拉图G*中重复边的权和最小