Szalony kartograf stworzył mapę rysując w przypadkowy sposób \(\displaystyle{ n [ ex]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
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ć?}\)
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.
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.
Medea 2 pisze: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
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?
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ść.
bakala12 pisze: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.
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.