EBOOKI WYDAWCY
Redakcja:
Wydawca:
Format:
ibuk
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.
Plik pdf ma postać skanów co uniemożliwia przeszukiwanie tekstu.
Rok wydania | 2002 |
---|---|
Liczba stron | 268 |
Kategoria | Inne |
Wydawca | Wydawnictwo WNT |
ISBN-13 | 978-83-2042-747-9 |
Numer wydania | 1 |
Język publikacji | polski |
Informacja o sprzedawcy | ePWN sp. z o.o. |
EBOOKI WYDAWCY
POLECAMY
Ciekawe propozycje
Spis treści
Przedmowa redaktora naukowego XI | |
Bibliografia XV | |
Rozdział. Klasyczne kolorowanie grafów (Krzysztof Manuszewski) | 1 |
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 | 20 |
1.3.2. Typowe metody przybliżone — znane wyniki | 21 |
1.3.3. Metoda NTL | 22 |
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 x = x? | 218 |
11.6.(k, r)-wybieralność | 218 |
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 |