szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 14 sie 2015, o 15:00 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
Szalony kartograf stworzył mapę rysując w przypadkowy sposób [tex] n [\tex]okręgów. Udowodnić,
że mapę tę można pokolorować dwoma kolorami tak, że regiony sąsiadujące mają różne
kolory.

Na początku przyszło mi twierdzenie o czterech barwach https://pl.wikipedia.org/wiki/Twierdzenie_o_czterech_barwach
jednak to nie to - inaczej zachowują się granice okręgów a inaczej "krajów", jednak ciężko mi powiedzieć dlaczego akurat tak jest. Pewnie trzeba jakoś pokazać ,że jak w każdym regionie narysujemy wierzchołek i poprowadzimy krawędzie między sąsiadującymi regionami to otrzymamy graf dwudzielny. Ma ktoś jakiś pomysł jak to ładnie pokazać?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 14 sie 2015, o 18:33 
Gość Specjalny

Posty: 3051
Lokalizacja: Gołąb
Wytłumacz bardziej szczegółowo treść zadania. Okręgi są położone zupełnie dowolnie? Jak definiujemy region? Co to znaczy że regiony sąsiadują?
Dopóki nie odpowiesz na te pytania zadanie nie ma dla mnie sensu.
Góra
Kobieta Offline
PostNapisane: 14 sie 2015, o 18:49 
Użytkownik
Avatar użytkownika

Posty: 2505
Tak jak zauważył bakala12, kilka pojęć wymaga doprecyzowania/ zdefiniowania. Zanim jednak autor tematu podejmie się odpowiedzenia na powyższe pytania, zaproponuję robocze rozwiązanie: pomaluj na zielono te punkty, które należą do nieparzyście wielu okręgów, zaś pozostałe na pomarańczowo.
Góra
Mężczyzna Offline
PostNapisane: 14 sie 2015, o 18:57 
Użytkownik

Posty: 15096
Lokalizacja: Bydgoszcz
Medea 2 napisał(a):
Tak jak zauważył bakala12, kilka pojęć wymaga doprecyzowania/ zdefiniowania. Zanim jednak autor tematu podejmie się odpowiedzenia na powyższe pytania, zaproponuję robocze rozwiązanie: pomaluj na zielono te punkty, które należą do nieparzyście wielu okręgów, zaś pozostałe na pomarańczowo.


Chciałas napisać "kół"?

Indukcja po ilości kół się kłania: gdy rysujemy nowe koło zmieniamy kolory tych obszarów, które są we wnętrzu
Góra
Kobieta Offline
PostNapisane: 14 sie 2015, o 19:23 
Użytkownik
Avatar użytkownika

Posty: 2505
Tak, kół zamiast okręgów, głupia pomyłka. Jak określić, które dwa obszary ze sobą sąsiadują, żeby takie rozwiązanie było poprawne? Przekrój ich domknięć nie może składać się z izolowanych punktów?
Góra
Mężczyzna Offline
PostNapisane: 14 sie 2015, o 19:42 
Użytkownik

Posty: 15096
Lokalizacja: Bydgoszcz
Z okręgami problem może być tylko tam, gdzie są one styczne. Ale to nie powinno stwarzać problemu, bo stycznośc implikuje zawieranie się stycznych kół lub ich "prawie" rozłaczność.
Góra
Mężczyzna Offline
PostNapisane: 14 sie 2015, o 22:38 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
bakala12 napisał(a):
Wytłumacz bardziej szczegółowo treść zadania. Okręgi są położone zupełnie dowolnie? Jak definiujemy region? Co to znaczy że regiony sąsiadują?
Dopóki nie odpowiesz na te pytania zadanie nie ma dla mnie sensu.




Niestety nic więcej mi o tym zadaniu nie wiadomo. Jedyne co mam to jego treść którą wam przedstawiłem. Intuicyjnie wydaję mi się ,że każdy okrąg jest regionem i każdy obszar powstały z przecięć okręgów.
Góra
Mężczyzna Offline
PostNapisane: 14 sie 2015, o 22:58 
Użytkownik
Avatar użytkownika

Posty: 6328
Niezależnie od tego czy okręgi się przecinają, czy są styczne to w punktach wspólnych dowolnej ilości okregów jest parzysta ilość wychodzących z takiego punktu łuków więc i parzysta ilośc obszarów (krajów) tam się stykających.
przykład::    
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 8 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Szalony układ równań  rekurencja  7
 szalony matematyku... jak narysować wykres funkcji:  badyl21a  6
 Szalony ułamek  realityoppa  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl