ebook Grafy i sieci Jacek Wojciechowski, Krzysztof Pieńkosz

Wydawca: Wydawnictwo Naukowe PWN

Rok wydania: 2013

Większość książek z grafów i sieci jest pisana przez matematyków i dla matematyków. Drugi nurt to książki na poziomie popularyzatorskim. Na polskim rynku brak jest współczesnego podręcznika. Książka wypełnia tę lukę, a jej cechą wyróżniającą jest zharmonizowanie teorii z praktycznymi umiejętnościami rozwiązywania problemów.
Ze Wstępu

Książka składa się z 19 niezbyt długich rozdziałów o powtarzalnej strukturze: po części opisowej (w której są przedstawione: notacja, definicje i niezbędna teoria) są podane algorytmy, zadania oraz wykaz literatury. Około 80 procent zadań ma podane pełne rozwiązania. Intencją autorów jest, by część opisowa dawała czytelnikowi podstawy teoretyczne, część zadaniowa – umiejętności praktyczne, a algorytmu – pokazywały, w jaki sposób można zaimplementować teorie.
Zagadnienia opisane w książce:
§ definicja grafu oraz podstawowe własności, izomorfizm i podobieństwo grafów, macierzowy opis grafu, operacje na grafach,
§ drogi i spójność grafów niezorientowanych oraz zorientowanych,
§ grafy płaskie,
§ cykl Eulera i cykl Hamiltona,
§ drzewa niezorientowane i zorientowane,
§ zliczanie drzew rozpinających, oraz algorytmy znajdowania minimalnego drzewa rozpinającego (Prima i Kruskala),
§ przestrzenie wektorowe grafu,
§ modele grafowe sieci,
§ spójność i kolorowanie grafów,
§ zbiory niezależne i dominujące, skojarzenia i pokrycia,
§ sieci i przepływy (algorytm Forda-Fulkersona).

Książka jest przeznaczona dla studentów kierunków ścisłych, studiów zarówno pierwszego, jak i drugiego stopnia (politechnik i uniwersytetów).

Spis treści ebooka Grafy i sieci

Od Autorów IX

1. Definicja grafu i przykłady zastosowań 1
1.1. Podstawowe pojęcia grafów 1
1.2. Przykład zastosowań grafów 6
1.3. Literatura 20

2. Podstawowe własności grafów 21
2.1. Własności liczbowe grafu 21
2.2. Realizowalność grafu o zadanych stopniach wierzchołków 23
2.3. Typy grafów 25
2.4. Reprezentacja grafu – lista sąsiedztwa 29
2.5. Elementarne operacje na grafach 30
2.6. Zadania 30
2.7. Literatura 46

3. Izomorfizm i podobieństwo grafów 47
3.1. Izomorfizm 47
3.2. Podobieństwo grafów 52
3.3. Zadania 53
3.4. Literatura 60

4. Drogi i spójność grafów niezorientowanych 61
4.1. Drogi 61
4.2. Spójność 62
4.3. Odległość wierzchołków 65
4.4. Droga ważona 67
4.5. Zadania 68
4.6. Literatura 87

5. Drogi i spójność grafów zorientowanych 88
5.1. Drogi 88
5.2. Spójność 89
5.3. Grafy acykliczne 91
5.4. Grafy orientowalne 93
5.5. Droga w grafie ważonym 95
5.6. Zadania 99
5.7. Literatura 107

6. Grafy planarne 108
6.1. Graf planarny 108
6.2. Twierdzenie Eulera 109
6.3. Grubość grafu 110
6.4. Charakterystyka grafów planarnych 112
6.5. Zadania 113
6.6. Literatura 129

7. Cykl Eulera 130
7.1. Cykl Eulera grafu niezorientowanego 130
7.2. Cykl Eulera grafu zorientowanego 132
7.3. Algorytmy poszukiwania drogi Eulera 134
7.4. Problem chińskiego listonosza 138
7.5. Zadania 142
7.6. Literatura 154

