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 ?
[Teoria grafów] turniej ligu piłkarskiej
-
- Użytkownik
- Posty: 268
- Rejestracja: 31 mar 2013, o 20:23
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 82 razy
[Teoria grafów] turniej ligu piłkarskiej
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.
-
- Użytkownik
- Posty: 2283
- Rejestracja: 14 cze 2011, o 11:34
- Płeć: Mężczyzna
- Lokalizacja: Sosnowiec
- Podziękował: 88 razy
- Pomógł: 351 razy
[Teoria grafów] turniej ligu piłkarskiej
To rozwiązanie jest błędne. Dajmy na przykład \(\displaystyle{ n=4}\). Zgodnie z
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.Hydra147 pisze: \(\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}\).
-
- Użytkownik
- Posty: 28
- Rejestracja: 13 kwie 2012, o 18:58
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Pomógł: 2 razy
[Teoria grafów] turniej ligu piłkarskiej
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.
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.