dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

1

Kolorowanie grafów

Określenia

Kolorowanie (wierzchołków) - przyporządkowanie wierzchołkom grafu
liczb naturalnych w taki sposób, aby końce żadnej krawędzi nie mialy
przypisanej tej samej liczby.

O kolorach mówi się ze względów historycznych i dla lepszego
wyobrażenia

Pokolorowanie wierzchołków grafu - jedno konkretne
przyporządkowanie liczb wierzchołkom. Pokolorowanie dozwolone
(legalne), gdy nie ma krawędzi której wierzchołki mają ten sam kolor.

Pokolorowanie optymalne - pokolorowanie dozwolone do którego użyto
najmniejszą mozliwą liczbę kolorów.

Liczba chromatyczna grafu

χ(G) - najmniejsza liczba kolorów

potrzebna do legalnego pokolorowania grafu G.

W niektórych przypadkach mozna łatwo podać liczbę chromatyczną
grafu

χ(G).

Przykłady:

a) Graf pełny

Każdy wierzchołek połączony z każdym. Graf pełny o n wierzchołkach
oznaczamy symbolem K

n

.

Liczba chromatyczna grafu K

n

jest równa

χ(K

n

) = n.

b) Graf cykliczny.

Graf cykliczny jest to graf, w którym każdy wierzchołek ma stopień 2.
Inaczej jest to graf spójny, regularny stopnia drugiego. Graf cykliczny
oznaczany C

n

, gdzie n - liczbą wierzchołków.

Przypadek 1 - liczba wierzchołków nieparzysta. Liczba chromatyczna
jest równa 3.
Jeżeli bowiem wierzchołki cyklu mają numery 1,2, ..., 2k+1, 1, to
można przyporządkować: wierzchołkom o numerach 1,3, ,,,. 2k-1 kolor
1, wierzchołkom 2,4, ..,2k kolor 2. Wierzchołek 2k+1 sąsiaduje z
wierzchołkami 2k i 1, więc nie moze otrzymać ani koloru 1 ani koloru 2

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

2

- nadajemy mu nowy kolor 3. Stąd

χ(C

2k+1

) = 3

Przypadek 2 - liczba wierzchołków parzysta. Rozumując podobnie jak w
przypadku 1 otrzymujemy

χ(C

2k

) =2.

Rys. 1 Kolorowanie wybranych grafów
a) pełny K

5

b) cykliczny C

5

c) cykliczny C

4

Oszacowania liczby chromatycznej grafu

Problem wyznaczania liczby chromatycznej jest w ogólności NP-trudny.
W praktyce korzysta się z różnych oszacowań tej liczby. Podamy
oszacowania dla pewnych przypadków, poprzedzając je wprowadzeniem
niezbędnych określeń.
Kliką grafu nazywamy jego podgraf pełny. Rozmiar kliki

ω - liczba

wierzchołków kliki.

Twierdzenie:

Liczba chromatyczna grafu

χ(G) spełnia nierówność

χ(G) ≥ ω

gdzie

ω jest rozmiarem maksymalnej kliki grafu G.

Podane oszacowanie ma wady:

- parametr

ω jest wielkością trudną do wyliczenia

- oszacowanie liczby chromatycznej grafu przez rozmiar maksymalnej

kliki nie jest dokładne, róznica między

χ(G) ≥ ω moze być dowolnie

duża.

(5)

(3)

(1)

(2)

(4)

a)

(2)

(1)

(2)

(1)

c)

(1)

(2)

(1)

(2)

(3)

b)

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

3

Inne oszacowanie, łatwiejsze do wyliczenia

(chociaż mniej dokładne)

ω ≥ n

2

/ (n

2

-2m) n - liczba wierzchołków, m - liczba krawędzi

Dalsze oszacowania liczby chromatycznej.

Twierdzenie

Dla dowolnego grafu G prawdziwe jest oszacowanie liczby
chromatycznej

χ(G)

χ(G) ≤ ∆+1,

gdzie

∆ jest maksymalnym stopniem wierzchołka.

Równość zachodzi dla dwóch klas grafów: grafy pełne K

n

oraz cykle

o nieparzystej liczbie wierzchołków (Brooks,1941)

Wniosek

Jeżeli G

≠K

n

oraz

∆ ≥ 3 to χ(G) ≤ ∆.

Powyższe oszacowanie może być również bardzo niedokładne, co
pokazuja poniższe przykłady
Przykład 1
Gwiazda jest grafem, w którym jeden wierzchołek jest połączony ze
wszystkimi pozostałymi i nie ma innych krawędzi (rys.2). Gwiazdę o
n+1 wierzchołkach oznaczamy K

1,n

- jest to szczególny przypadek grafu

dwudzielnego (opisany w dalsze części). Gwiazda, jak każdy graf
dwudzielny, ma liczbę chromatyczną 2.






Oszacowanie zależne od liczby krawędzi grafu

Twierdzenie:

Niech m oznacza liczbę krawędzi grafu,

λ długość najdłuższej ścieżki

w grafie G, mierzona liczbą krawędzi.
Liczba chromatyczna grafu spełnia nierówności

χ(G) ≤ (2m)

1/2

+1

i

χ(G) ≤ λ +1

(1)

(2)

(2)

(2)

(2)

(2)

Rys. 2 Gwiazda -
liczba chromatyczna =2.

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

4

Również i te oszacowania mogą być bardzo niedokładne.

Rys. 3 Kolorowanie ścieżki P

5

Przykładem jest ścieżka

P

n

= (v

0

, v

1

, ...,v

n

) v

i

≠v

j

dla i

≠ j (rys.3). W tym przypadku χ(P

n

) =

2 ale

λ(P

n

) = n. Liczba krawędzi m = n i również (2m)

1/2

= (2n)

1/2

nie

jest najlepszym oszacowaniem.

Jako drugi przykład można podać graf dwudzielny pelny K

n, n

(rys. 4) .

Rys. 4. Graf dwudzielny pełny

Graf dwudzielny - taki graf, w którym wierzchołki są podzielone na dwa
zbiory, a końce każdej krawędzie należą do różnych zbiorów. Pełny graf
dwudzielny o n

1

+ n

2

wierzchołkach oznacza się K

n1, n2

Liczba krawędzi grafu dwudzielnego pełnego K

n, n

jest równa m=2n

2

,

więc z oszacowania

χ(G) ≤ (2m)

1/2

+1 otrzymujemy

χ(G) ≤ 2n

+1,

podczas gdy

χ(G) =2.

(1)

(2)

(1)

(1)

(2)

(2)

u

1

u

2

u

3

u

n

v

1

v

n

v

3

v

2

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

5

Kolorowanie grafów planarnych
Graf planarny - to graf, który można przedstawić na płaszczyźnie tak,
by żadne dwie krawędzie się nie przecinały
Dwa minimalne grafy, które nie są planarne, to K

5

i K

3,3

.(rys )

Rys 5 Minimalne grafy nieplanarne

a) graf pełny K

5

b) graf dwudzielny K

3,3

Dowolny rysunek płaski grafu planarnego wyznacza spójne obszary
płaszczyzny zwane ścianami. Dokładnie jeden z tych obszarów, zwany
ścianą zewnętrzną, jest nieograniczony.

Wzór Eulera

Jeżeli G jest grafem spójnym i planarnym, to

| V | + | S | − | E | = 2,

gdzie V - zbiór wierzchołków, E - zbiór krawędzi, S - zbiór ścian
dowolnego rysunku płaskiego grafu G.

Wnioski

1.

Jeżeli G jest planarny, to |E|

≤ 3 |V| - 6 .

2.

Jeżeli G jest planarny, to przynajmniej jeden wierzchołek jest

