第八讲 图论概念和一笔画问题
（教材：第八讲 图论概念和一笔画问题）
3．模型的建立
(1)双行道问题
假设：每条道路有两条相反的行车道。
A．可将地图中每个交叉路口看成点，每条市内道路看成边，道路的长度看成该边对应的权，这样就将地图变成一个网络N＝（V,E,W）
B．由假设，每条道路均是双行道，即网络N上的点均为偶点，由上一节的结论1可知，该网络N是一个欧拉有向图，可用弗莱里算法求得N的欧拉环游。
C．若只有一辆扫雪车，该问题转化为中国邮递员问题。
现在有两辆扫雪车，工作性能完全相等，要使工作时间尽量少，我们可将网络N分成两个子网络
和
。
和
均连通，且两网络的权尽可能相同。可用如下方法实现网络的分割：把网络N分成两个连通子网络，分别算出两个子网络中所有边的总长度。由于N的总边长已知，在总长较大的子网络中划出一些与另一子网络相连的边，添加到总长较小的子网络中。
(2)单行道问题
先加对应的网络N分成两个子网络
和
。
要求
和
子网络边总长度相等，再利用中国邮递员问题的解法，可以分别求得
和
的欧拉环游，得到近似解。
4．进一步讨论
(1)不管双行道问题还是单行道问题，都须对原网络进行划分。可测量图中各路径的长度，并将数
据输入计算机，由计算机划分网络。
(2)若两扫雪车性能不同，或出发时间不同等造成两车的差异，可将网络按比例划分。
(3)若首先应该清扫主干道积雪，这就要考虑如何规定主干道。
(4)若遇到大风，就要考虑顺风与逆风时车速不同等因素。