5
这个问题在图论中应该有答案，但它并不完全符合我所知道的任何图论问题。 （注意：这实际上是一个现实世界的问题，为便于阅读而虚构化）从图形创建“配对”？
想象一下，我家有一组偶数棋手。我有足够的桌子和国际象棋套装供大家玩，但我需要创建一个“配对”（不知道是否有图论理论术语）或一系列比赛，以便每个人都扮演一个人。国际象棋选手们都喜欢和以前从未玩过的人一起玩。
如果我从每个玩家身上得到了他们玩过的玩家的名单，我可以很容易地创建一个显示以前比赛的图表。例如，假设一个发挥B和C，和C起到d：
A----B
|
|
C----D
我知道我可以投其所好B/C和A/d创建配对。
但是，如果以前的对决的图如下所示：
A----B
\ |
\ |
C D
然后，我将无法创建配对。 B只能打C，这会让A和D（已经打过）彼此打对方。
那么，我怎么能知道（通过蛮力以外的方法）我是否可以创建配对？这不是我正在寻找的树或周期，但是我还可以测试其他一些图属性吗？