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

欧拉图：

一个图为欧拉图，当且公当有一条回路经过图的每一条边且恰好经过一次。

欧拉定理表明：一个图为欧拉图，当且仅当不含有奇度数的顶。

假设图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)). 这一个理论值，当然在实际过程中并不可能达到，但是确实给我们提供了一很好问题解决方法。