[Teoria grafów] turniej ligu piłkarskiej

[matinf]

Witam,
Mamy turniej ligi piłkarskiej. Tzn każdy z każdym rozegra dwa mecze, ale żadna drużyna nie rozegra dwóch meczy jednego dnia. Tzn każda maxymalnie jeden. Jaka jest minimalna liczba dni potrzebna do rozegrania wszystkich meczy ?

[Hydra147]

Liczba możliwych sparowań drużyn to \(\displaystyle{ \frac{n(n-1)}{2}}\). Skoro każda para rozgrywa \(\displaystyle{ 2}\) mecze to będzie ich w sumie \(\displaystyle{ n(n-1)}\). Z kolei skoro każda drużyna rozgrywa max \(\displaystyle{ 1}\) mecz, to jednego dnia może się odbyć max \(\displaystyle{ n}\) meczy. Czyli nasza minimalna liczba meczy jest nie mniejsza niż \(\displaystyle{ n-1}\). Jest to wynik osiągalny. Oznaczmy drużyny numerami \(\displaystyle{ 1,2,3,...,n}\). \(\displaystyle{ i}\)-tego dnia zawodów drużyna z numerem \(\displaystyle{ k}\) gra mecz z drużyną o numerze \(\displaystyle{ k+i}\) przy czym jeśli liczba ta jest większa od \(\displaystyle{ n}\) to gra z drużyną o numerze \(\displaystyle{ k+i-n}\). Pozostaje Ci tylko udowodnić, że dla każdej pary drużyn istnieją dokładnie \(\displaystyle{ 2}\) dni, w których drużyny te grały ze sobą mecz.

[matmatmm]

To rozwiązanie jest błędne. Dajmy na przykład \(\displaystyle{ n=4}\). Zgodnie z

\(\displaystyle{ i}\)-tego dnia zawodów drużyna z numerem \(\displaystyle{ k}\) gra mecz z drużyną o numerze \(\displaystyle{ k+i}\) przy czym jeśli liczba ta jest większa od \(\displaystyle{ n}\) to gra z drużyną o numerze \(\displaystyle{ k+i-n}\).

pierwszego dnia jedynka gra z dwójką, dwójka z trójką, trójka z czwórką i czwórka z jedynką, czyli każda drużyna rozgrywa dwa mecze.

[kapsl0k]

Skoro każdy gra z każdym, to możemy rozważyć graf pełny, w którym każda krawędź oznacza jeden mecz w turnieju.

Możemy ten problem rozważyć jako kolorowanie krawędzi w grafie, tzn. gdy krawędzie mają dwa takie same kolory, to te mecze możemy rozegrać jednego dnia, jeśli nie, to muszą być rozegrane w różne dni.

Jak wiadomo, graf pełny \(\displaystyle{ K_n=(V,E)}\) ma indeks chromatyczny równy \(\displaystyle{ |V|}\), gdy liczba wierzchołków jest nieparzysta oraz \(\displaystyle{ |V|-1}\) w przeciwnym przypadku. Indeks chromatyczny jest zarazem liczbą dni potrzebną do rozegrania po jednym meczu. Nasze drużyny mają jednak rozegrać po dwa mecze, więc potrzeba nam dwa razy tyle dni.