Создать «спаривание» из графика?

Question

Эта проблема пахнет так, будто в теории графов должен быть ответ, но она не совсем соответствует ни одной из проблем теории графов, которые я знаю. (Примечание: на самом деле это реальная проблема, выдуманная для облегчения чтения)

Представьте, что в моем доме группа шахматистов с четным номером. У меня есть множество столов и шахматных наборов, на которые могут играть все, но мне нужно создать «Pairing» (не уверен, есть ли для него термин теории графов) или список матчей, чтобы каждый играл кого-нибудь. Все шахматисты хотели бы сыграть кого-то, кого они никогда раньше не играли.

Если у меня есть список от каждого игрока, с которым они играли, я могу легко построить график, показывающий предыдущие матчи. Например, допустим, что 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) . То, что вы, вероятно, ищете, идеально подходит.

Также посмотрите на: http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm

Примечание: для использования алгоритма сопоставления необходимо использовать Дополнение графика, который вы описываете в вопросе.

Answer 2

Если бы вы представляли каждого игрока на своем графике дважды, один раз окрашенный в красный и один раз в зеленый (скажем, избегая черно-белого, чтобы избежать путаницы с шахматными фигурами), это могло бы стать проблемой на двудольном графике, для которого существует куча ресурсов.