Optymalizacja dyskretna. Modele i metody kolorowania grafów

W książce omówiono dziewięć wybranych modeli kolorowania grafów; są to kolorowania: klasyczne, sprawiedliwe, sumacyjne, kontrastowe, harmoniczne, cyrkularne, zwarte, ścieżkowe, listowe. Wyboru modeli dokonano ze względu na możliwości ich zastosowań praktycznych w dziedzinach takich jak: szeregowanie zadań, telekomunikacja światłowodowa, technologia cienkowarstwowa, telefonia komórkowa, radionawigacja lotnicza i organizacja produkcji. Szczególny nacisk położono na konstrukcję wielomianowych algorytmów kolorowania - dokładnych bądź przybliżonych. Każdy rozdział książki został napisany przez innego Autora i jest w pewnym stopniu autonomiczny, może więc być czytany niezależnie od pozostałych. Książka jest przeznaczona dla środowiska akademickiego, przede wszystkim dla studentów i doktorantów matematyki i informatyki, a także dla osób zainteresowanych optymalizacją dyskretną, zwłaszcza programistów.

Spis treści

Przedmowa redaktora naukowego XI
Bibliografia XV

Rozdział 1. Klasyczne kolorowanie grafów 1 (Krzysztof Manuszewski) 2

1.1. Podstawowe pojęcia i definicje 2
1.1.1. Rodziny grafów 4
1.1.2. Analiza metod przybliżonych 5
1.2. Klasyczne kolorowanie wierzchołków 8
1.2.1. Złożoność problemu oraz najprostsze oszacowania 8
1.2.2. Najczęściej spotykane metody przybliżone 10
1.2.3. Znane benczmarki 18
1.3. Kolorowanie krawędzi 19
1.3.1.Złożoność problemu oraz najprostsze oszacowania
1.3.2. Typowe metody przybliżone — znane wyniki 21
1.3.3. Metoda NTL 23
Bibliografia 24

Rozdział 2. Metaheurystyki w kolorowaniu grafów (Dariusz Szyfelbein) 26

2.1. Wprowadzenie 27
2.1.1. Warunki zakończenia algorytmu 28
2.1.2. Reprezentacja 28
2.1.3. Funkcja kosztu 29
2.2. Symulowane wyżarzanie 30
2.2.1. Generowanie nowego rozwiązania 32
2.2.2. Schematy schładzania 32
2.3. Przeszukiwanie tabu 34
2.3.1. Sąsiedztwo oraz generowanie nowego rozwiązania 35
2.4. Algorytmy genetyczne 36
2.4.1. Populacja początkowa i selekcja osobników 38
2.4.2. Operatory rekombinacji 39
2.4.3. Algorytmy hybrydowe 44
2.5. Algorytmy mrówkowe 45
2.6. Podsumowanie 49
Bibliografia 50

Rozdział 3. Kolorowanie w trybie on-line (Piotr Borowiecki) 53

3.1. Kolorowanie on-line a kolorowanie o?-line 54
3.2. Podstawowe algorytmy kolorowania on-line 56
3.2.1. Algorytm zachłanny First-Fit 56
3.2.2. Algorytm LST 57
3.3. Pesymistyczna efektywność algorytmów kolorowania on-line 58
3.3.1. Oszacowania dla dowolnych algorytmów 59
3.3.2. Efektywność algorytmu LST 60
3.3.3. Efektywność algorytmu First-Fit 61
3.4. Oczekiwana efektywność algorytmów kolorowania on-line 61
3.5. Kolorowanie on-line grafów przecięć zbiorów 63
3.6. Zastosowania w zarządzaniu zasobami 66
3.6.1. Dynamiczny przydział przestrzeni 66
3.6.2. Przydział kanałów transmisyjnych w sieci optycznej typu WDM 68
Bibliografia 69

Rozdział 4. Sprawiedliwe kolorowanie grafów (Hanna Furmańczyk) 72

4.1. Sprawiedliwe kolorowanie wierzchołków 72
4.1.1. Algorytmy wielomianowe 83
4.2. Sprawiedliwe kolorowanie krawędzi 85
4.3. Sprawiedliwe kolorowanie totalne 88
Bibliografia 91

Rozdział 5. Sumacyjne kolorowanie grafów (Michał Małafiejski) 93

5.1. Definicje i podstawowe własności sumy chromatycznej 93
5.2. Złożoność problemu sumy chromatycznej 98
5.2.1. Przypadki NP-trudne 99
5.2.2. Wielomianowe algorytmy optymalne i przybliżone 101
5.3. Uogólnienia problemu sumy chromatycznej 106
5.3.1. Problem sumacyjnego kolorowania z kosztami 106
5.3.2. Suma multichromatyczna 107
5.4. Wybrane zastosowania sumychromatycznej 108
Bibliografia 109

