W(C)=={W(Ci)|W(Ci)为生成环的Ci的权}
另一种提法是限制货郎每村都次数不限，这在实际问题中更有应用意义。
从算法理论上讲，这两种提法的难度是相当的。下面考虑后一种提法，其难度相当大，其理由有二： (1) 如何判定G是否为哈密顿图，至今尚无有效算法，也不知这种算法是否存在。(2) 已知G是哈密顿图，至今亦无求G的哈密顿环的有效算法，这种算法的存在性问题也未解决。因此，货郎担问题的有效算法的存在问题，是当今图论中面临的一个难题。但可以采用近似法来求解，下面介绍一个较好的近似算法——最邻近方法。
设G=(V，E，W)，｜V｜=n，对V中任意三个结点i，j，k，满足：
w(i，j)+w(j，k)≥w(i，k)
求最小权的哈密顿回路的步骤如下：
任选一点v0作起始点，找一个与v0最近的邻接点v，得到一边构成的路。
1) 设v是新加到这条路中的一点，从不在路中的所有点中，选一个与v最近的邻接点，将它与v连成一边，构成一条新路。
2) 若所有结点均在路中，则连接最后加入的结点与v0，构成一条回路，它就是所求的哈密顿回路，否则转1)。
演化算法是对于求解大规模TSP问题较为有效的近似算法，是一种近年研究较多的模拟达尔文进化理论的算法，读者若有兴趣，请查阅相关文献。
例10.27 时间分配问题
考虑在七天内安排七门课程的考试，要求同一位教师所任教的两门课程考试不安排在接连的两天里，请应用有关图论性质证明：如果教师所担任的课程都不多于四门，则存在满足上述要求的考试安排方案. 解 设G为七个结点的图，每一个结点对应一门功课的考试，如果这两个结点对应的课程的考试是由不同教师担任的，那么这两个结点之间有一条边，因为每个教师所任的课程不超过4，故每个结点的度数至少是3，任两个结点度数的和至少是6，故根据定理10.10，G总包含一条哈密尔顿路，它对应于一个七门考试课目的一个适当安排。
16
第三章 欧拉图和哈密顿图
