0000052

Ocieli dodatkowo

u>(C) £ rz(C) ♦ ©ntior k_#(C)] " ^{1# t0}

T(C) 4 rz(C) - ant ier [£ k_#(G)] - 1 5/ TWIERDZENIE 6.4 (Welnstein, 1963)

Dożęli C Jeot grafom zwykłym, takim io S(G)4rz(C) *• 3, to

T(C) 4 rz(G)

_______S.I2l2i___

♦ «ox [4, rz(G) +

s₀t^c> -¹)

6/ Oczywista Jest nierówność rz(G) 4 ^<]f(G)oc(C)₍ czyli

T(C) » Kf£l

oc(G)

7/ Graf nazywany Jest grafem płaskim wtedy 1 tylko wtedy, gdy da oię nazywać na płaszczyźnie w ten eposób, aby gałęzi© oię nie krzyżowały.

TWIERDZENIE 6.6 (Kuratewski, Pontriagin)

Graf jest płaski wtedy i tylko wtedy, gdy nie zawiera podgrafów homeomorflcznych z grafami przedstawionymi no rys.6.4

Rys.6.4

Owo grafy zwykłe bq homeomorficzno, gdy można Je otrzymać z jednego grafu przez "rozcinanie" gałęzi 1 wstawianie- nowych wiorzchołków.

Grofy zwykłe będoco modelami systemowymi używanymi przy projektowaniu kolorowania map politycznych oq grafami ;• oskimi.

TWIERDZENIE 6.6

Oflitll C Joet grafem plaoklo boz pętli, to T(C) 4 5

Dowód twierdzenia jest zamieszczony w [4].    _w

W praktyce nio spotkano dotychczas grafu płaskiego,którego liczba chroaatyczns byłaby większa 00 4. Od około 100 lat po -azukiwany jest dowód hipotezy, ta dlo grafu płaskiego

T(C)44

Autor nie zna dowodu, że hipoteza ta jest prawdziwa. Poszukiwania takiego dowodu nosi historyczny nazwę problemu czterech barw. Problaaea tym zajmowało się wielu wybitnych matematyków i przy tej okazji powstało wiele proc rozwijajycych teorię grafów,

6.6. .Metody euboptyaalnego kolorowania grafów

Wyznaczenie optymalnego rozwlyzanla problemu kolorowonia wierzchołków grafu o dużej Hotel wierzchołków 1 gałęzi Jest bardzo pracochłonne, a w wielu wypadkach praktycznie wręcz niemożliwe. Dlatego poszukiwane e« metody pozwolajyce w epooób efektywny wyznaczyć przynajmniej rozwiyzanie zbliżone do optymalnego.

6.5.1. Metoda redukcji grafu (H.Burlage, 1971)

Podstawy tej matody jest oszacowanie liczby chromatycznej T(C) ^ S(G) ♦ 1 oraz .sposób zmniejszenia ilości wykorzyety -wanych kolorów, przedstawiony w dowodzie tego oazacowanla(patrz punkt 6.4.2).

Wprowadzimy naetępujyce oznaczenia 1 G • <X,U,P>    - graf wyjściowy;

^Ck "^*k^,Uk'^Pk^    “ Podgraf określony przez X_k, przy czym przyj

miemy że G_q > G ;

e(x) - stopień wierzchołka w C ■ C_Q ;

103