Optymalizacja dyskretna. Modele i metody kolorowania grafów

Optymalizacja dyskretna. Modele i metody kolorowania grafów

1 opinia

Redakcja:

Marek Kubale

Wydawca:

Wydawnictwo WNT

Format:

ibuk

WYBIERZ RODZAJ DOSTĘPU

 

Dostęp online przez myIBUK

WYBIERZ DŁUGOŚĆ DOSTĘPU

6,15

Wypożycz na 24h i opłać sms-em

23,00

cena zawiera podatek VAT

ZAPŁAĆ SMS-EM

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.


Liczba stron268
WydawcaWydawnictwo WNT
ISBN-13978-83-2042-747-9
Numer wydania1
Język publikacjipolski
Informacja o sprzedawcyRavelo Sp. z o.o.

Ciekawe propozycje

Spis treści

[]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
RozwińZwiń
W celu zapewnienia wysokiej jakości świadczonych przez nas usług, nasz portal internetowy wykorzystuje informacje przechowywane w przeglądarce internetowej w formie tzw. „cookies”. Poruszając się po naszej stronie internetowej wyrażasz zgodę na wykorzystywanie przez nas „cookies”. Informacje o przechowywaniu „cookies”, warunkach ich przechowywania i uzyskiwania dostępu do nich znajdują się w Regulaminie.

Nie pokazuj więcej tego powiadomienia