This problem smells like there should be an answer in graph theory, but it certainly does not correspond to any of the graph theory problems that I know. (Note: this is really a real problem, fictional for easier reading)
Imagine that I have an even group of chess players in my house. I have many tables and chess sets for everyone to play, but I need to create a “Pairing” (not sure if there is a term for graph theory for it) or a list of matches in which everyone plays someone. Chess players would all like to play the one they never played with.
If I have a list from each player they played, I can easily build a graph showing previous comparisons. For example, let's say A played B and C, and C played D:
A
|
|
C
I know that I can match B / C and A / D to create pairing.
But if the schedule of previous matches looks like this:
A----B
\ |
\ |
C D
Then I can’t create pairing. B can only play C, which would make A and D (who have already played) play with each other.
So, how can I find out (using some method other than brute force), can I create a pairing? This is not the tree or cycle that I am looking for, but is there another graph property that I can check?
Ryan source
share