0000053 2

*_k(x) - otoplcrt wiorzchołko w ;

S₀(C_k) •    ®_k(*) - -topień minimalny grafu.

n-1, gdzie

* »_W(*^k) • S₀(G_k).

Tworzymy cięg podgrofów    ; k ■ 0...

^Xk*l " ^Xk\l*^k) ^{; k} " °*****ⁿ“²* fldzio x^k

Po utworzoniu clogu podgrofów [c_k| nadaje oię kolory wierzchołkom x^k poczynojoc od xⁿ“¹ i otarajgc się nadawać kolory Jul wykorzystywane. W każdym k-tyra kroku toj procodury nio trzeba dyoponowoć wiykezę H0ÓCI9 barw nil S₀(G_k) ♦ i.

Oznaczając 6(G) ■ max G_c(G_k), otrzyoujomy następne oszacowanie liczby chromotycznej

8/ r(C) * 6(C) ♦ 1

Wartość G(G) zoatoła nozwana stopnica zredukowanym grafu. Dest to oszocowanic lepsze nil T(C) i S(C) ♦ 1, ponlewol dla każdego k mamy &_o(G_k) 6 S(G), o zatem G(G) 4 S(G). Równoóć 6(G) - S(G) epołniona Jest Je -dynio dla grofu regulornego, to znaczy ta -kiego, którego wszystkie wierzchołki mejg Identyczne stopnie [8].

Przykłod 6.3

Wyznaczymy eotodę redukcji pokolorowanie wierzchołków grafu G »<X,U,P> przedstawionego no rys.6.5.

/

Ryo.6.5

^C2    ■^^X2*^U2*^P2^    '    ^X2    "    {²*³»⁵*6} #    S₀(C₂) "    ³»    *²    ■    6

^C3    "    ^^X3'^U3*^P3^    #    ^x3    ■    {2,3.5}    , S₀(C₃)    -2, x³    ■    5

^C4    "    ^^X4*^U4^,P4^    *    ^X4    “    l²*³) »    ^s0(^c4) *    ^ł*    *⁴    •    ³

^C5    "    ^^X5^,U5'^Ps)    *    ^X5    *    (²) *    ^S0(C₅) *    °»    *⁵    ■    ²

Kolorujooy wierzchołki według neetępujocej kolejności

I*⁵.*⁴.*³.*².*¹.*⁰} . {2.3,5.6.4.l}

Moteay nedeć neetępujfce koloryt dle 2 nr i, dle 3 nr 2, dle 5 nr 3, dle 6 nr 4. dle 4 nr 2, dle 1 nr 4.

G(G) • aax (4,3,3,2,1,0} ■ 4 i otrzymujemy oezecowenie    •

?(C) 4 5

Zużyto cztery kolory. Przypedkowo uzyokano rozwiązanie optymol-ne, poniowoź <o(c) - 4 i 'j-(G) *4.

Ctqd |*(G) - 4.

6.5.2. Metoda ttooda

Heuryetyczno podstewf tej aetody etanowi naetępuj«co ro -zuaoweniet Dożęli w optymalnie pokolorowanym grafie letnieJe para wierzchołków <x,y> taka, że $>(x,y) .21 pora te Jeet połączona duż« iloócle aarezrut o długości 2, to wierzchołki te powinny aleć ton eea kolor [52] .

Algorytm tej aetody Jeet naetępuJfCy:

rz

(?) Dle grafu zwykłago G - <X.U,P> tworzymy mecie ^C" [^Cij]n»n * ⁿ * 1*1'

O

-1

dla i • J dl. r . 1

1J

dla r

gdzie r_tJ - element macierzy przyległości R(C).

i 05

A