第八讲 图论概念和一笔画问题
（教材：第八 章 图论概念和一笔画问题）
四． 实际问题应用举例－ 扫雪问题（教材第104页）
教材第104页上，图8.6（a）中的实线表示美国马里兰州克尔米市需要清除积雪的双向行车道路， 虚线是州高速公路。雪后两辆扫雪车分别从地图*号标出的两点以西约4英里处出发清扫道路上的 积雪。扫雪车可以通过高速公路进入市内道路。假定扫雪过程中扫雪车不会损坏或停止，并且道 路交叉处不需要另外附加的扫雪程序。试为两车找出有效的路径。
1． 问题的分析
完成清除积雪任务的有效解法应具有以下特点：
(1)扫完全部路面所花的时间尽量少。
(2)扫雪完毕后，两车应尽快回到出发点。
(3)两车工作时间大致相同。
对于(1)，我们认为，如果扫雪车没有重复走某一条路，或重复走的路径和最小，则扫雪所花时间少。
在(1)和(2)的情况下，如果只有一辆扫雪车，即可归结为中国邮递员问题。
对于(3)，两车工作时间大致相同，即要求两车走过的路程和大致相同，这也是要求（1）的自然 结论。因此可将该图划为两个子图，使这两个子网络的权尽可能的相等。
2．模型的假设
可作如下的假设：
(1)扫雪过程中没有下雪，所有室内道路都有积雪需要清除。
(2)两辆扫雪车性能相同，都能正常工作。
(3)两辆扫雪车司机驾驶技术相同，扫雪时，车速相同。
(4)在所有交叉路口，包括室内道路与高速公路的接口，扫雪车可不减速地转弯。
(5)两辆车出发的时间相同。
(6)每条路面的积雪范围、厚度相同。