graf planarny
-
skowron01
- Użytkownik
- Posty: 2
- Rejestracja: 26 sty 2008, o 23:23
- Płeć: Mężczyzna
- Lokalizacja: warszawa
graf planarny
Niech G bedzie grafem planarnym dla ktorego w pewnej jego planarnej reprezentacji kazdy region jest ograniczony cyklem o parzystej liczbie krawedzi Pokazac ze G jest dwudzielny.
-
loirid
- Użytkownik
- Posty: 4
- Rejestracja: 17 sty 2007, o 00:32
- Płeć: Mężczyzna
- Lokalizacja: Pisk
- Pomógł: 1 raz
graf planarny
zatem kazdy cykl jest parzystej dlugosci
zauwazmy ze gdy kolorujemy cykl o dlugosci parzystej dwona kolorami otrzymujemy kolorowanie
B C ... B C B C
zatem kolorujemy dowolny wierzchołek na dowolny kolor
zatem teraz mozemy pokolorowac caly cykl naprzemiennie 2 kolorami
weźmy teraz inny cykl łączący sie z naszym juz pokolorowanym co najmniej 1 wierzchołkiem (może być więcej ale to nic nie przeszkadza ponieważ nigdy nie będzie sytuacji B B lub C C)
ponieważ cykle są parzystej długości
teraz dokolorowujemy te wierzchołki w cyklu ktore nie byly pokolorowane i tak kolorujemy caly graf
graf zostal pokolorowany 2 kolorami wiec musi być dwudzielny
(nie wiem czy to jest formalnie ale działa )
zauwazmy ze gdy kolorujemy cykl o dlugosci parzystej dwona kolorami otrzymujemy kolorowanie
B C ... B C B C
zatem kolorujemy dowolny wierzchołek na dowolny kolor
zatem teraz mozemy pokolorowac caly cykl naprzemiennie 2 kolorami
weźmy teraz inny cykl łączący sie z naszym juz pokolorowanym co najmniej 1 wierzchołkiem (może być więcej ale to nic nie przeszkadza ponieważ nigdy nie będzie sytuacji B B lub C C)
ponieważ cykle są parzystej długości
teraz dokolorowujemy te wierzchołki w cyklu ktore nie byly pokolorowane i tak kolorujemy caly graf
graf zostal pokolorowany 2 kolorami wiec musi być dwudzielny
(nie wiem czy to jest formalnie ale działa )