從圖形創建「配對」？

Question

這個問題在圖論中應該有答案，但它並不完全符合我所知道的任何圖論問題。 （注意：這實際上是一個現實世界的問題，爲便於閱讀而虛構化）

想象一下，我家有一組偶數棋手。我有足夠的桌子和國際象棋套裝供大家玩，但我需要創建一個「配對」（不知道是否有圖論理論術語）或一系列比賽，以便每個人都扮演一個人。國際象棋選手們都喜歡和以前從未玩過的人一起玩。

如果我從每個玩家身上得到了他們玩過的玩家的名單，我可以很容易地創建一個顯示以前比賽的圖表。例如，假設一個發揮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)。你可能正在尋找的是一個完美的匹配。

也要看：http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm

注：爲了使用匹配算法，您需要使用您的問題描述圖表的Complement。

Answer 2

如果您要在圖表中顯示每個玩家兩次，一次爲紅色，一次爲綠色（例如，避免黑白以避免與棋子混淆），這可能會變成一個二分圖上的問題，對此有很多資源。