昨天做题用到了欧拉图,本来刚看到这个名词我是不知道什么是欧拉图的,wiki了一下发现原来欧拉图就是小学奥数做腻了的"一笔画"问题...
图论起源于18世纪,1736年瑞士数学家欧拉(Eular)发表了图论的第一篇论文:哥尼斯堡七桥问题"。
在当时的哥尼斯堡城有一条横贯全市的普雷格尔河,河中的两个岛与两岸用七座桥联结起来,见图(1)。当时那里的居民热衷于一个难题:游人怎样不重复地走遍七桥,最后回到出发点。为了解决这个问题,欧拉用ABCD四个字母代替陆地,作为4个顶点,将联结两块陆地的桥用相应的线段表示,如图(2),于是哥尼斯堡七桥问题就变成了图(2)中,是否存在经过每条边一次且仅一次,经过所有的顶点的回路问题了。欧拉在论文中指出,这样的回路是不存在的。
定义:
欧拉通路 (欧拉迹):通过图中每条边且只通过一次,并且经过每一顶点的通路。
欧拉回路 (欧拉闭迹):通过图中每条边且只通过一次,并且经过每一顶点的回路。
欧拉图:存在欧拉回路的图。
简单说欧拉通路就是首尾不相接,而欧拉回路要求首尾相接。
无向图是否具有欧拉通路或回路的判定:
欧拉通路:图连通;图中只有2个度为奇数的节点(就是欧拉通路的2个端点)
欧拉回路:图连通;图中所有节点度均为偶数
有向图是否具有欧拉通路或回路的判定:
欧拉通路:图连通;除2个端点外其余节点入度=出度;1个端点入度比出度大1;一个端点入度比出度小1
欧拉回路:图连通;所有节点入度=出度
分享到:
相关推荐
欧拉回路C++程序 随机输入任意点数,给出图中存在的欧拉回路
图论——欧拉回路的Fleury算法 根据离散数学教材中思想 实现求欧拉回路。
本算法解决了如何构造一个欧拉图的问题,在构造完欧拉图后如何去寻找一个欧拉回路。
随机生辰欧拉图,通过深度优先遍历来求欧拉回路
图论中的经典问题,构造一个欧拉图,并求它的欧拉回路,
云南大学数学与统计学院《算法图论实验》上机实践报告课程名称:算法图论实验年级:2015级上机实践成绩:指导教师:李建平姓名:刘鹏专业:信息与计算科学上机实践名称
2. 对矩阵表示的无向图,判断其是否存在欧拉通路,并且判断其是否欧拉图。如果是欧拉图,则至少找出一条欧拉回路。
实现的功能为对于给定图的判断是否存在欧拉路径,使用的编程语言为Java,采用邻接表作为图的存储结构,使用并查集判断图的连通性,基于深度优先算法,广度优先算法,佛洛莱算法得到一条有效的欧拉回路以及路径长度,...
14_2. 对矩阵表示的无向图,判断其是否存在欧拉通路,并且判断其是否欧拉图。如果是欧拉图,则至少找出一条欧拉回路。
具有欧拉通路而无欧拉回路的图称为半欧拉图。 对欧拉图的一个现代扩展是蜘蛛图,它向欧拉图增加了可以连接的存在点。 这给予欧拉图析取特征。 欧拉图已经有了合取特征(就是说区定义了有着与起来的那些性质的对象在区...
2010年数据结构课程设计,编译环境是Vissal Studio C++
实验内容: 对具有n个结点的无向图,判断其能否被一笔画。 实验要求: 对给定n个结点的无向图,进行欧拉图和半欧拉图的判定,若是欧拉图或半欧拉图,则输出所有的欧拉(回)路。
3.写一个程序,输入一个图,确定是否是欧拉图,如果是欧拉图,输出欧拉回路。 4.写一个程序,输入一个图,输出每个顶点的度数。 5.写一个程序,输入一个有向图,输出每个顶点的出度和入度。 6.写一个程序,输入一个...
用C语言实现对欧拉图的判定,主要分为两个部分:判断每个顶点的度是否为偶数、判断图是否连通。其中,对图连通性的判定使用了Warshall算法。
代码包括欧拉图的判断,欧拉迹的查找等,代码中有明确的说明。
奇顶点完全图中欧拉回路的设计与实现 能使你对图的概念有更清楚的认识
1.写一个程序,输入一个图,一对顶点和通路长度,输出两个顶点间指定长度的通路数。 2.编程用图的关联矩阵实现结点的合并,并输出合并后...7.写一个程序,输入一个图,确定是否是欧拉图,如果是欧拉图,输出欧拉回路。
Fleury算法是求解欧拉图的十分有效的算法,在执行过程中需要用到类似于图的深度优先遍历,将已找到的路径不断扩展下去,直到所有的路径都扩展完。