从图中创建“配对”？

Question

这个问题似乎应该有一个图论解答，但它并不完全符合我所知道的任何图论问题。（注：这实际上是现实中的问题，为了更容易理解而虚构的）

假设我家里有一组偶数名象棋玩家。我有足够的桌子和棋盘供每个人使用，但我需要创建一份“配对”列表（不确定是否有图论术语可以描述），或者说是一份比赛清单，使每个人都能与别人对弈。所有象棋玩家都希望与他们从未见过面的人对弈。

如果我有每个玩家曾经对弈过的记录清单，我就可以轻松地构建出显示先前比赛情况的图形。例如，假设A已经与B和C对战过，而C已经与D对战过：

A----B
|
|     
C----D

我可以将B/C和A/D进行配对。但如果以前的比赛图形看起来像这样：

A----B
  \  |
   \ |
C    D

那么我将无法创建配对。B只能与C比赛，这将导致A和D（已经比赛过）互相比赛。

那么，除了暴力破解外，我如何知道是否可以创建配对呢？我不是在寻找树或循环，但是否有其他图形属性可以测试呢？

- Ryan

Answer 1

看起来像是经典的匹配问题：en.wikipedia.org/wiki/Matching_(graph_theory)。你可能正在寻找完美匹配。

还要看：http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm 注意：为了使用匹配算法，你需要使用你在问题中描述的图形的补图。

- Aryabhatta

Answer 2

如果你要将图中的每个玩家都表示两次，一次涂成红色，一次涂成绿色（比如说，避免使用黑白色以避免与棋子混淆），这可能会在二分图上成为一个问题，而对于这种情况有大量的资源可供使用。

- High Performance Mark