如何设计处理器之间的一对一通信算法？

Question

让我给你看一个例子来说明我的问题。我有4个处理器1-4。他们中的任何两个人都必须进行一些交流。因此，为了节省时间，我们可以按如下步骤进行。

时间1:(1,2)(3,4)

时间2:(1,3)(2,4)

时间3:(1,4)(2,3)

所以我们可以看到，对于偶数n，我们可以在n-1次内完成这种通信。但当处理器数量n变得很大时，要找到一种算法来确保每次都没有空闲的处理器并不是一件容易的事情。

如果n等于6，下面不是一个好的选择：

时间1:(1,2)(3,4)(5,6)

时间2:(1,3)(2,4) .(5和6已经相互通信，所以它们在时间2是空闲的)。

尽管我的专业是电磁学，我还是查了很多关于组合学的书。但我还是找不到答案。有没有人能把我引向正确的方向？

Answer 1

这个问题等价于顶点数为偶数的完全图的边着色问题。每个顶点对应于某个“处理器”，每个颜色对应于原始问题的“时间”。

对于这种情况，Wikipedia article on edge coloring提出了一个简单的算法：

将n个点放置在正则(n个−1)-sided多边形的顶点和中心。对于每个颜色类，包括从中心到其中一个多边形顶点的一条边，以及连接成对多边形顶点的所有垂直边。

​

​