文档介绍：洒水车问题
——理论解决实际问题的例子
指导老师: 窦霁虹
报告人: 林小围
黄志华
张宁辉
一、问题提出
西北大学的洒水车要给主要路面洒水,该如何确定行车路线?
二、问题分析
我们首先根据西北大学的实际情况确定需要洒水的路段。从网址[1]处得到校园的平面图,并进行的细化,绘制出在尺度上大致准确的示意图(图 1)。
[1]
洒水车要给主要路面洒水,也就意味着行车路线必需经过图示所有的路面至少一次。这类似于图论中一个典型的问题:中国邮路问题[2]。中国邮路问题说的是:一个邮递员从邮局出发,到所辖街道投递邮件,最后返回邮局,如果他必须走遍所辖的每条街道至少一次,那么该如何选择投递路线,使所走的路程最短。
[2] 肖位枢,图论及其算法,航空工业出版社,1993
三、假设与符号约定
假设:
(1)洒水车行驶过一次即能满足路面的洒水要求;
(2)洒水车一次加水,即有足够水量给图示所有路面洒水,或者用完水后能在可以忽略路程内加水;
符号约定:
:图的第个节点;
:图中连接第个顶点与第个节点的边;
:边上的权;
:以为节点集,以
为边集的图;
:以为起点为终点的路;
:图的第个节点的度数;
:图的一个附加边子集;
:边集的总权;
:经过边的次数;
:最短路矩阵
四、一些基本概念、算法和定理
欧拉回路:设G(V,E)为一个图,若存在一条回路,使它经过图中的每条边且只经过一次又回到起始节点,就称这种回路为欧拉回路,并称图G为欧拉图。
节点的度数:连接节点的边数为此节点的度数。当为奇数时,称为奇节点;否则,称为偶节点。
附加边子集:将图的奇节点配对,每对节点之间在图中有相应的最短路,连接这些最短路即构成一个附加边子集。
佛罗莱算法(Fleury Algorithm):
Step 1:任取起始节点,取连接这起始节点的任一边为初始路,即;
Step 2:设路已经选出,则从中选出边,使与相连,除非没有其他选择。不应为
的断边,即仍为连通图;
Step 3:重复Step 2直到不能进行下去为止。