kolorowanie grafu - graf planarny 3-kolorowalny

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Algorytmistrz
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 12 wrz 2012, o 20:07
Płeć: Mężczyzna
Lokalizacja: Białogard

kolorowanie grafu - graf planarny 3-kolorowalny

Post autor: Algorytmistrz »

Witam, mam problem z zadaniem:
Na płaszczyźnie narysowano linie proste, w taki sposób że żadne trzy nie przecinają się w tym samym miejscu (czyli w jednym punkcie maksymalnie przecinają się tylko 2 proste odcinki). Wykaż że powstały graf jest 3-kolorowalny.

Oczywiście każdy graf planarny jest 4-kolorowalny (z twierdzenie o czterech barwach).
Oczywiście każdy wierzchołek ma stopień :
4 (standardowe przecięcie 2 odcinków)
lub 3 (gdy koniec odcinka przecina inny odcinek)
lub 2 (gdy stykają się dwa końce odcinków)
lub 1 (koniec odcinka).

Nie potrafię dojść w jaki sposób wykazać że graf jest 3-kolorowalny, oczywiście nie jest 2- kolorowalny (np "trójkąt"), a napewno jest 4-kolorowalny jak wyżej wspomniałem.

Za wszelką udzieloną pomoc z góry serdecznie dziękuje.
pawels
Użytkownik
Użytkownik
Posty: 304
Rejestracja: 5 wrz 2009, o 20:15
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 3 razy
Pomógł: 33 razy

kolorowanie grafu - graf planarny 3-kolorowalny

Post autor: pawels »

Ponumerujmy nasze proste w następujący sposób: jako k-tą wybieramy taką, dla której wszystkie punkty, poza do tej pozy ponumerowanymi, leżą po jednej jej stronie. Zacznijmy kolorować w dowolny poprawny sposób punkty na ostatniej prostej.

Następnie bierzemy poprzednią prostą i kolorujemy jakkolwiek poprawnie dowolny skrajny wierzchołek na niej, a następnie kolorujemy poprawnie kolejne z nich. Widzimy, że każdy dotychczas niepokolorowany wierzchołek z tej prostej ma co najwyżej 2 sąsiadów w zbiorze już pokolorowanych wierzchołków, więc uda się nam pokolorować wszystkie punkty z tej prostej.

Powtarzając czynności z poprzedniego akapitu w stosunku do prostych o coraz niższych numerach w końcu pokolorujemy poprawnie wszystkie wierzchołki.
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

kolorowanie grafu - graf planarny 3-kolorowalny

Post autor: norwimaj »

pawels pisze:Ponumerujmy nasze proste w następujący sposób: jako k-tą wybieramy taką, dla której wszystkie punkty, poza do tej pozy ponumerowanymi, leżą po jednej jej stronie.
Zdanie jest nieścisłe, bo najpierw twierdzisz, że numerujesz proste, a później, że punkty. Czy chodziło o: "jako \(\displaystyle{ k}\)-tą wybieramy taką, dla której wszystkie punkty, poza przecięciami do tej pory ponumerowanych prostych, leżą po jednej jej stronie"?

Powinieneś jeszcze wyjaśnić, dlaczego tak się da. Przynajmniej pokaż to na przykładzie grafu, którego krawędzie są zawarte w przekątnych pięciokąta wypukłego.

\(\displaystyle{ \begin{picture}(0,0)
\put(0,0){\circle*{4}}
\put(60,0){\circle*{4}}
\put(60,60){\circle*{4}}
\put(30,60){\circle*{4}}
\put(0,30){\circle*{4}}
\put(-8,-10){$1$}
\put(62,-10){$5$}
\put(62,62){$4$}
\put(23,62){$3$}
\put(-7,32){$2$}
\put(20,20){\circle*{4}}
\put(40,40){\circle*{4}}
\put(12,24){\circle*{4}}
\put(20,40){\circle*{4}}
\put(36,48){\circle*{4}}
\put(18,10){$8$}
\put(43,35){$7$}
\put(2,17){$9$}
\put(8,42){$10$}
\put(35,52){$6$}
\put(0,0){\line(1,1){60}}
\put(0,0){\line(1,2){30}}
\put(60,0){\line(-1,2){30}}
\put(60,0){\line(-2,1){60}}
\put(0,30){\line(2,1){60}}
\end{picture}}\)

Od której prostej należy zacząć?
ODPOWIEDZ