欧拉图

来自计算思维百科
跳转至: 导航搜索
欧拉图1.png

一个能够遍历完所有的边而没有重复的图称为欧拉图。这时遍历的路径称为欧拉路径,如果路径闭合,则称为欧拉回路。

基本概念

图论起源于18世纪,1736年瑞士数学家欧拉(Euler)发表了图论的第一篇论文“哥尼斯堡七桥问题”。在当时的哥尼斯堡城有一条横贯全市的普雷格尔河,河中的两个岛与两岸用七座桥连结起来。当时那里的居民热衷于一个难题:有游人怎样不重复地走遍七桥,最后回到出发点。为了解决这个问题,欧拉用A,B,C,D4个字母代替陆地,作为4个顶点,将联结两块陆地的桥用相应的线段表示,于是”哥尼斯堡七桥问题”就变成了图中,是否存在经过每条边一次且仅一次,经过所有的顶点的回路问题了。欧拉在论文中指出,这样的回路是不存在的。

欧拉图2.png

无向连通图G有欧拉路径的充要条件是:图中奇数度(与该点相连的边个数)顶点的数目等于0或者2。

有向连通图D有欧拉回路,当且仅当D的每个顶点的入度等于出度。

应用范围

欧拉图在实际生活中有着广泛的应用,例如路径规划中如何避免重复路径,并且要遍历所有需要路径。

应用案例

应用1-游园问题

案例:

生活中我们会去到大型游乐场游玩,我们知道,大型游乐场通常面积大,游玩项目丰富,在有限的时间内我们常常没有办法全部逛完,而我们最希望尽可能地游玩更多的不同的项目,此时应该要怎么设置路径以达到该目的呢?

解决步骤:

我们可以把游乐场的地图转化成无向图,以游玩项目点为顶点,两地相通则连接两点。然后找出欧拉回路。则欧拉回路即为游玩的最佳路径。假设游乐场项目分布及连通情况如下:

则找出欧拉回路得:

欧拉图3.png

因此,得出最佳游玩路径为1->2->4->3->6->5->3->1;

应用2-牛奶配送问题

案例:牛奶配送往往根据经验,如何能给所有的住户都把牛奶送到,同时不走重复路径,这就是一个欧拉图可以解决的问题。

解决方案:将所有住户的位置作为顶点,住户之间的路径作为点间连接关系,在这张图中可以判断是否存在欧拉回路。

可以体现的计算思维

欧拉图体现了计算思维的抽象思想,把实际问题抽象成图,从而进行操作,可以清晰明了地得到问题的结果。