Optymalizacja dyskretna. Modele i metody kolorowania grafów

Marek Kubale

Uzyskaj dostęp

ISBN/ISSN:

83-204-2747-9

DOI:

Wydawnictwo:

Wydawnictwo WNT

Rok wydania:

2002

Liczba stron:

279

XML:ISBN/ISSN:

ONIX MARC21

Bibliografia:

. Optymalizacja dyskretna. Modele i metody kolorowania grafów. Red. Kubale, Marek . Warszawa: Wydawnictwo WNT, 2002, 279 s. ISBN 83-204-2747-9

Bibliografia refWorks:

RT Book, Whole

SR Electronic(1)

A2 Kubale, M.

T1 Optymalizacja dyskretna. Modele i metody kolorowania grafów

PB Wydawnictwo WNT

PP Warszawa

YR 2002

SN 83-204-2747-9

Bibliografia BibTex:

@Book{ 466, author = "", editor = "Kubale, Marek", title = "Optymalizacja dyskretna. Modele i metody kolorowania grafów", publisher = "Wydawnictwo WNT", year = "2002", address = "Warszawa", isbn = "83-204-2747-9" }

Bibliografia endNote:

TY - BOOK

AU -

ED - Kubale, Marek

TI - Optymalizacja dyskretna. Modele i metody kolorowania grafów

PB - Wydawnictwo WNT

CY - Warszawa

PY - 2002

SN - 83-204-2747-9

ER -

Netografia (standard APA):

. Red. Kubale, Marek. Optymalizacja dyskretna. Modele i metody kolorowania grafów [baza danych online] Warszawa: Wydawnictwo WNT, 2002 [dostęp: 04 07 2024]. Dostęp w Ibuk Libra: https://libra.ibuk.pl/reader/optymalizacja-dyskretna-modele-i-metody-kolorowania-grafow-marek-kubale-466.

kolorowanie grafów, grafy, telekomunikacja światłowodowa, organizacja produkcji, telefonia komórkowa

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...

Więcej

ISBN/ISSN:

83-204-2747-9

DOI:

Wydawnictwo:

Wydawnictwo WNT

Rok wydania:

2002

Liczba stron:

279

XML:ISBN/ISSN:

ONIX MARC21