8. Cykl Hamiltona 155
8.1. Cykl Hamiltona grafu niezorientowanego 155
8.2. Cykl Hamiltona grafu zorientowanego 161
8.3. Turnieje 162
8.4. Problem komiwojażera 164
8.5. Zadania 168
8.6. Literatura 186

9. Macierzowy opis grafu 187
9.1. Macierz sąsiedztwa 187
9.2. Macierz incydencji 190
9.3. Macierz Laplace’a 192
9.4. Graf cykliczny 194
9.5. Zadania 195
9.6. Literatura 205

10. Operacje na grafach 206
10.1. Dopełnienie grafu 206
10.2. Graf krawędziowy 207
10.3. Potęga grafu 211
10.4. Iloczyn kartezjański grafów 213
10.5. Zadania 215
10.6. Literatura 230

11. Drzewa niezorientowane 231
11.1. Drzewo niezorientowane 231
11.2. Drzewo rozpinające 235
11.3. Minimalne drzewo rozpinające 239
11.4. Algorytmy MST 240
11.5. Zadania 244
11.6. Literatura 262

12. Drzewa zorientowane 263
12.1. Drzewo zorientowane 263
12.2. Drzewo rozpinające 264
12.3. Drzewa przeszukiwań 265
12.4. Binarne drzewo poszukiwań 266
12.5. Badanie grafu w głąb 270
12.6. Badanie grafu wszerz 274
12.7. Zadania 275
12.8. Literatura 284

13. Zliczanie drzew 285
13.1. Formuła Kirchhoffa 285
13.2. Grafy regularne 287
13.3. Wielomiany generyczne 291
13.4. Przypadki szczególne 293
13.5. Zadania 294
13.6. Literatura 304

14. Własności algebraiczne grafów 305
14.1. Przestrzeń grafów częściowych 305
14.2. Przestrzenie w grafach niezorientowanych 306
14.2.1. Przestrzeń cykli 306
14.2.2. Przestrzeń przekrojów 309
14.2.3. Macierze bazowe 311
14.3. Cykle i przekroje grafu zorientowanego 315
14.3.1. Cykle grafu zorientowanego 315
14.3.2. Macierz cykli grafu zorientowanego 316
14.3.3. Przekroje grafu zorientowanego 316
14.4. Zadania 318
14.5. Literatura 327

15. Zbiory niezależne, skojarzenia i pokrycia 328
15.1. Zbiory niezależne i kliki 328
15.2. Skojarzenia 331
15.3. Pokrycie wierzchołkowe 334
15.4. Pokrycie krawędziowe 336
15.5. Zadania 338
15.6. Literatura 347

16. Kolorowanie grafów 348
16.1. Kolorowanie wierzchołków 348
16.2. Metody kolorowania wierzchołków 352
16.3. Kolorowanie krawędzi 357
16.4. Inne modele kolorowania grafów 361
16.5. Zadania 364
16.6. Literatura 374

17. Grafowe modele sieci 376
17.1. Wstęp 376
17.2. Parametry sieci 376
17.3. Modele determistyczne 380
17.4. Grafy losowe 380
17.5. Sieć Erdösa i Rényiego 380
17.6. Sieć euklidesowa 383
17.7. Sieć małego świata 386
17.8. Sieć bezskalowa 388
17.9. Zadania 393
17.10. Literatura 397

18. Spójność – twierdzenie Mengera 399
18.1. Spójność wierzchołkowa i krawędziowa grafu 399
18.2. Grafy k-spójne 402
18.3. Twierdzenie Mengera 403
18.4. Zadania 405
18.5. Literatura 414

19. Sieci przepływowe 415
19.1. Problem maksymalnego przepływu 416
19.2. Problem najtańszego przepływu 420
19.3. Zadania 423
19.4. Literatura 430

Skorowidz 431