Podręcznik
2. Algebra Boole’a i przekształcenia boolowskie
2.4. Kolorowanie grafu
Kolorowaniem grafu nazywamy przyporządkowanie kolorów do wierzchołków grafu w taki sposób, aby żadna para wierzchołków sąsiednich nie miała takiego samego koloru. Przykład prawidłowo pokolorowanego grafu pokazany jest na rys. 1.4.
Rys. 1.4. kolorowanie grafu
Podstawowym problemem jest zadanie obliczenia najmniejszej liczby kolorów zapewniających prawidłowe pokolorowanie grafu. Jest to tzw. liczba chromatyczna grafu. Korzystając z pojęcia maksymalnych zbiorów niezależnych można algorytm kolorowania grafu sprowadzić do wykonania następujących obliczeń:
1. Obliczyć wszystkie maksymalne zbiory niezależne MZN. Uzyskujemy Rodzinę Maksymalnych Zbiorów Niezależnych (RMZN).
2. Obliczyć pokrycie zbioru wierzchołków V minimalną liczbą maksymalnych zbiorów niezależnych (tzw. minimalne pokrycie). Minimalne pokrycie reprezentuje minimalny zbiór kolorów.
3. W uzyskanym pokryciu usunąć elementy powtarzające się.
E = {(v1, v6), (v2, v3), (v2, v4), (v2, v5), (v2, v6), (v3, v4), (v3, v6), (v5, v6)}
Rys. 1.5. Graf i jego kolorowanie
Dla grafu z rys. 1.5a należy wyznaczyć kolorowanie z minimalną liczbą kolorów. W tym celu najpierw obliczamy maksymalne zbiory niezależne: {v1, v4, v5}, {v1, v3, v5}, {v4, v6}, {v1, v2}. Następnie tworzymy minimalną podrodzinę pokrywającą zbiór V = {v1, ¼, v6}: {v1, v3, v5}, {v4, v6}, {v1, v2}. Wreszcie po usunięciu wierzchołków powtarzających się uzyskujemy zbiory rozłączne reprezentują kolorowanie: {v1, v3, v5}, {v4, v6}, {v2}, co przedstawiono na rys. 1.5b.
Na zakończenie podamy jeszcze jedną – wygodną do stosowania w praktyce – metodę obliczania maksymalnych klas zgodności.
Metoda wg par zgodnych
Niech E będzie relacją na zbiorze V = {v1, ..., vn}, tzn. zbiorem par zgodnych (sąsiednich) vi, vj: i, j Î {1, ..., n} oraz i ¹ j. Obliczenie (maksymalnych) klas zgodności w zbiorze V przy danej E sprowadza się do wykonania następujących czynności.
1. Zapisujemy elementy v w rodzinach Sj zgodnie z zasadą vi Î Sj tylko wtedy, gdy vj, vi jest parą zgodną oraz i < j.
2. Jeżeli RKZk jest rodziną klas zgodności uzyskaną w k-tym kroku algorytmu, to rodzinę RKZk+1 uzyskujemy, obliczając przecięcie każdej KZ Î RKZk ze zbiorem Sk+1. Wyróżniamy przy tym następujące przypadki:
a) Sk+1 = f i wtedy RKZk+1 jest powiększana o klasę KZ = {k+1},
b) KZ Ç Sk+1 = f wtedy klasa KZ nie ulega zmianie,
c) KZ Ç Sk+1 ¹ f wtedy powstaje nowa klasa KZ’ = KZ Ç Sk+1 È {k+1}.
W przykładzie obliczymy maksymalne klasy zgodności algorytmem korzystającym z par zgodnych. Następujące pary są zgodne: (v1, v2), (v1, v3), (v1, v5), (v2, v3), (v2, v5), (v3, v4), (v3, v5), (v3, v7), (v4, v6), (v4, v7), (v5, v6), (v6, v7). Na tej podstawie wyznaczamy zbiory Sj i tworzymy kolejne listy (rodziny RKZk ) klas zgodnych, które dla uproszczenia zapisów podawać będziemy w postaci zbiorów indeksów:
|
S1 = f |
{1} |
|
S2 = {1} |
{1, 2} |
|
S3 = {1, 2} |
{1, 2, 3} |
|
S4 = {3} |
{3, 4}, {1, 2, 3} |
|
S5 = {1, 2, 3} |
|
|
S6 = {4, 5} |
{5, 6}, {4, 6}, {1, 2, 3, 5}, {3, 4} |
|
S7 = {3, 4, 6} |
|
Dla relacji R, w której zbiór par zgodnych jest E = {(e1,e2), (e1,e3), (e1,e4), (e1,e5), (e1,e6), (e1,e7), (e2,e3), (e2,e5), (e2,e6), (e2,e7), (e3,e4), (e3,e5), (e3,e6), (e3,e8), (e4,e6), (e4,e7), (e4,e8), (e5,e6), (e5,e7), (e5,e8), (e6,e7), (e6,e8), (e7,e8)} obliczyć maksymalne klasy zgodności:
- metodą wg par zgodnych,
- metodą wg par sprzecznych.
Rozwiązanie a)
|
S1 = Æ |
e1 |
|
S2 = e1 |
e1, e2 |
|
S3 = e1, e2 |
e1, e2, e3 |
|
S4 = e1, e3 |
e1, e3, e4/e1, e2, e3 1) |
|
S5 = e1, e2, e3 |
|
|
S6 = e1, e2, e3, e4, e5 |
e1, e2, e3, e5, e6/e1, e3, e4, e6/ |
|
S7 = e1, e2, e4, e5, e6 |
e1, e2, e5, e6, e7/e1, e4, e6, e7/e1, e2, e3, e5, e6/e1, e3, e4, e6 |
|
S8 = e3, e4, e5, e6, e7 |
e5, e6, e7, e8/e4, e6, e7, e8/e3, e5, e6, e8/e3, e4, e6, e8/e1, e2, e5, e6, e7/e1, e4, e6, e7/e1, e2, e3, e5, e6/e1, e3, e4, e6 |
Rozwiązanie b)
Pary sprzeczne: (e1, e8) (e2, e4) (e2, e8) (e3, e7) (e4, e5)
(e8 + e1) (e8 + e2) (e4 + e2) (e4 + e5) (e3 + e7) = = (e8 + e1e2) (e4 + e2e5)(e3 + e7) =
= (e4e8 + e2e5e8 + e1e2e4 + e1e2e5)(e3 + e7) = e3e4e8 + e2e3e5e8 + e1e2e3e4 + e1e2e3e5 + e4e7e8 + + e2e5e7e8 + e1e2e4e7 + e1e2e5e7
W obu przypadkach maksymalne klasy zgodności są następujące:
{e1, e2, e5, e6, e7} { e1, e2, e3, e5, e6}
{e1, e4, e6, e7} {e5, e6, e7, e8}
{ e4, e6, e7, e8} { e1, e2, e3, e5, e6}
{e1, e3, e4, e6} {e3, e5, e6, e8}
{e3, e4, e6, e8}
1) Do rozdzielenia klas zgodności użyto znaku „/” (zamiast nawiasów „{” i „}”