Terminarz ligowy wg klucza matematycznego

Niewątpliwie do najbardziej popularnych należą turnieje sportowe, w których uczestnicy rozgrywają poszczególne gry (mecze) w parach na zasadzie „każdy z każdym". Warunek ten oznacza, że w każdej grze bierze udział dwóch graczy i każdy z nich rozgrywa grę z każdym innym dokładnie taką samą liczbę razy w całym turnieju. Biorąc pod uwagę istotny czynnik ograniczający liczbę gier rozgrywanych przez każdego z graczy w ustalonych przedziałach czasowych, turniej taki jest podzielony na rundy (kolejki); w danej rundzie każdy gracz rozgrywa co najwyżej jedną grę. Bardzo często dodatkowe kryterium stanowi lokalizacja rozgrywania poszczególnych gier na obiektach sportowych przypisanych do poszczególnych graczy. Wówczas jeden z graczy będzie rozgrywał dany mecz  „u siebie", podczas gdy dla jego przeciwnika będzie to gra „na wyjeździe".

Skonstruowanie harmonogramu spełniającego wymienione warunki może być wykonane w oparciu o tzw. Tablice Bergera, rozwiązania znane i wykorzystywane już w XIX wieku. Schematy te są nadal narzędziem powszechnie stosowanym w wielu krajach. Obecnie z tego rozwiązania korzystają w Polsce m.in. ligi piłki nożnej (poza Ekstraklasą), koszykówki, piłki siatkowej oraz piłki ręcznej. 

Tablice Bergera mają niestety liczne wady. Jedną z nich jest tzw. efekt przeniesienia, polegający na połączeniu w pary graczy, którzy w kolejnych dwóch rundach rozgrywają mecze z tym samym przeciwnikiem, zawsze w tej samej kolejności. Dla przykładu, efekt przeniesienia dla pary graczy (A,B) oznacza, że jeśli w danej rundzie przeciwnikiem gracza A jest C, to w rundzie następnej C rozgrywa mecz z B. Niewątpliwie należy uwzględnić jak najmniejszą liczbę powtórzeń takiej sytuacji dla zadanej pary graczy, aby uniknąć niemal ciągłego przejmowania przeciwnika po tym samym graczu. Inna niedogodność Tablic Bergera dotyczy nierównej liczby tzw. przełamań dla poszczególnych uczestników turnieju; przełamanie oznacza rozgrywanie dwóch kolejnych gier wyłącznie na swoim obiekcie, albo tylko „na wyjeździe". Dodatkowo dążyć należy do niewystępowania przełamań w ostatniej rundzie turnieju. W ten sposób bardzo istotnym kryterium jest takie zaplanowanie rozgrywek, aby schemat naprzemienności gier rozgrywanych „u siebie" i „na wyjeździe" był możliwie jak najbardziej zrównoważony. Zasadniczym celem podczas konstrukcji optymalnych harmonogramów jest dążenie do sytuacji, w której żaden uczestnik turnieju nie jest premiowany bardziej dogodnym układem rozgrywanych meczów.

 

Lista potencjalnych wymagań dodatkowych może zawierać szereg innych warunków. Dla przykładu można wymienić: oczekiwania mediów do równomiernego rozłożenia w sezonie potencjalnie najbardziej atrakcyjnych spotkań, równomierne rozłożenie gier rozgrywanych w danym mieście czy regionie, uwzględnienie dostępności przypisanych obiektów sportowych, restrykcje geograficzne, uwzględniające m.in. konieczność pokonywania dużych odległości. Ponadto optymalny harmonogram powinien mieć własność łatwej modyfikacji w przypadku, gdy w trakcie rozgrywek liczba graczy ulegnie zmianie.

Wspomniane wcześniej Tablice Bergera stosunkowo prosto można wyrazić w formie przedstawionego poniżej wzoru matematycznego. Jednak skonstruowanie niemal optymalnych harmonogramów, pozbawionych mankamentów wymienionych wcześniej, wraz z uwzględnieniem priorytetowej listy warunków dodatkowych, nie jest możliwe do uzyskania w tak łatwy sposób. W tym celu można się posłużyć dogodnym modelem matematycznym 1-faktoryzacji grafów pełnych. Wykorzystanie własności kombinatorycznych tych struktur wraz z możliwością komputerowej analizy, opartej na specjalnie przygotowanych metodach algorytmicznych, stanowią podstawowe  narzędzia do konstrukcji harmonogramów. O złożoności problemu może świadczyć fakt, iż samo wygenerowanie wszystkich potencjalnych możliwości jest niewykonalne nawet w przypadku turniejów z niewielką liczbą graczy - zadanie takie wielokrotnie przekracza możliwości obliczeniowe najszybszych komputerów. Dla przykładu, o ile w przypadku 10 uczestników turnieju liczba wszystkich możliwych bazowych schematów przypisania poszczególnych gier wynosi „tylko" 1 225 566 720, to w przypadku turnieju z 12 graczami jest to liczba  252 282 619 805 368 320, a dla 14 graczy 98 758 655 816 833 727 741 338 583 040.

 

Efektem długoletniej współpracy autora artykułu z profesorem Daliborem Fronckiem (z Uniwersytetu Minnesota Duluth w USA) są schematy spełniające wszystkie wyżej wymienione kryteria, przygotowane na potrzeby Orange Ekstraklasy (wykorzystywane w latach 2007-09) oraz Gambrinus Ligi - czeskiej pierwszej ligi piłki nożnej (wykorzystywane od roku 2002).

 

 

Tekst: dr Mariusz Meszka, Wydział Matematyki Stosowanej AGH