stopnia co najwyżej 5.

Twierdzenie o czterech barwach

Graf planarny można zawsze pokolorować przy użyciu co
najwyżej czterech kolorów.

(5)

(3)

(1)

(2)

(4)

(1)

(1)

(1)

(2)

(2)

(2)

a)

b)

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

6

Powyższe twierdzenie zostało udowodnione w 1976 roku (Appel,
Haken) przy wspomaganiu komputerowym (sprawdzenia 1936
przypadków szczególnych). Wczesniej znane było analogiczne
twierdzenie w którym liczba kolorów była równa 5 (Heawood, 1890)

Grafy o mniejszej liczbie kolorów

Twierdzenie

Graf planarny nie zawierający podgrafu K

3

jest trójbarwny.

Twierdzenie.

Graf planarny jest dwubarwny wtedy i tylko wtedy, gdy nie zawiera
cykli o nieparzystej długości.

Wniosek

Każdy graf dwudzielny jest dwubarwny

Algorytmy przyblizone kolorowania

Kolorowanie grafów w ogólności jest zagadnieniem NP- trudnym.
Dlatego w praktyce stosuje się algorytmy przyblizone, działające w
czasie wielomianowym. Jednak algorytmy te często wymagają użycia
dużo większej liczby kolorów niż jest to konieczne.

Przez A(G) oznaczymy liczbę kolorów jaką musi użyć algorytm A do
kolorowania grafu G.

Dla scharakteryzowania algorytmów kolorowania wprowadzamy
parametry

1. Złożoność obliczeniowa
2. Funkcja dobroci dla grafu o n wierzchołkach

A(n) = max { A(G) /

χ(G) }

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

7

Prosty algorytm sekwencyjny

Każdy krok w prostym algorytmie sekwencyjnym polega na dołączaniu
następnego wierzchołka do zbioru wierzchołków juz pokolorowanych.
Przy tym na każdym kroku staramy się używać możliwie najmniejszej
liczby kolorów.
Niech v

1

, v

2

, , v

n

będzie pewnym uporządkowaniem wierzchołków

grafu. Rozpatrujemy etap na którym wierzchołki v

1

, v

2

, , v

k-1

już

zostały pokolorowane. Dla v

k

należy dobrać kolor, który nie ma żaden

z jego sąsiadów, przy tym o mozliwie niskim numerze.
Formalnie algorytm ten zapiszemy w postaci

Algorytm prosty sekwencyjny (S) -pseudokod
// f (v

i

) – kolor wierzchołka v

i

begin
f (v

1

):=1;

for i:= 2, 3, ..., n do
f (v

i

):=min(k: k

≥ 1 i f (v

j

)

≠ k

dla każdego v

j

będącego sąsiadem v

i

)

end;

Przykład 2
Graf z rys 6

Dane do programu:
Graf 6 wierzcholkow
Syslo, rys. 4.3 str 328

6

//liczba wierzcholkow

v l.sąs.

sasiedzi

1

3

2 4 5

2

4

1 3 5 6

3

2

2 6

4

2

1 5

5

4

4 2 1 6

6

3

2 3 5

1

6

2

5

4

3

Rys. 6 Graf, 6 wierzchołków (Sysło, str 328)

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

8

Wyniki
prosty algorytm sekwencyjny
wierzchołek 1 otrzymuje kolor 1 (inicjalizacja)
przy wyborze koloru dla każdego następnego wierzchołka kierujemy się
tablicą logiczną określającą czy dany kolor jest zajęty przez
któregokolwiek sąsiada (1) czy jest wolny (0).
2

tabl kol 100000 wybrany 2

3

tabl kol 010000 wybrany 1

4

tabl kol 100000 wybrany 2

5

tabl kol 110000 wybrany 3

6

tabl kol 111000 wybrany 4

Wyznaczone kolory wierzchołków (v_kolor(v))
1_ 1

