TU Wien:Diskrete Mathematik für Informatik VU (Drmota)/Übungen WS20/Beispiel 30

From VoWi
Jump to navigation Jump to search

Follow the hint below to construct a schedule for the matches in a league of 2n teams which meets the following constraints:
-In each round each team plays exactly one match.
-In the end each team must have played against each of the other teams exactly once.

Hint: Consider the graph K2n on the vertex set {1,2,...,2n} and show that each of the sets Mi={1i}∪{xy:x+y≡2imod 2n−1 and x!=y, x!= 1,y!= 1}is a perfect matching for i∈{2,...,2n}

Hilfreiches[edit | edit source]

Lösungsvorschlag[edit | edit source]