如何設計處理器之間的一對一通信算法？

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）的邊多邊形。對於每個顏色類，包括從中心到其中一個多邊形頂點的一條邊，以及連接多邊形頂點對的所有垂直邊。