2_ 2

3_ 1

4_ 2

5_ 3

6_ 4

koniec obliczeń

Przykład 3
Przykład ten pokazuje że algorytm może dać dalece niezadowalające
wyniki.
Graf dwudzielny G

2,n

(rys 7 )

Rys. 7 Graf dwudzielny G

2,n

Wierzchołki grafu są podzielone na dwa zbiory:
U zawierający u

i

oraz V zawierający v

i

, i = 1,2, ..., n.

Zbiór krawędzi tego grafu: E = { (u

i

, v

j

) dla i

≠ j.}

Obliczenia zostały wykonane dla n=5.
Graf ma 10 wierzchołków, które ponumerowano w kolejności :
u

1

, v

1

, u

2

, v

2

, ..., u

5

, v

5

.

u

1

u

2

u

3

u

n

v

1

v

n

v

3

v

2

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

9

prosty algorytm sekwencyjny
Start z wierzchołka u

1

=1 – wierzchołek ten otrzymuje kolor 1.

2

tabl kol 000000

wybrany 1

3

tabl kol 100000

wybrany 2

4

tabl kol 100000

wybrany 2

5

tabl kol 110000

wybrany 3

6

tabl kol 110000

wybrany 3

7

tabl kol 111000

wybrany 4

8

tabl kol 111000

wybrany 4

9

tabl kol 111100

wybrany 5

10 tabl kol 111100

wybrany 5

kolory wierzcholkow – wynik końcowy (v_kolor(v))
1_ 1

2_ 1

3_ 2

4_ 2

5_ 3

6_ 3

7_ 4

8_ 4

9_ 5

10_ 5

Nie jest to najlepszy wynik, ponieważ graf jest dwudzielny a więc
optymalne kolorowanie wymaga użycia tylko dwóch kolorów.

Algorytm sekwencyjny przy uporzadkowaniu LF (largest-first)
Róznica w porównaniu z prostym algorytmem sekwencyjnym polega
jedynie na wczesniejszym uporządkowaniu wierzchołków grafu. Są one
porządkowane tak, by ciąg stopni wierzchołków był nierosnący (od
największego do najmniejszego).

Przykład 4
Algorytm LF zastosowany do grafu z przykładu 2 (rys 6 ).
wynik porządkowania v_stopień[v]
2_4, 5_4, 1_3, 6_3, 3_2, 4_2
Przebieg kolorowania jest podany dla numerów ciągu
uporządkowanego, numer wierzchołka sprzed porządkowania są
umieszczne w nawiasach kwadratowych.
Wyznaczanie kolorów – start:
wierzchołek 1 [2] otrzymuje kolor 1
2 [5]

tabl kol 100000 wybrany 2

3 [1] tabl kol 110000 wybrany 3

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

10

4 [6] tabl kol 110000 wybrany 3
5 [3] tabl kol 101000 wybrany 2
6 [4] tabl kol 011000 wybrany 1
wyznaczone kolory wierzcholkow: v_kolor(v)
2_1 5_2 1_3 6_3 3_2 4_1
Wystarczyły 3 kolory, zamiast 4 użytych w przykładzie 3

Przykład 5
Algorytm zastosowany do grafu dwudzielnego G

2,5

z przykładu 3 (rys.

7, 8 ) niczego nowego nie wnosi. Wszystkie wierzchołki tego grafu są
stopnia 4, więc porządkowanie niczego nie zmienia. Przykład ten
pokazuje, że wynik kolorowania może być równie niezadowalający jak
w prostym algorytmie sekwencyjnym.

Algorytm sekwencyjny z wymianą kolorów.

Jest to algorytm, w którym dopuszcza się zmianę kolorów wcześniej
pomalowanych wierzchołków grafu. Rozpatrzmy etap, na którym
nadajemy kolor wierzchołkowi v

i

. Wierzchołki v

1

, v

2

, ... , v

