szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 11 lis 2016, o 20:49 
Użytkownik

Posty: 29
Lokalizacja: oOo
Na płaszczyźnie danych jest n punktów. Niektóre z nich są połączone odcinkami. Wiadomo, że z każdego punktu wychodzi nie więcej, niż 11 odcinków. Udowodnij, że punkty te można pokolorować czterema kolorami tak, aby jednokolorowych odcinków było nie więcej niż n.
Góra
Mężczyzna Offline
PostNapisane: 11 lis 2016, o 21:06 
Użytkownik

Posty: 15253
Lokalizacja: Bydgoszcz
A jak się koloruje odcinki?
Góra
Mężczyzna Offline
PostNapisane: 11 lis 2016, o 21:12 
Użytkownik

Posty: 29
Lokalizacja: oOo
a4karo napisał(a):
A jak się koloruje odcinki?

Jednokolorowy odcinek to taki, który ma końce tego samego koloru.
Góra
Mężczyzna Offline
PostNapisane: 11 lis 2016, o 21:38 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Hint:    

Rozwiązanie:    
Góra
Mężczyzna Offline
PostNapisane: 11 lis 2016, o 21:56 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
a jak nie będzie ani jednego odcinka
Góra
Mężczyzna Offline
PostNapisane: 11 lis 2016, o 22:38 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Troszeczkę zmieniłem treść rozwiązania - warunek o minimalnym stopniu z zacytowanego zadania można zamienić na warunek o maksymalnym stopniu. Chodzi mi o to, że sposób rozwiązywania tego zadania jest dość charakterystyczny i znany z różnych olimpiad - półniezmienniki.
Przypadek braku odcinków jest trywialny i po tej zmianie już działa.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczba połączeń w pary nieprzecinajace się odcinki  lightinside  2
 Obszary koła, które są dzielone przez odcinki  Hendra  5
 Dzielenie prostej na odcinki o zadanych długościach  TrzyRazyCztery  3
 punkty i odcinki  Anonymous  1
 odcinki - zadanie 2  mol_ksiazkowy  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl