最新消息:点击查看大S的省钱秘笈

欧拉图 欧拉回路 欧拉通路

编程相关 Slyar 128浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

昨天做题用到了欧拉图,本来刚看到这个名词我是不知道什么是欧拉图的,wiki了一下发现原来欧拉图就是小学奥数做腻了的"一笔画"问题...

eular

图论起源于18世纪,1736年瑞士数学家欧拉(Eular)发表了图论的第一篇论文:哥尼斯堡七桥问题"。

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

定义:

欧拉通路 (欧拉迹):通过图中每条边且只通过一次,并且经过每一顶点的通路。

欧拉回路 (欧拉闭迹):通过图中每条边且只通过一次,并且经过每一顶点的回路。

欧拉图:存在欧拉回路的图。

简单说欧拉通路就是首尾不相接,而欧拉回路要求首尾相接。

无向图是否具有欧拉通路或回路的判定:

欧拉通路:图连通;图中只有2个度为奇数的节点(就是欧拉通路的2个端点)

欧拉回路:图连通;图中所有节点度均为偶数

有向图是否具有欧拉通路或回路的判定:

欧拉通路:图连通;除2个端点外其余节点入度=出度;1个端点入度比出度大1;一个端点入度比出度小1

欧拉回路:图连通;所有节点入度=出度

转载请注明:Slyar Home » 欧拉图 欧拉回路 欧拉通路

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (2)

  1. 嗯,确实不存在那样的回路。
    莫良8年前 (2009-06-13)回复
  2. 入度 出度 听起来感觉自己很文盲.
    胡普照8年前 (2009-06-12)回复