从图表中创建"配对"？

Question

这个问题有点像图论中应该有答案,但它并不完全符合我所知道的任何图论问题.(注意:这实际上是一个现实世界的问题,为了更容易阅读而虚构化)

想象一下,我家里有一群偶数的国际象棋选手.我有很多桌子和国际象棋给大家玩,但我需要创建一个"配对"(不知道是否有是它的一个图论的术语),或使得每个人都扮演着一个人的对决名单.国际象棋选手都喜欢扮演以前从未玩过的人.

如果我有一个他们所扮演的每个玩家的列表,我可以很容易地构建一个显示前一场比赛的图表.例如,假设A播放了B和C,C播放了D:

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

我知道我可以匹配B/C和A/D来创建配对.

但是如果之前的比赛图表看起来像这样:

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

然后我将无法创建配对.B只能玩C,这会让A和D(已经玩过的人)相互比赛.

那么,我怎么能知道(通过蛮力以外的某种方法)是否可以创建配对？它不是我正在寻找的树或周期,但是我可以测试一些其他图形属性吗？

Answer 1

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

注意：为了使用匹配算法，您需要使用问题中描述的图的补集。