Optymalizacja dyskretna. Modele i metody kolorowania grafów
Pod redakcją Marek Kubale
Wydawnictwa Naukowo-Techniczne, Warszawa 2002
Wydanie: pierwsze
Oprawa: twarda
Liczba stron: 268
ISBN: 83-[zasłonięte]-2747-9
Stan: bardzo dobry jak nowa

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.


0]Przedmowa redaktora naukowego[1]XI  
[1]Bibliografia[1]XV  
[0]Rozdział 1. Klasyczne kolorowanie grafów 1 (Krzysztof Manuszewski)[1] 2
[1]1.1. Podstawowe pojęcia i definicje[1] 2
[2]1.1.1. Rodziny grafów[1] 4
[2]1.1.2. Analiza metod przybliżonych[1] 5
[1]1.2. Klasyczne kolorowanie wierzchołków[1] 8
[2]1.2.1. Złożoność problemu oraz najprostsze oszacowania[1] 8
[2]1.2.2. Najczęściej spotykane metody przybliżone[1] 10
[2]1.2.3. Znane benczmarki[1] 18
[1]1.3. Kolorowanie krawędzi[1] 19
[2]1.3.1. Złożoność problemu oraz najprostsze oszacowania[1] 20
[2]1.3.2. Typowe metody przybliżone — znane wyniki[1] 21
[2]1.3.3. Metoda NTL[1] 22
[1]Bibliografia[1] 23
[0]Rozdział 2. Metaheurystyki w kolorowaniu grafów (Dariusz Szyfelbein)[1] 26
[1]2.1. Wprowadzenie[1] 27
[2]2.1.1. Warunki zakończenia algorytmu[1] 28
[2]2.1.2. Reprezentacja[1] 28
[2]2.1.3. Funkcja kosztu[1] 29
[1]2.2. Symulowane wyżarzanie[1] 30
[2]2.2.1. Generowanie nowego rozwiązania[1] 32
[2]2.2.2. Schematy schładzania[1] 32
[1]2.3. Przeszukiwanie tabu[1] 34
[2]2.3.1. Sąsiedztwo oraz generowanie nowego rozwiązania[1] 35
[1]2.4. Algorytmy genetyczne[1] 36
[2]2.4.1. Populacja początkowa i selekcja osobników[1] 38
[2]2.4.2. Operatory rekombinacji[1] 39
[2]2.4.3. Algorytmy hybrydowe[1] 44
[1]2.5. Algorytmy mrówkowe[1] 45
[1]2.6. Podsumowanie[1] 49
[1]Bibliografia[1] 50
[0]Rozdział 3. Kolorowanie w trybie on-line (Piotr Borowiecki)[1] 53
[1]3.1. Kolorowanie on-line a kolorowanie o?-line[1] 54
[1]3.2. Podstawowe algorytmy kolorowania on-line[1] 56
[2]3.2.1. Algorytm zachłanny First-Fit[1] 56
[2]3.2.2. Algorytm LST[1] 57
[1]3.3. Pesymistyczna efektywność algorytmów kolorowania on-line[1] 58
[2]3.3.1. Oszacowania dla dowolnych algorytmów[1] 59
[2]3.3.2. Efektywność algorytmu LST[1] 60
[2]3.3.3. Efektywność algorytmu First-Fit[1] 61
[1]3.4. Oczekiwana efektywność algorytmów kolorowania on-line[1] 61
[1]3.5. Kolorowanie on-line grafów przecięć zbiorów[1] 63
[1]3.6. Zastosowania w zarządzaniu zasobami[1] 66
[2]3.6.1. Dynamiczny przydział przestrzeni[1] 66
[2]3.6.2. Przydział kanałów transmisyjnych w sieci optycznej typu WDM[1] 68
[1]Bibliografia[1] 69
[0]Rozdział 4. Sprawiedliwe kolorowanie grafów (Hanna Furmańczyk)[1] 72
[1]4.1. Sprawiedliwe kolorowanie wierzchołków[1] 72
[2]4.1.1. Algorytmy wielomianowe[1] 83
[1]4.2. Sprawiedliwe kolorowanie krawędzi[1] 85
[1]4.3. Sprawiedliwe kolorowanie totalne[1] 88
[1]Bibliografia[1] 91
[0]Rozdział 5. Sumacyjne kolorowanie grafów (Michał Małafiejski)[1] 93
[1]5.1. Definicje i podstawowe własności sumy chromatycznej[1] 93
[1]5.2. Złożoność problemu sumy chromatycznej[1] 98
[2]5.2.1. Przypadki NP-trudne[1] 99
[2]5.2.2. Wielomianowe algorytmy optymalne i przybliżone[1] 101
[1]5.3. Uogólnienia problemu sumy chromatycznej[1] 106
[2]5.3.1. Problem sumacyjnego kolorowania z kosztami[1] 106
[2]5.3.2. Suma multichromatyczna[1] 107
[1]5.4. Wybrane zastosowania sumychromatycznej[1] 108
[1]Bibliografia[1] 109
[0]Rozdział 6. Kontrastowe kolorowanie grafów (Robert Janczewski)[1] 112
[1]6.1. Rozpiętości[1] 112
[1]6.2. Zbiory odległości zakazanych[1] 115
[1]6.3. Pokolorowania kontrastowe[1] 118
[1]6.4. T rozpiętości i liczba T chromatyczna[1] 119
[1]6.5. Homomorfizmy i T grafy[1] 121
[1]6.6. Oszacowania i wartości dokładne[1] 123
[1]6.7. Złożoność obliczeniowa[1] 125
[2]6.7.1. Liczba T chromatyczna[1] 125
[2]6.7.2. T rozpiętość[1] 126
[2]6.7.3. T rozpiętość krawędziowa[1] 126
[1]6.8. Algorytmy przybliżone[1] 126
[2]6.8.1. Algorytm T LF[1] 126
[2]6.8.2. Algorytm T SL[1] 127
[2]6.8.3. Algorytm T DSATUR[1] 128
[1]6.9. Zastosowania[1] 128
[1]Bibliografia[1] 129
[1]Rozdział 7. Harmoniczne kolorowanie grafów (Marek Kubale)[1] 132
[2]7.1. Wprowadzenie[1] 133
[2]7.2. Rodziny grafów o znanej harmonicznej liczbie chromatycznej[1] 135
[2]7.3. Oszacowania harmonicznej liczby chromatycznej dla grafów ogólnych[1] 139
[2]7.4. Algorytm degresywny[1] 140
[2]7.5. Zastosowania[1] 142
[2]Bibliografia[1] 145
[0]Rozdział 8. Cyrkularne kolorowanie grafów (Adam Nadolski)[1] 147
[1]8.1. Cyrkularne kolorowanie wierzchołków[1] 147
[2]8.1.1. Cyrkularna liczba chromatyczna i jej własności[1] 147
[2]8.1.2. Wyznaczenie χc(G) dla niektórych klas grafów[1] 150
[2]8.1.3. Cyrkularne kolorowanie grafów obciążonych[1] 153
[2]8.1.4. Zastosowanie cyrkularnego kolorowania wierzchołków[1] 154
[1]8.2. Cyrkularne kolorowanie krawędzi[1] 155
[2]8.2.1. Cyrkularny indeks chromatyczny[1] 155
[2]8.2.2. Zastosowanie cyrkularnego kolorowania krawędzi[1] 156
[2]8.2.3. Podstawowe własności[1] 158
[1]Bibliografia[1] 165
[0]Rozdział 9. Zwarte kolorowanie krawędzi (Krzysztof Giaro)[1] 167
[1]9.1. Podstawowe własności modelu[1] 168
[1]9.2. Zwarcie kolorowalne grafy dwudzielne[1] 174
[1]9.3. Rozpiętość zwartego kolorowania[1] 179
[1]9.4. Deficytowość grafów[1] 182
[1]Bibliografia[1] 188
[0]Rozdział 10. Kolorowanie ścieżek w grafach (Jakub Białogrodzki)[1] 190
[1]10.1. Definicja kolorowania ścieżek[1] 191
[1]10.2. Znane wyniki dotyczące kolorowania ścieżek[1] 196
[2]10.2.1. Złożoność obliczeniowa[1] 196
[2]10.2.2. Grafy ogólne[1] 196
[2]10.2.3. Drogi[1] 198
[2]10.2.4. Cykle[1] 200
[2]10.2.5. Drzewa[1] 202
[1]10.3. Zastosowania[1] 206
[1]Bibliografia[1] 207
[0]Rozdział 11. Listowe kolorowanie grafów (Konrad Piwakowski)[1] 209
[1]11.1. Podstawowe definicje i własności[1] 210
[1]11.2. Grafy dwudzielne i 2-wybieralne[1] 210
[2]11.2.1. Konstrukcja Hajósa[1] 213
[1]11.3. D-wybieralność i twierdzenie Brooksa[1] 215
[1]11.4. Grafy planarne[1] 217
[1]11.5. Grafy dla których x = xι[1] 218
[1]11.6.(k, r)-wybieralność[1] 218
[1]11.7. Listowe kolorowanie krawędzi[1] 220
[1]Bibliografia[1] 223
[0]Rozdział 12. Ramseyowskie pokolorowania grafów pełnych (Tomasz Dzido)[1] 225
[1]12.1. Podstawowe oznaczenia i de?nicje[1] 226
[1]12.2. Twierdzenie Ramseya i de?nicje liczb Ramseya[1] 227
[1]12.3. Wartości i własności klasycznych liczb Ramseya[1] 229
[1]12.4. Nieklasyczne liczby Ramseya[1] 236
[2]12.4.1. Liczby Ramseyadla grafów pełnych z usuniętą jedną krawędzią[1] 236
[2]12.4.2. Ogólne grafowe liczby Ramseya[1] 238
[2]12.4.3. Liczby Ramseya dla s-jednostajnych hipergrafów[1] 239
[1]12.5. Zastosowania liczb Ramseya[1] 239
[2]12.5.1. Przykład algebraicznego wykorzystania liczb Ramseya[1] 240
[2]12.5.2. Przykład geometrycznego wykorzystania liczb Ramseya[1] 241
[1]Bibliografia[1] 243
[0]Rozdział 13. Planowanie rozmieszczenia strażników w galeriach sztuki metodą kolorowania grafów (Paweł Żyliński)[1] 245
[1]13.1. Wprowadzenie[1] 245
[1]13.2. Problem galerii sztuki[1] 247
[1]13.3. Galerie dowolnego kształtu bez dziur[1] 248
[1]13.4. Galerie ortogonalne bez dziur[1] 252
[1]13.5. Ortogonalne galerie z dziurami[1] 255
[2]13.5.1. Liczba strażników niezależna od liczby dziur[1] 256
[1]Bibliografia[1] 259
[0]Skorowidz[1] 260
[0]Wykaz oznaczeń[1] 266