网页设计和网站建设的区别,研发一款app要多少钱,怎么设计自己logo,免费发广告的软件什么是欧拉图
提到欧拉图就要谈到哥尼斯堡七桥问题#xff0c;最初有这样的一个问题的#xff1a;18世纪中叶#xff0c;东普鲁士哥尼斯堡城有一条贯穿全城的普雷格尔河#xff0c;河中有两个岛#xff0c;通过七座桥彼此相连#xff0c;如下图所示
问题是这样的…什么是欧拉图
提到欧拉图就要谈到哥尼斯堡七桥问题最初有这样的一个问题的18世纪中叶东普鲁士哥尼斯堡城有一条贯穿全城的普雷格尔河河中有两个岛通过七座桥彼此相连如下图所示
问题是这样的有人从四块陆地中的任意一块出发按什么样的路线能做到每座桥只通过一次而最后返回原地。 我们可以将整个问题抽象成下面的图进行解答
如果我们将每个节点与其他边数查出来即数出每个节点的度数这样就有下面的列表
名称度数陆地13陆地23岛14岛23
对于一个结点来说每出一次节点代表与结点相连的某一条边已经走过了即结点度数减1与其相连的结点的度数也减1如果上述哥尼斯堡有解的话就应该存在这样一条回路从某个地点出发最后回到某个地点。 每走过一条边会导致这条边的两个端点的度数减1如下图所示
名称度数陆地13-12陆地23岛14-13岛23
也就是说如果能够不重复的走过所有的桥最后各个结点的度数一定为0.即
名称最终不断计算度数变化陆地10陆地20岛10岛20
如果七桥问题有解由于最终是回到起点所以走的路径一定是回路
假设在七桥问题中存在这样一条回路先考虑回路除起点终点外的其他结点那么进入某个结点之后应该能够出来也就是每经过一个结点会造成结点的度数减2 也就是说非起点终点结点的度数一定得是偶数才能经过不断的减2、减2最终变成0
起点终点在最初的时候出了一次度数减去1在最终的时候回了一次度数减去1这样就减去了2
经过分析起点终点结点的度数一定得是偶数才能经过不断的减2、减2最终变成0。 也就是说必须在所有结点的度数均为偶数的情况下才能找到一条回路经过一次所有边且只经过一次。
欧拉在解决了哥尼斯堡七桥问题之后提出并解决了一个更加一般性的问题在什么样的图中能够找到通过图中每条边一次且仅一次的回路 我们将能够在图中找到通过图中每条边一次且仅一次的通路注意没有说回路的图称为欧拉图。这样的通路叫做欧拉通路。具有欧拉通路的图叫欧拉图。
如何确定欧拉图
上边已经确定分析了具有欧拉回路的情况因为是回路所以其中所有的结点的度数都是偶数。 那么不是回路但是通过所有的边一次且仅以此的通路会让我们得出什么样的结论呢 非起点或终点的结点即路径中间的经过的结点我们可以通过如下图的分析得到
中间的结点仍然是减去2
也就是说在欧拉通路不是回路的情况下只有两个结点的度数为奇数其余结点的度数均为偶数。 结合欧拉通路是回路的情况也就是说一个图要是欧拉图要么所有结点的度数均为偶数要么其中两个结点的度数为奇数其余结点的度数为偶数即奇度数结点的个数为0或2.注奇度数结点为2的是半欧拉图。图必须是连通的不连通一定不是欧拉图。
欧拉图的应用
欧拉图可以用来解决一笔画问题、蚂蚁比赛问题、计算机鼓轮设计、中国邮路问题这些问题在以后有时间了在进行讨论。 如果有什么地方讲的不好或者讲错的地方欢迎大家指出来如果我所讲的对你们有帮助不要忘了点赞、收藏、关注哦 我是你们的好伙伴apprentice_eye 一个致力于让知识变的易懂的博主。
