Na płaszczyźnie narysowano linie, tak że żadne 3 nie przecinają się w tym samym punkcie.
Wykazać, że punkty przecięcia się linii można pokolorować 3 kolorami, tak aby na każdej linii sąsiednie punkty przecięć otrzymały różne kolory.
prosze o pomoc.
przecinające się linie
-
Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
przecinające się linie
Powstaje graf 2-regularny, więc raczej nie ma kłopotu z kolorowaniem 2 barwami. Z każdego wierzchołka wychodzą 2 krawędzie, chyba łatwo sobie wyobrazić jak przebiega kolorowanie?
-
Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
przecinające się linie
Oj rzeczywiście, bzdurę napisałem. Spróbuję się zaraz poprawić.
edit:
Nie wiem czy dobrze interpretuję treść zadania, ale jak dla mnie linie = proste . Zakładam też, że linii można narysować tylko skończenie wiele, bo inaczej teza może być nieprawdziwa.
Ok, to ogólna idea jest taka jak zawsze tzn. indukcja po liczbie wierzchołków. Tutaj wierzchołkami są przecięcia prostych i kłopot jest taki, że krok indukcyjny się zacina, bo po usunięciu jednego wierzchołka może się pojawić graf, który nie powstaje w żądany sposób... Moja propozycja jest taka, żeby zmodyfikować nieco treść zadania, tzn. nie rysujemy całych linii, tylko odcinki. Wierzchołkami są końce odcinków, ale trzeba jeszcze podać zastrzeżenia co do ilości odcinków wychodzących z jednego wierzchołka itp.
No i teraz można już prowadzić indukcję względem liczby wierzchołków.
1. Dla jednego wierzchołka oczywiste.
2. Niech dla wszystkich grafów o n wierzchołkach jest OK. Wezmy teraz dowolny graf \(\displaystyle{ G}\) o (n+1) wierzchołkach, wystarczy teraz pokazać, że istnieje w tym grafie wierzchołek stopnia \(\displaystyle{ \le 2}\) (bo wtedy z zał. ind. pokolorujemy \(\displaystyle{ G \backslash \{v\}}\) a \(\displaystyle{ v}\) trywialnie).
Skąd taki wierzchołek wziąć, ano najlepiej zobaczyć to na rysunku, postaram się to jakoś wyjaśnić. Niech \(\displaystyle{ (a,b)}\) będzie wierzchołkiem, którego współrzędna \(\displaystyle{ y}\) jest największa. Jeśli jest kilka takich wierzchołków (o tej samej, maksymalnej wspolrzednej \(\displaystyle{ y}\)) to wezmy ten, o najwiekszej współrzędnej \(\displaystyle{ x}\). Łatwo wtedy pokazać (patrząc na rysunek), że taki wierzchołek nie może mieć stopnia większego niż 2.
edit:
Nie wiem czy dobrze interpretuję treść zadania, ale jak dla mnie linie = proste . Zakładam też, że linii można narysować tylko skończenie wiele, bo inaczej teza może być nieprawdziwa.
Ok, to ogólna idea jest taka jak zawsze tzn. indukcja po liczbie wierzchołków. Tutaj wierzchołkami są przecięcia prostych i kłopot jest taki, że krok indukcyjny się zacina, bo po usunięciu jednego wierzchołka może się pojawić graf, który nie powstaje w żądany sposób... Moja propozycja jest taka, żeby zmodyfikować nieco treść zadania, tzn. nie rysujemy całych linii, tylko odcinki. Wierzchołkami są końce odcinków, ale trzeba jeszcze podać zastrzeżenia co do ilości odcinków wychodzących z jednego wierzchołka itp.
No i teraz można już prowadzić indukcję względem liczby wierzchołków.
1. Dla jednego wierzchołka oczywiste.
2. Niech dla wszystkich grafów o n wierzchołkach jest OK. Wezmy teraz dowolny graf \(\displaystyle{ G}\) o (n+1) wierzchołkach, wystarczy teraz pokazać, że istnieje w tym grafie wierzchołek stopnia \(\displaystyle{ \le 2}\) (bo wtedy z zał. ind. pokolorujemy \(\displaystyle{ G \backslash \{v\}}\) a \(\displaystyle{ v}\) trywialnie).
Skąd taki wierzchołek wziąć, ano najlepiej zobaczyć to na rysunku, postaram się to jakoś wyjaśnić. Niech \(\displaystyle{ (a,b)}\) będzie wierzchołkiem, którego współrzędna \(\displaystyle{ y}\) jest największa. Jeśli jest kilka takich wierzchołków (o tej samej, maksymalnej wspolrzednej \(\displaystyle{ y}\)) to wezmy ten, o najwiekszej współrzędnej \(\displaystyle{ x}\). Łatwo wtedy pokazać (patrząc na rysunek), że taki wierzchołek nie może mieć stopnia większego niż 2.