早教吧 育儿知识 作业答案 考试题库 百科 知识分享

判断是否为欧拉图的并行算法

题目详情
判断是否为欧拉图的并行算法
▼优质解答
答案和解析
欧拉图:一个图为欧拉图,当且公当有一条回路经过图的每一条边且恰好经过一次.
欧拉定理表明:一个图为欧拉图,当且仅当不含有奇度数的顶.
假设图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.判断每个度的数度是否为奇数:
看了 判断是否为欧拉图的并行算法...的网友还看了以下: