操作说明:
试着用绳子连接驻点,使每条线只覆盖一次,形成底板中的图案。
产品简介:
当一个联通图形中的奇点(与奇数条边相连的点)个数为 0 或 2 时,可以一笔画成,即可以用绳子绕成地板中的图案。 经过每一条边恰好一次的环游称为欧拉环游,一个图若包含欧拉环游,则称为欧拉图。与每个顶点连接的线的个数称为度数。欧拉证明:一个非空连通图是欧拉图当且仅当它的每个顶点的度数都是偶数。
从 A 点出发,沿着 f-g-h-i-j-k1-m-n-p-q-r 这个路径就可以将绳子不重复地覆盖每条线一次并且形成了底板中的图案。
补充材料:
欧拉图是指通过图(无向图或有向图)中所有边且每边仅通过一次通路,相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图(Euler Graph),具有欧拉通路而无欧拉回路的图称为半欧拉图。对欧拉图的一个现代扩展是蜘蛛图,它向欧拉图增加了可以连接的存在点。这给予欧拉图析取特征。欧拉图已经有了合取特征(就是说区定义了有着与起来的那些性质的对象在区中的存在)。所以蜘蛛图允许使用欧拉图建模逻辑或的条件。
图论起源于18世纪,1736年瑞士数学家欧拉(Euler)发表了图论的第一篇论文“哥尼斯堡七桥问题”。在当时的哥尼斯堡城有一条横贯全市的普雷格尔河,河中的两个岛与两岸用七座桥连结起来。当时那里的居民热衷于一个难题:有游人怎样不重复地走遍七桥,最后回到出发点。
为了解决这个问题,欧拉用 A,B,C,D 4个字母代替陆地,作为 4 个顶点,将联结两块陆地的桥用相应的线段表示,于是哥尼斯堡七桥问题就变成了图中,是否存在经过每条边一次且仅一次,经过所有的顶点的回路问题了。欧拉在论文中指出,这样的回路是不存在的。
弗勒里(B.H.Fleury) 在1883 年给出了在欧拉图中找出一个欧拉环游的多项式时间算法,称为弗勒里算法(Fleury’salgorithm)。这个算法具体表述如下:
输入:一个连通偶图 G 和 G 中任意一个指定项点 u
输出:从 u 出发的 G 的一个欧拉环游
1、令 W:=u,x:=u,F:=G
2、while
3、选一条
中的边 e,其中 e 不是 F 的一条割边;如果
中的边都是割边,那么任选一条边 e
4、用
替换
,用 y 替换 x ,用
替换 F
5、end while
6、返回 W
其算法核心就是沿着一条迹往下寻找,先选择非割边,除非这个点的邻边都是割边。这样得到一条新的迹,然后再继续往下寻找,直到把所有边找完。遵循这样一个原则就可以找出图的一个欧拉环游来。
在有向图中也可以类似地定义有向环游、有向欧拉环游、有向欧拉图和有向欧拉迹的概念。
类似地,有如下定理:一个有向图是有向欧拉图当且仅当这个图中每个顶点的出度和入度相等。