0000054 2

I

• ino* C, . .

i.j

Ola każdej pary wierzchołków    takiej, te ■ p

sprawdzamy, która z poniższych trzech sytuacji aa alejscs i postępujemy zgodnie z odpowiednia punktów algorytaui a/ oba wierzchołki mają już przyporządkowana kolory - nic nio robimy;

b/ jeden z wierzchołków aa już nadany kolor, a drugi nie. Badamy, czy można wierzchołkowi bez koloru nadać Jeden z używanych Już kolorów.

TAKi nadajemy ten kolor.

NIE i nic nie robimy.

c/ Oba wierzchołki nie mają nadanych kolorów, wtedy, o ile obu wierzchołkom możemy nadać kolor Już używany, to nadajemy lm ton kolor, w przeciwnym wypadku para tych wierz* chołków Inicjuje nowy kolor, p i • P - 1 .

Outoli p < O, to KONIEC - wszystkie wierzchołki są pokoloro

wane.

Skok do(3°).

Przykłod 6.4

Pokolorujemy metodą Wooda wierzchołki grafu z rys.6.5.

1 2 3 4 5 6

1    O

2    1

3    1

4    1

5    1

6    Lo

R(c) -

11110 0 1111 10 0 11 10 0 11 1110 1 11110

c-

1

2

3

4

5

6

1

0

-1

-1

-1

-1

4

2

-1

0

-1

-1

-1

-1

3    4    5    6

-1 -1 -1    4

-1 -1 -1 -1 0    4-1-1

4    0-1-1 -1 -1 0 -1 -1 -1 -1 O

Biorąc jod uwagę symetrycznofć macierzy C możemy*rozpatrywać tylko pary < i,J> tokle, że i ij.

Wartość p ■ 4. Para wierzchołków <1,6> otrzymują kolor nr 1. Naetąpnle para wierzchołków <3,4> otrzymuje kolor nr 2. Taraz cztarokrotnla zanlejezany wartość piw wyniku p • 0. Paraal wlarzchołków, która nla aej# nadanago koloru, w punkcia 3°c/ algorytmu, a« pory <2,2> 1 <5.5> ; nadajamy la odpowiadnlo (wierzchołkom 215) kolory o numerach 3 1 4. w tan apoaób wozyatkla wierzchołki e# pokolorowana za ponoć# czterech kolorów. Przypadkowo uzyekallśay rozwiązanie optyaalna ponieważ T(C) - 4.

107