Zorganizowanie turnieju szachowego

[alek22999]

Naszym zadaniem jest zorganizowanie turnieju szachowego między \(\displaystyle{ n}\) zawodnikami. W ciągu ilu najmniej dni można zorganizować ten turniej, jeśli każda para zawodników musi rozegrać partię i żaden zawodnik nie może grać dwukrotnie w ciągu jednego dnia? Odpowiedź uzasadnij pokazując jak uzyskać optymalne rozwiązanie.

Zadanie to pojawiło się na liście dotyczącej grafów planarnych.

[Mruczek]

Mamy klikę \(\displaystyle{ n}\) - wierzchołkową (wierzchołki to zawodnicy, krawędzie to partie).
Powiedzmy, że krawędzie odpowiadające partiom rozegranym tego samego dnia kolorujemy tym samym kolorem. Partiom rozegranym w różnych dniach odpowiadają różne kolory. Chcemy, aby w tym samym dniu jeden zawodnik rozegrał co najwyżej jeden mecz, tzn aby żadne dwie krawędzie tego samego koloru nie miały wspólnego końca. Ponadto chcemy zminimalizować liczbę dni, czyli chcemy zminimalizować liczbę kolorów którymi możemy pokolorować krawędzie tej kliki. Sprowadziliśmy ten problem do klasycznego problemu kolorowania krawędziowego, w tym przypadku kliki - szukamy indeksu chromatycznego kliki i odpowiadającego mu kolorowania. Ten problem jest dość znany.

To jest zadanie z 48 OM - II - 3 stąd:

[alek22999]

Dziękuję kolego za twoją pomoc.