Rozdział 6. Kontrastowe kolorowanie grafów (Robert Janczewski) 112

6.1. Rozpiętości 112
6.2. Zbiory odległości zakazanych 115
6.3. Pokolorowania kontrastowe 118
6.4. T rozpiętości i liczba T chromatyczna 119
6.5. Homomorfizmy i T grafy 121
6.6. Oszacowania i wartości dokładne 123
6.7. Złożoność obliczeniowa 125
6.7.1. Liczba T chromatyczna 125
6.7.2. T rozpiętość 126
6.7.3. T rozpiętość krawędziowa 126
6.8. Algorytmy przybliżone 126
6.8.1. Algorytm T LF 126
6.8.2. Algorytm T SL 127
6.8.3. Algorytm T DSATUR 128
6.9. Zastosowania 128
Bibliografia 129

Rozdział 7. Harmoniczne kolorowanie grafów (Marek Kubale) 132

7.1. Wprowadzenie 133
7.2. Rodziny grafów o znanej harmonicznej liczbie chromatycznej 135
7.3. Oszacowania harmonicznej liczby chromatycznej dla grafów ogólnych 139
7.4. Algorytm degresywny 140
7.5. Zastosowania 142
Bibliografia 145

Rozdział 8. Cyrkularne kolorowanie grafów (Adam Nadolski) 147

8.1. Cyrkularne kolorowanie wierzchołków 147
8.1.1. Cyrkularna liczba chromatyczna i jej własności 147
8.1.2. Wyznaczenie ?c(G) dla niektórych klas grafów 150
8.1.3. Cyrkularne kolorowanie grafów obciążonych 153
8.1.4. Zastosowanie cyrkularnego kolorowania wierzchołków 154
8.2. Cyrkularne kolorowanie krawędzi 155
8.2.1. Cyrkularny indeks chromatyczny 155
8.2.2. Zastosowanie cyrkularnego kolorowania krawędzi 156
8.2.3. Podstawowe własności 158
Bibliografia 165

Rozdział 9. Zwarte kolorowanie krawędzi (Krzysztof Giaro) 167

9.1. Podstawowe własności modelu 168
9.2. Zwarcie kolorowalne grafy dwudzielne 174
9.3. Rozpiętość zwartego kolorowania 179
9.4. Deficytowość grafów 182
Bibliografia 188

Rozdział 10. Kolorowanie ścieżek w grafach (Jakub Białogrodzki) 190

10.1. Definicja kolorowania ścieżek 191
10.2. Znane wyniki dotyczące kolorowania ścieżek 196
10.2.1. Złożoność obliczeniowa 196
10.2.2. Grafy ogólne 196
10.2.3. Drogi 198
10.2.4. Cykle 200
10.2.5. Drzewa 202
10.3. Zastosowania 206
Bibliografia 207

Rozdział 11. Listowe kolorowanie grafów (Konrad Piwakowski) 209

11.1. Podstawowe definicje i własności 210
11.2. Grafy dwudzielne i 2-wybieralne 210
11.2.1. Konstrukcja Hajósa 213
11.3. D-wybieralność i twierdzenie Brooksa 215
11.4. Grafy planarne 217
11.5. Grafy dla których ? = ?? 218
11.6.k r wybieralność
11.7. Listowe kolorowanie krawędzi 220
Bibliografia 223

Rozdział 12. Ramseyowskie pokolorowania grafów pełnych (Tomasz Dzido) 225

12.1. Podstawowe oznaczenia i de?nicje 226
12.2. Twierdzenie Ramseya i de?nicje liczb Ramseya 227
12.3. Wartości i własności klasycznych liczb Ramseya 229
12.4. Nieklasyczne liczby Ramseya 236
12.4.1. Liczby Ramseyadla grafów pełnych z usuniętą jedną krawędzią 236
12.4.2. Ogólne grafowe liczby Ramseya 238
12.4.3. Liczby Ramseya dla s-jednostajnych hipergrafów 239
12.5. Zastosowania liczb Ramseya 239
12.5.1. Przykład algebraicznego wykorzystania liczb Ramseya 240
12.5.2. Przykład geometrycznego wykorzystania liczb Ramseya 241
Bibliografia 243

Rozdział 13.Planowanie rozmieszczenia strażników w galeriach sztuki metodą

kolorowania grafów (Paweł Żyliński) 245

13.1. Wprowadzenie 245
13.2. Problem galerii sztuki 247
13.3. Galerie dowolnego kształtu bez dziur 248
13.4. Galerie ortogonalne bez dziur 252
13.5. Ortogonalne galerie z dziurami 255
13.5.1. Liczba strażników niezależna od liczby dziur 256

Bibliografia 259
Skorowidz 260
Wykaz oznaczeń 266