i-1

już mają

nadane kolory, do czego użyto k kolorów.

Rozpatrujemy podgraf G

i

złożony z sąsiadów wierzchołka v

i

.

Załózmy przy tym, że do malowania wierzchołków tego podgrafu
zostały wykorzystane wszystkie dotychczas użyte kolory 1, 2, .., k.
W takim przypadku prosty algorytm sekwencyjny wymaga użycia
nowego koloru k+1.
Jeżeli G

i

jest grafem pełnym stopnia k, to do kolorowania wierzchołka

v

i

konieczne jest uzycie nowego, k+1 koloru. W przeciwnym przypadku

mamy możemy liczyć na to, ze wymiana pewnej pary kolorów we
wcześniej pomalowanej części grafu zwolni jeden z kolorów użytych do
malowania wierzchołków podgrafu G

i

(sąsiadów v

i

).

Przyjmujemy oznaczenia

- f (u) – kolor wierzchołka u
- G

p, q

oznacza podgraf indukowany przez wierzchołki

pomalowane kolorami p, q.

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

11

- U

p

– zbiór wierzchołków tych składowych spójnosci grafu,

które zawierają sąsiada v wierzchołka v

i

, o kolorze p (f (v)= p)

- (p, q) zamiana - dla każdego u

∈ U

p

stosujemy zamianę:

jezeli f (u) =p to f (u):=q a jeżeli f (u) =q to f (u):=p;

- przyjęte uporządkowanie wierzchołków: v

1

, v

2

, ... , v

n

Algorytm sekwencyjny z wymianą - pseudokod

begin
f (v

1

):=1; k:=1;

for i:= 2, 3, ... , n do
begin

g:= min(h: h

≥1 i f(u) ≠h dla każdego u będącego sąsiadem v

i

)

if g

≤ k then f (v

i

):=g

else
if można zastosować (p, q) zamianę dla pewnych kolorów p i q

takich, że

1

≤ p, q ≤ k,

p < q

then

begin zamienić kolory w G

p, q

; f (v

i

):=p end

else begin f (v

i

):=g; k:=k+1 end;

end;
end;

Przykład 6

Graf dwudzielny G

2,n

z przykładów 3, 5 (rys 7, 8 ), dla n=5.

dane
v

sąsiedzi v

1: 4 6 8 10 /
2: 3 5 7 9 /
3: 2 6 8 10 /
4: 1 5 7 9 /
5: 2 4 8 10 /
6: 1 3 7 9 /
7: 2 4 6 10 /
8: 1 3 5 9 /

1

3

5

7

9

2

10

8

6

4

Rys 8 Graf dwudzielny G

2, 5

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

12

9: 2 4 6 8 /
10: 1 3 5 7 /

algorytm sekwencyjny z wymianą
g - kolor wybrany k – liczba kol uzytych

start – kolor wierzcholka i=1 przyjęty g=1
i=2 tabl kol dla sasiadow 000000 g= 1 k= 1
i=3 tabl kol dla sasiadow 100000 g= 2 k= 1
i=4 tabl kol dla sasiadow 100000 g= 2 k= 2
i=5 tabl kol dla sasiadow 110000 g= 3 k= 2

i= 5 wymiana kolorow 1 z 2 dla wierzchołków 2 3

Rys 9. Wymiana kolorów w podgrafie grafu G

2,5

i=5 tabl kol dla sasiadow 010000 g= 1 k= 2

i=6 tabl kol dla sasiadow 100000 g= 2 k= 2
i=7 tabl kol dla sasiadow 010000 g= 1 k= 2
i=8 tabl kol dla sasiadow 100000 g= 2 k= 2
i=9 tabl kol dla sasiadow 010000 g= 1 k= 2
i=10 tabl kol dla sasiadow 100000 g= 2 k= 2

wyznaczone kolory wierzcholkow (v_kolor(v))
1_1 2_2 3_1 4_2 5_1 6_2 7_1 8_2 9_1 10_2

10

1(1)

3{2}

5[3]

2{1}

4(2)

1(1)

3(1)

5[1]

2(2)

4(2)

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

13

Algorytm sekwencyjny z nawrotami.

Algorytm ten jest modyfikacją zwykłego algorytmu sekwencyjnego,
która pozwala uzyskać optymalne kolorowanie grafu. Przed
kolorowaniem każdego wierzchołka ustala się zbiór kolorów
dopuszczalnych – zależny od różnych ograniczeń, w tym od przyjętego
kolorowania poprzednich wierzchołków (o niższych numerach)
sąsiadujących z bieżącym.
Niżej zostały podane ograniczenia, które pozwalają wykluczyć
pokolorowania nieoptymalne lub równoważne. Przyjmiemy, że
kolorowanie wierzchołków jest zgodne z pewnym uporządkowaniem
wierzchołków v

1

, v

2

, ... , v

n

.

Kolor wierzchołka v

i

, j = f (v

i

) spełnia ograniczenia

1. j

≤ min ( i, deg(v

i

) +1)

2. j

≤ l ( i-1) +1, gdzie l ( i-1) = max (f (v

k

) , k =1,..., i-1)

3. j

≠ f (u) dla każdego u będącego sąsiadem wierzchołka v

i

4. jeżeli zostało juz znalezione q-pokolorowanie i szukamy
lepszego, to j

≤ q-1

Dalsze ograniczenia dla koloru każdego wierzchołka otrzymujemy w
miarę kolorowania wierzchołków, uwzględniając kolory sąsiadów -
w ten sposób dla każdego wierzchołka v

i

otrzymujemy zbiór

wierzchołków dopuszczalnych U

i

.

Przykład 7
Dla grafu z przykładów 2, 4, pokazanego na rys. 6, ograniczenia
numerów kolorów wynikające z warunków 1, 2 pokazuje tabelka 1

tabela 1
i

1 2 3 4 5 6

deg(i)

3 4 2 2 4 3

l ( i -1)

0 1 2 3 3 4

górne ( j = f ( i)) 1 2 3 3 4 4

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

14

Dalsze ograniczenia wynikają z uwzględnienia sąsiedztwa
wierzchołków - stąd dla wierzchołków 1 i 2 kolory są zdeterminowane, f
(1) =1 i f (2) = 2. Dalsze ograniczenia wynikające z sąsiedztwa są
uzależnione od dokonanego wyboru ze zbioru kolorów dopuszczalnych
dla każdego wierzchołka. Przykład kolorowania przedstawia tabelka 2.
W tabeli tej wybrany kolor został podany w kolumnie 2, bezpośrednio
obok numeru wierzchołka, w następnej kolumnie zbiór kolorów
dopuszczalnych, a dalsze kolumny wyjaśniają dlaczego właśnie taki
zbiór kolorów dopuszczalnych.

tabela 2

i wybrany f (i)

kolory

∈U

i

sąsiedzi u < i

kolory sąsiadów

max f (i)

1

1

1

-

-

1

2

2

2

1

1

2

3

1

1, 3

2

2

3

4

2

2, 3

1

1

3

5

3

3, 4

1, 2, 4

1, 2

4

6

4

4

2, 3, 5

2, 1, 3

4

Zostało wyznaczone kolorowanie przy wykorzystaniu q = 4 kolorów.
Czy można wyznaczyć lepsze pokolorowanie? Trzeba sprawdzić, czy
wybór kolorów dla wierzchołków 3, 4,5 był optymalny. Wracamy do
wierzchołka 3 i dokonujemy nowego wyboru – stosujemy nizej opisany
algorytm.

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

15

Algorytm sekwencyjny z nawrotami- pseudokod

begin

{ k jest numerem rozpatrywanego wierzchołka, q – liczba kolorow

użytych w najlepszym jak dotąd rozwiązaniu,

l – liczba kolorów w

bieżacym pokolorowaniu częściowym,

l [k] - wartoscią l dla

wierzchołka v[k],

lowerbound – wartością dolnego oszacowania

liczby chromatycznej kolorowanego grafu

}

l:=1; k:= 1; f(v[1]):=1; q:=n+1;
increse:= true;
{increase ma wartosc true dla kroku w przod i false dla kroku w
tył – tu krok w przod} repeat
if increase then
begin

l[k]:=l; k:=k+1;

znaleźć zbiór kolorów dopuszczalnych U

k

;

end;

if U

k

= (pusty)

begin
k:=k-1;

l:= l[k]; increase := false;

end else
begin
j:= najmniejsza liczba w U

k

;

U

k

:=U

k

– {j};

f

(v[k]) := j;

if j > l then l:=l +1;
if k < n then increase : = true
else
begin

{znaleziono nowe, lepsze

rozwiazanie }

zapamietac aktualne rozwiazanie;
znalezc najmniejsze i takie, ze f (v[i]) = l ;

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

16

usunac kolory

l, l +1, ... , q -1 z U

1

, U

2

, ...

U

i-1

;

q:=l; l := q–1; k:=i-1;

increase := false;

znalezc najmniejsze i takie, ze f (v[i]) =

l ;

end
end { U

k

<> (pusty) }

until (k=1) or (q = lowerbound)

end;


Przykład 8

W poprzednim przykładzie dla grafu z rys.6 znaleziono 4-
pokolorowanie.
Szukamy teraz lepszego pokolorowania, przy użyciu 3 kolorów.
Ograniczenia podane w tabelce 1 zmieniają się po wprowadzeniu
warunku 4 - zmienia to jedynie maksymalne wartości kolorów dla
wierzchołków 5 i 6 - teraz wartość ta jest równa 3. Maksymalne
wartości numerów kolorów dla poszczególnych wierzchołków podaje
tabela 3.

tabela 3
i

1 2 3 4 5 6

górne ( j = f ( i)) 1 2 3 3 3 3

Zaczniemy zmianę kolorowania od wierzchołka 4 - wybieramy f(4) = 3
zamiast poprzednio wybranego koloru 2. Wtedy jednak sąsiedzi
wierzchołka 5 już mają wszystkie dopuszczalne kolory - 1,2,3, więc brak
koloru dla wierzcholka 5.
Zmiany nalezy więc zacząć od wierzchołka 3 - efekty pokazuje tabela 3.

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

17

tabela 4
i wybrany f (i) kolory

∈U

i

sąsiedzi u < i kolory sąsiadów max f (i)

1

1

1

-

-

1

2

2

2

1

1

2

3

3

1, 3

2

2

3

4

2

2, 3

1

1

3

5

3

3

1, 2, 4

1, 2

3

6

1

1

2, 3, 5

2, 3

3

Graf został pokolorowany przy użyciu 3 kolorów.
Jest to najmniejsza z możliwych liczb kolorów, bo graf zawiera kliki
liczące po 3 wierzchołki ((1, 2, 5), (1, 4, 5), (6, 2, 3), (6, 2, 5)).

Przykład 9

Rys. 10 Graf dwudzielny G

2, 4

.

Wstępne ograniczenia wartości kolorów dla poszczególnych
wierzchołków, wybikające z warunków 1-3 są zestawione w tabeli 5

tabela 5
i

1 2 3 4 5 6 7 8

deg(i)

3 3 3 3 3 3 3 3

l ( i -1)

0 1 2 3 3 4 4 4

górne ( j = f ( i)) 1 2 3 4 4 4 4 4

a) pierwsza próba kolorowania została zapisana w tabeli 6

Zatem zostało wyznaczone 4-kolorowanie grafu

f: {1, 2, 3, 4, 5, 6, 7, 8}

→ {1, 1, 2, 2, 3, 3, 4, 4}

1

2

3

5

7

4

6

8

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

18

tabela 6
i wybrany f

(i)

kolory

∈U

i

sąsiedzi u <

i

kolory
sąsiadów

max f
(i)

1

1

1

-

-

1

2

1

1, 2

-

-

2

3

2

2, 3

2

1

3

4

2

2, 3, 4

1

1

4

5

3

3, 4

2, 4

1, 2

4

6

3

3, 4

1, 3

1, 2

4

7

4

4

2, 4, 6

1, 2, 3

4

8

4

4

1, 3, 5

1, 2, 3

4

b) Szukamy lepszego pokolorowania, przy użyciu 3 kolorów. Mamy

więc nowe ograniczenia na numery kolorów wierzchołków (tab 7)

tabela 7
i

1 2 3 4 5 6 7 8

górne ( j = f ( i)) 1 2 3 3 3 3 3 3

Zmiany kolorowania trzeba zacząć nie później niz od wierzchołka 4.
Jeżeli bowiem zostawimy kolor wierzchołka 4 bez zmian, to jedynym
kolorem w zbiorze U

5

będzie 3, a wtedy przy ograniczeniu f (v)

≤ 3

braknie kolorów dla wierzchołka 8 (poprzednio pozostał jedynie kolor 4).

tabela 8
i

wybrany f (i) kolory

∈U

i

sąsiedzi u < i kolory sąsiadów max f (i)

1

1

1

-

-

1

2

1

1, 2

-

-

2

3

2

2, 3

2

1

3

4

3

2, 3

1

1

3

5

2

2

2, 4

1, 3

3

6

3

3

1, 3

1, 2

3

7

2

2

2, 4, 6

1, 3

3

8

3

3

1, 3, 5

1, 2

3

Dla grafu z rys. 10 zostało więc wyznaczone 3-pokolorowanie (rys.11)

f: {1, 2, 3, 4, 5, 6, 7, 8}

→ {1, 1, 2, 3, 2, 3, 2, 3}

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

19

Rys. 11 Graf dwudzielny G

2,4

i jego 3-pokolorowanie

c) Następny etap to próba wyznaczenia 2- pokolorowania.

Postępując podobnie jak poprzednio, otrzymujemy

f: {1, 2, 3, 4, 5, 6, 7, 8}

→ {1, 2, 1, 2, 1, 2, 1, 2}

Przebieg obliczeń:

Wstępne ograniczenia dla kolorów wierzchołków podaje tabela 9.

tabela 9
i

1 2 3 4 5 6 7 8

górne ( j = f ( i)) 1 2 2 2 2 2 2 2

Jak można zauważyć, zmiany należy zacząć juz od kolorowania

wierzcholka 2.

tabela 10
i wybrany f

(i)

kolory

∈U

i

sąsiedzi u <

i

kolory
sąsiadów

max f
(i)

1

1

1

-

-

1

2

2

1, 2

-

-

2

3

1

1

2

2

2

4

2

2

1

1

2

5

1

1

2, 4

2

2

6

2

2

1, 3

1

2

7

4

1

2, 4, 6

2

2

8

4

2

1, 3, 5

1

2

1

2

3

5

7

4

6

8

1

2

2

2

1

3

3

3

dr Stefan Grabowski, Matematyka dyskretna

Kolorowanie grafów

20

Zatem zostało wyznaczone 2-kolorowanie grafu

f: {1, 2, 3, 4, 5, 6, 7, 8}

→ {1, 2, 1, 2, 1, 2, 1, 2}

Jest to najmniejsza liczba kolorów, jakiej można użyć do kolorowania
grafu, który ma chociaż jedną krawędź.

Rys. 12 Graf dwudzielny G

2,4

i jego 2-pokolorowanie

1

2

3

5

7

4

6

8

1

1

1

1

2

2

2

2