Przedmowa redaktora naukowego6
Bibliografia10
Rozdział 1. Klasyczne kolorowanie grafów 1 (Krzysztof Manuszewski)12
1.1. Podstawowe pojęcia i definicje13
1.1.1. Rodziny grafów15
1.1.2. Analiza metod przybliżonych16
1.2. Klasyczne kolorowanie wierzchołków19
1.2.1. Złożoność problemu oraz najprostsze oszacowania19
1.2.2. Najczęściej spotykane metody przybliżone21
1.2.3. Znane benczmarki29
1.3. Kolorowanie krawędzi30
1.3.1. Złożoność problemu oraz najprostsze oszacowania31
1.3.2. Typowe metody przybliżone - znane wyniki32
1.3.3. Metoda NTL33
Bibliografia35
Rozdział 2. Metaheurystyki w kolorowaniu grafów (Dariusz Szyfelbein)37
2.1. Wprowadzenie38
2.1.1. Warunki zakończenia algorytmu39
2.1.2. Reprezentacja39
2.1.3. Funkcja kosztu40
2.2. Symulowane wyżarzanie41
2.2.1. Generowanie nowego rozwiązania43
2.2.2. Schematy schładzania43
2.3. Przeszukiwanie tabu45
2.3.1. Sąsiedztwo oraz generowanie nowego rozwiązania46
2.4. Algorytmy genetyczne47
2.4.1. Populacja początkowa i selekcja osobników49
2.4.2. Operatory rekombinacji50
2.4.3. Algorytmy hybrydowe55
2.5. Algorytmy mrówkowe56
2.6. Podsumowanie60
Bibliografia61
Rozdział 3. Kolorowanie w trybie on-line (Piotr Borowiecki)64
3.1. Kolorowanie on-line a kolorowanie off-line65
3.2. Podstawowe algorytmy kolorowania on-line67
3.2.1. Algorytm zachłanny First-Fit67
3.2.2. Algorytm LST68
3.3. Pesymistyczna efektywność algorytmów kolorowania on-line69
3.3.1. Oszacowania dla dowolnych algorytmów70
3.3.2. Efektywność algorytmu LST71
3.3.3. Efektywność algorytmu First-Fit72
3.4. Oczekiwana efektywność algorytmów kolorowania on-line72
3.5. Kolorowanie on-line grafów przecięć zbiorów74
3.6. Zastosowania w zarządzaniu zasobami77
3.6.1. Dynamiczny przydział przestrzeni77
3.6.2. Przydział kanałów transmisyjnych w sieci optycznej typu WDM79
Bibliografia80
4.1. Sprawiedliwe kolorowanie wierzchołków83
Rozdział 4. Sprawiedliwe kolorowanie grafów (Hanna Furmańczyk)83
4.1.1. Algorytmy wielomianowe94
4.2. Sprawiedliwe kolorowanie krawędzi96
4.3. Sprawiedliwe kolorowanie totalne99
Bibliografia102
5.1. Definicje i podstawowe własności sumy chromatycznej104
Rozdział 5. Sumacyjne kolorowanie grafów (Michał Małafiejski)104
5.2. Złożoność problemu sumy chromatycznej109
5.2.1. Przypadki NP-trudne110
5.2.2. Wielomianowe algorytmy optymalne i przybliżone112
5.3. Uogólnienia problemu sumy chromatycznej117
5.3.1. Problem sumacyjnego kolorowania z kosztami117
5.3.2. Suma multichromatyczna118
5.4. Wybrane zastosowania sumychromatycznej119
Bibliografia120
6.1. Rozpiętości123
Rozdział 6. Kontrastowe kolorowanie grafów (Robert Janczewski)123
6.2. Zbiory odległości zakazanych126
6.3. Pokolorowania kontrastowe129
6.4. T rozpiętości i liczba T chromatyczna130
6.5. Homomorfizmy i T grafy132
6.6. Oszacowania i wartości dokładne134
6.7. Złożoność obliczeniowa136
6.7.1. Liczba T chromatyczna136
6.7.2. T rozpiętość137
6.7.3. T rozpiętość krawędziowa137
6.8. Algorytmy przybliżone137
6.8.1. Algorytm T LF137
6.8.2. Algorytm T SL138
6.8.3. Algorytm T DSATUR139
6.9. Zastosowania139
Bibliografia140
Rozdział 7. Harmoniczne kolorowanie grafów (Marek Kubale)143
7.1. Wprowadzenie144
7.2. Rodziny grafów o znanej harmonicznej liczbie chromatycznej146
7.3. Oszacowania harmonicznej liczby chromatycznej dla grafów ogólnych150
7.4. Algorytm degresywny151
7.5. Zastosowania153
Bibliografia156
8.1. Cyrkularne kolorowanie wierzchołków158
8.1.1. Cyrkularna liczba chromatyczna i jej własności158
Rozdział 8. Cyrkularne kolorowanie grafów (Adam Nadolski)158
8.1.2. Wyznaczenie Xc(G) dla niektórych klas grafów161
8.1.3. Cyrkularne kolorowanie grafów obciążonych164
8.1.4. Zastosowanie cyrkularnego kolorowania wierzchołków165
8.2. Cyrkularne kolorowanie krawędzi166
8.2.1. Cyrkularny indeks chromatyczny166
8.2.2. Zastosowanie cyrkularnego kolorowania krawędzi167
8.2.3. Podstawowe własności169
Bibliografia176
Rozdział 9. Zwarte kolorowanie krawędzi (Krzysztof Giaro)178
9.1. Podstawowe własności modelu179
9.2. Zwarcie kolorowalne grafy dwudzielne185
9.3. Rozpiętość zwartego kolorowania190
9.4. Deficytowość grafów193
Bibliografia199
Rozdział 10. Kolorowanie ścieżek w grafach (Jakub Białogrodzki)201
10.1. Definicja kolorowania ścieżek202
10.2. Znane wyniki dotyczące kolorowania ścieżek207
10.2.1. Złożoność obliczeniowa207
10.2.2. Grafy ogólne207
10.2.3. Drogi209
10.2.4. Cykle211
10.2.5. Drzewa213
10.3. Zastosowania217
Bibliografia218
Rozdział 11. Listowe kolorowanie grafów (Konrad Piwakowski)220
11.1. Podstawowe definicje i własności221
11.2. Grafy dwudzielne i 2-wybieralne221
11.2.1. Konstrukcja Hajósa224
11.3. D-wybieralność i twierdzenie Brooksa226
11.4. Grafy planarne228
11.5. Grafy dla których x = x1229
11.6.(k, r)-wybieralność229
11.7. Listowe kolorowanie krawędzi231
Bibliografia234
Rozdział 12. Ramseyowskie pokolorowania grafów pełnych (Tomasz Dzido)236
12.1. Podstawowe oznaczenia i defnicje237
12.2. Twierdzenie Ramseya i defnicje liczb Ramseya238
12.3. Wartości i własności klasycznych liczb Ramseya240
12.4. Nieklasyczne liczby Ramseya247
12.4.1. Liczby Ramseyadla grafów pełnych z usuniętą jedną krawędzią247
12.4.2. Ogólne grafowe liczby Ramseya249
12.4.3. Liczby Ramseya dla s-jednostajnych hipergrafów250
12.5. Zastosowania liczb Ramseya250
12.5.1. Przykład algebraicznego wykorzystania liczb Ramseya251
12.5.2. Przykład geometrycznego wykorzystania liczb Ramseya252
Bibliografia254
13.1. Wprowadzenie256
Rozdział 13. Planowanie rozmieszczenia strażników w galeriach sztuki metodą kolorowania grafów (Paweł Żyliński)256
13.2. Problem galerii sztuki258
13.3. Galerie dowolnego kształtu bez dziur259
13.4. Galerie ortogonalne bez dziur263
13.5. Ortogonalne galerie z dziurami266
13.5.1. Liczba strażników niezależna od liczby dziur267
Bibliografia270
Skorowidz271
Wykaz oznaczeń277

