szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
PostNapisane: 18 lut 2017, o 12:08 
Użytkownik
Naszym zadaniem jest zorganizowanie turnieju szachowego między 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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 18 lut 2017, o 15:18 
Użytkownik

Posty: 1086
Lokalizacja: Lublin/Warszawa
Mamy klikę 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: http://archom.ptm.org.pl/?q=node/442
Góra
PostNapisane: 18 lut 2017, o 15:25 
Użytkownik
Dziękuję kolego za twoją pomoc. :)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Uczestników turnieju szachowego podzielono na 2 rozłączne gr  kamilka257  1
 2n drużyn w turnieju gra równolegle, dowód, że się da  banias  3
 drogi krola szachowego/Ustawienie podzbiorow w ciag  pred  3
 Ilość partii w turnieju szachowym  goku94  1
 W turnieju szachowym rozegrano  91patii  5
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl