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