欧拉图:
一个图为欧拉图,当且公当有一条回路经过图的每一条边且恰好经过一次。
欧拉定理表明:一个图为欧拉图,当且仅当不含有奇度数的顶。
假设图G大小为M * N和邻接矩阵A。 判断一个图是否为欧拉图,很容易在O(M*N)的时间内完成。
为了说明方便,下面设M = N
下面给出复杂度为O(Log(N)) 并行算法,注意这里只给出理论上可行的算法。
1. 计算每个点的度数:求一个点的度,也就是求邻接矩阵中一行的和。因此可以使用O(N)个处理器在O(Log(N))的时间内求出。
因些N个并行求度数,需要N * N个处理器,在O(Log(N))的时间内完成。存于数组da[]中
2. 判断每个度的数度是否为奇数:
可以使用N处理器在O(1)的时间内求出,在于pa[] 中(1 or 0). 如果为奇则为1,否则为0
3.判断是否为欧拉图:
从第2步可以得出每个点的度数是否为奇数。 这也类似于对N个数求和,因此可以使用O(N)个处理器在O(Log(N))的时间内完成。
4. 如果第3步求出的和大于1, 说明不是欧拉图。
因此总的时间复杂度为O(Log(N)). 这一个理论值,当然在实际过程中并不可能达到,但是确实给我们提供了一很好问题解决方法。
分享到:
相关推荐
欧拉图的构造算法 欧拉图的构造 构造欧拉图算法
用C语言实现对欧拉图的判定,主要分为两个部分:判断每个顶点的度是否为偶数、判断图是否连通。其中,对图连通性的判定使用了Warshall算法。
C#,图论与图算法,用于检查给定图是否为欧拉图(Eulerian Graph)的算法与源程序 欧拉图是指通过图(无向图或有向图)中所有边且每边仅通过一次通路, 相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图(Euler ...
离散数学上机作业:用C或者C++实现欧拉图算法
图论——欧拉回路的Fleury算法 根据离散数学教材中思想 实现求欧拉回路。
14_2. 对矩阵表示的无向图,判断其是否存在欧拉通路,并且判断其是否欧拉图。如果是欧拉图,则至少找出一条欧拉回路。
欧拉超路算法
哈密顿图和欧拉图的判断毕业设计源代码 虽然很简单,但是没有认真学习过要编程实现的话还是挺麻烦的
本算法解决了如何构造一个欧拉图的问题,在构造完欧拉图后如何去寻找一个欧拉回路。
1. 了解欧拉图的来历、定义以及图论表述 2. 能快速写出求最短路的最小插点问题的动态规划算法 1. 写出判定一个给定的图是否是欧拉图的算法 2. 写出寻找含有
运用点回路与变回路的方法来判断哈密顿图与欧拉图。推荐
这里运用C++程序采用FLEURY算法,程序计算欧拉环游,很简单
里面有四个代码,分别是真值表的判断,并交差集、判断二元关系、判断欧拉图;每个代码的具体功能实现是分开方法写的,读者可以快速知道某个功能的具体实现方式
提出了2种赋予任意一个图均衡方向的方法:欧拉图构造法和圈树分解法,第一种方法是欧拉图构造法:若给定的图是欧拉图,先找到欧拉环游后再顺着欧拉环游的方向给边赋予方向,若不是欧拉图,可以通过给此非欧拉图补充边得到...
实验内容: 对具有n个结点的无向图,判断其能否被一笔画。 实验要求: 对给定n个结点的无向图,进行欧拉图和半欧拉图的判定,若是欧拉图或半欧拉图,则输出所有的欧拉(回)路。
图论及其算法-2欧拉图与哈密尔顿图.ppt
本代码是一个关于欧拉图的随机生成,欧拉图判定,欧拉图遍历的一个可视化的小软件。可以用来进行简单的欧拉图研究。该代码运用MFC和常用算法,来实现所求功能。本代码可用于教学、科学研究、基础代码应用等。
欧拉图与相关专题 出版时间:2012年版 内容简介 《现代数学译丛(21):欧拉图与相关专题》是迄今为止唯一的一本全面阐述欧拉图理论的主要研究成果和研究方法及其与其他图论问题之间的联系的专著。本书包含两卷共...
逻辑学欧拉图试题(卷)与答案解析.doc