Szalony kartograf

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
gardner

Szalony kartograf

Post autor: gardner »

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

Kod: Zaznacz cały

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ć?}\)
bakala12
Użytkownik
Użytkownik
Posty: 3044
Rejestracja: 25 mar 2010, o 15:34
Płeć: Mężczyzna
Lokalizacja: Gołąb
Podziękował: 24 razy
Pomógł: 513 razy

Szalony kartograf

Post autor: bakala12 »

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.
Awatar użytkownika
Medea 2
Użytkownik
Użytkownik
Posty: 2491
Rejestracja: 30 lis 2014, o 11:03
Płeć: Kobieta
Podziękował: 23 razy
Pomógł: 479 razy

Szalony kartograf

Post autor: Medea 2 »

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.
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Szalony kartograf

Post autor: a4karo »

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
Awatar użytkownika
Medea 2
Użytkownik
Użytkownik
Posty: 2491
Rejestracja: 30 lis 2014, o 11:03
Płeć: Kobieta
Podziękował: 23 razy
Pomógł: 479 razy

Szalony kartograf

Post autor: Medea 2 »

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?
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Szalony kartograf

Post autor: a4karo »

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ść.
gardner

Szalony kartograf

Post autor: gardner »

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.
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Szalony kartograf

Post autor: kerajs »

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::    
ODPOWIEDZ