1.KLASYCZNEKOLOROWANIEGRAFÓW

Ponieważwielenowychalgorytmówrealizującychprzybliżonekolo-

rowaniegrafówkorzystazróżnychpodejść,częstozdeterminowanychspe-

cyﬁkąproblemu,trudnościąsamąwsobiestajesiętestowanieefektyw-

nościtakichalgorytmów.Możliwesągeneralniedwarozsądne,niewyklu-

czającesiępodejścia.Pierwszeznichpoleganadoborzetakichrodzin

grafówtrudnych,którewiążąsięzdedykowanymimetodamikolorowa-

nia,stosowanymidladanejklasyproblemów,lubtakichrodzingrafów

trudnych,którewiążąsięzcharakterystycznymikonﬁguracjamidanych

wejściowych.Wdrugimpodejściuzakładasięoddzielneposzukiwanie

iwykorzystywaniegrafówtrudnychdlacałychrodzinmetod.Grafytakie

będziemynazywaćbenczmarkami.Wanalogicznysposóbzdeﬁniujemy

słabebenczmarki,tj.grafydośćtrudnedokolorowaniadlawielualgoryt-

mów.

DEFINICJA1.21.NiechA={A1,

...,Ak}będzierodzinąalgorytmówko-

lorowaniagrafów.GrafGnazywamybenczmarkiem(ang.benchmark)

dlarodzinyA,jeżeliGjestHCdlakażdegoAi,i=1,

...,k.GrafG

nazywamysłabymbenczmarkiem(ang.weakbenchmark)dlarodzi-

nyA,jeżeliGjestSHCdlakażdegoAi,i=1,

...,k.

Zauważmy,żedlapewnychrodzinalgorytmówbenczmarkinieist-

nieją,ponieważnieistniejądlanichgrafytrudnedokolorowania(choć

zawszeistniejągrafydośćtrudne).Zauważmyrównież,żewspomniane

podejściadoanalizymetodkolorowaniapozwalająuzyskaćinne,uzupeł-

niającesięinformacje.Testowaniemetodyprzybliżonejnaszerokiejklasie

grafówdużychrozmiarów,trudnychdlainnychmetod,lubwręcznagra-

fachogólnychpozwalaocenićnp.jakwielejestgrafówtrudnych,jakduży

procentgrafówztakiejpopulacjijestkolorowanynieoptymalnie,jakbar-

dzonieoptymalnepokolorowaniamożegenerowaćtestowanaheurystyka.

Przeglądznanychbenczmarkóworaznajmniejszychgrafówtrudnychidość

trudnychdlaróżnychmodeliorazheurystykmożnaznaleźćw[22,25].

1.2.

1.2.1.

Klasycznekolorowaniewierzchołków

Złożonośćproblemuoraznajprostszeoszacowania

Klasycznekolorowaniewierzchołkówgrafuczy—mówiącściślej—za-

danieodpowiadająceznalezieniuoptymalnegowsensieklasycznympo-

kolorowaniawierzchołkówdowolnegografu,jestproblememNP-trudnym

[7],czyli—mówiącnieformalnie—takim,któregoniemożnarozwiązać

praktyczniewczasiewielomianowym.Ojegotrudnościświadczyteżfakt,

żeskonstruowaniealgorytmuk-względnieprzybliżonegoik-absolutnie

Brak wyników

Optymalizacja dyskretna. Modele i metody kolorowania grafów

Treść książki

Znajdź bibliotekę blisko siebie, i uzyskaj dostęp do ebooka w systemie IBUK Libra