1、2/3/20231图论模型 瑞士数学家欧拉(E.Euler)在研究哥尼斯堡七桥问题的同时开创了图论研究的先河。经过两百多年的发展，尤其是在20世纪中叶以后，伴随着计算机科学的发展，图论也得到迅速发展和广泛应用，内容及其丰富。这里仅介绍图论中的几个最常见问题，主要目的是通过一些例子来阐述它们的应用价值。2/3/20232 1 城镇道路扫雪模型 邮递员从邮局中取出邮件，递送到不同地点，然后再返回邮局。假设要求他至少一次走过他投递范围内的每一条街道，我们希望选择一条尽可能短的路线。这个问题称为中国邮递员问题，因为它是我国数学家管梅谷首先研究的。在一个网络N=(V,E,W)中，经过它的每条边的链称为欧
2、拉链，经过N中每一边至少一次的闭链称为N的环游，经过N中每一边恰好一次的环游称为欧拉环游。一个图能一笔画就是该图有欧拉环游。显然中国邮递员问题就是在具有非负权的网络中找出一条权最小的环游，这种环游称为最优环游。2/3/20233 若N有欧拉环游，则它的每一条欧拉环游具有相同的权，它也必然是最优环游。对有欧拉环游的网络，我们可以采用弗莱里（Fleury）算法求得N的最优环游。弗莱里算法计算步骤如下：（）任意选取N的一个顶点0，置Z=0。（）假设链Z=v0e1v1eivi已选定，从E e1,e2,ei中按下述方法选取ei+1；ei+1和vi相关联；2/3/20234 ei+1尽量不选Gi（是G中去
3、掉边e1,e2,ei而得到的图）的割边（即去掉此边后，图Gi变为不连通），除非没有非割边可选择。（）设ei+1另一关联点为i+1。若E e1,ei+1 ，重复步骤（2）；否则v1e1v2ei+1vi+1即为N的一条欧拉环游。若网络N没有欧拉环游，此时最优环游通过的某些边将超过一次。例如图1(a)的图中xuywvzwyxuwvxzyx是最优环游，此时四条边ux,xy,yw和wv都被这环游通过二次。2/3/2023512265122423423xvwyzxvyz121236511222(a)(b)图1w2/3/20236 下面是一种有关引进重复边的算法。将边e的两个端点再用一条权为w(e)的新边连
4、接时，称为边e的重复边。例如把上述图(a)中边ux,xy,yw和wv重复，得到图1（b）。因此，中国邮递员问题可以重新叙述如下：给定一个具有非负权的网络N，用添重复边的方法求得N的一个欧拉赋权母图N+，使得 尽可能小；求N+的欧拉环游。E(N)N()(eeW2/3/20237 解可用弗莱里算法；解已有好算法（爱德蒙斯Edmonds和约翰逊Johnson算法），由于这一算法比较复杂，这里就不再介绍了，有兴趣的读者可以参阅有关图论算法的书。当点数较少时，可用奇偶点图上作业法求解，为此我们不加证明介绍下述两个结论。结论结论1网络N有欧拉环游当且仅当N中每一点的次为偶数。结论结论2最优环游具有这样的性
5、质：（1）每条边至多重复一次；（2）每一圈上重复边的长度不超过该圈总长的一半。当某当某一圈上重复边的长度超过该圈总长的一半时，将该2/3/20238 圈中的所有重复边去掉，该圈中未重复的边重复，从而得奇偶点图上作业法如下：（1）若N每一点的次均为偶数，则用弗莱里算法求得其欧拉环游，此即为N的最优环游。（2）若不然，则用添重复边的办法得到N的欧拉赋权母图N*。求得N*的欧拉环游（用弗莱里算法）。（3）若某一条边在欧拉赋权母图N*中重复多次，只要去掉该边的偶数次重复边，总可以使得该边至多重复一次，这样的图仍为欧拉赋权母图。（4）然后逐一检查N*的每一个圈，当某一圈上重复边的长度超过该圈总长的一半时
6、，将该圈中的所有重复边2/3/20239 去掉，该圈中未重复的边重复，所得到的图也是欧拉赋权母图。例例 设某邮递员负责投递邮件的街道如图2（a）所示,求出该邮递员的最短投递路线。解解 该网络有8个奇点:v2、v4、v5、v7、v8、v9、v11、v12，用添重复边的办法得图2(b)。按结论2进行调整,圈v4 v10 v11 v5其总长为12,而重复边长为11,此时去掉重复边v4 v10、v10 v11 、v11 v5 ,添加重复边v4 v5。同样在圈v2 v3 v9 v7 v6 v2中其总长为21，重复边长为12也超过一半。经调整后得到新的网络图2（c）。2/3/202310v2v3v5v6v
7、8v7v9v12v13v2v5v6v8v7v9v11v12v13v2v3v5v6v8v7v9v11v13v1v4v10v1v4v10图图2(a)图图2(b)图图2(c)457444224511252v11v12v101 v4v14v32/3/202311 检查图2(c)的每一个圈,其重复边的长度均不大于该圈长的一半,因此用弗莱里算法求得图2(c)中网络的欧拉环游即为要求的最优环游。下面一个问题是美国1990年数模竞赛B题:图3(a)中的实线表示美国马里兰州威克米尔市需要清除积雪的双向行车道路,虚线是州高速公路。雪后,两辆扫雪车分别从地图*号标出的两点以西约4英里处出发清扫道路上的积雪。扫雪车可
8、以通过高速公路进入市内道路。假定扫雪过程中扫雪车不会损坏或停止,并且道路交叉处不需要另外附加的扫雪程序.试为两车找出有效的路径。应用前面的方法.我们可以解决这个问题。2/3/202312北图图3(a)3 英里*2/3/202313 1问题的分析 我们的目的是寻找一个有效的办法用两台扫雪车清除威克米尔市内道路（不包括州高速公路）的积雪。这个问题的有效解法应该有以下特点：扫完全部路面所花的时间尽量少；扫雪完毕后，两车应尽快回到出发点；两车工作时间大致相同。如果扫雪车没有重复走某一条路，或者扫雪车重复走的路径和最小，我们就认为扫雪所花的时间最少。为使交通尽快畅通，通常应该把所花时间少放在最重要的地位
9、来考虑。当然，有时需要先扫除主要干线上的积雪，再考虑扫清剩下2/3/202314 的道路，此时就要涉及确定哪一些路线是主干线的问题。2模型的假设 对模型作如下假设：扫雪过程中没有下雪，所有市内道路都有积雪需要清除；两辆扫雪车性能相同，都能正常工作；两辆扫雪车司机驾驶技术相同，扫雪时，车速相同；在所有交叉路口，包括市内道路与高速公路的接口，扫雪车可不减速地转弯；两辆车出发的时间相同；2/3/202315 每条路面的积雪范围、厚度相同。3模型的建立（1）双行道问题 假定每条道路均有两条方向相反的行车道。此时，将地图中每个交叉路口（包括市内与高速公路的交叉口）看成点，每条市内道路看成边，它的长度看成
10、该边对应的权，这样我们就得到了网络N=(V,E,W)。由于每条公路均是双行道，这样的网络N是一个欧拉有向图，每点的入次和出次相同。利用弗莱里算法可以求得N的欧拉环游。如果只有一辆扫雪车，这就是中国邮递员问题。现在有两辆扫雪车，为了使工作过程最优，两辆扫雪车应扫过几乎同样长2/3/202316 度的道路。为此，我们将网络N分成两个子网络N和N,使得N和N均连通，且N和N两网络的权尽可能相等。这可以用如下办法实现：把网络N分为两个连通子网络，分别算出两个子网络中所有边的总长度，由于N的总边长已知，在总长较大的子网络中减去一些与另一子网络相连的边，添加到总长较小的子网络中。最后调整的结果如图3（b）
11、所示。如果扫雪车在市内道路交叉路口或市内道路与高速公路交叉处可以掉头，即扫雪车到达城市边缘可以不经高速公路而重新进入市区，则可用上述方法求解。如果忽略扫雪车在高速公路上的行车时间，则可同上述情况一样求解。否则，我们要将高速公路看成上述网络的若干条新边，然后再用上述方法求解。2/3/202317-高速公路*分划处*3 英里*北图3（b）*2/3/202318 （2）单行道问题。近代喷气扫雪车已问世，它靠喷射热气流来清除积雪。因此，这种扫雪车在双行道一边行驶时，就可轻易清除整条路面上的积雪，无需再沿另一边重新行驶。求这种情况的最优解问题称为单行道问题。对这类问题，与双行道问题一样，将它对应一个网络
12、N，并将N分成两个子网络N1和N2，要求N1和N2两个子网络的边总长度相等，这样利用求解中国邮递员问题的算法，可以分别求得N1和N2的欧拉环游，得到要求的近似解。2/3/202319 4、进一步讨论。对双行道与单行道两种情况，都必须对原网络进行分划。为此，对原始途径进行测量，然后用手工或计算机输入一定数量的数据，通过计算机将网络进行分划。如果两辆扫雪车的性能不同，或者两辆车出发的时间不同，只需把整个网络分成相应比例的两部分即可。2/3/202320 上述方案的缺点是手工测量的数据不够精确，且太费时间。在实际情况中，问题更复杂。例如首先应该扫清主干道积雪，以便有个通道，让救护车、公共汽车以及其他各种特殊类型的车辆通过该路段，这就需要考虑如何规定主干道。又如遇到大风时，就要考虑顺风与逆风的车速不同等因素。
