Grafy i sieci (Wydawnictwo Naukowe PWN)

Tytuł Grafy i sieci Autorzy Jacek Wojciechowski, Krzysztof Pieńkosz Język polski Wydawnictwo Wydawnictwo Naukowe PWN ISBN 978-83-01-19323-2 Rok wydania 2013 Warszawa Wydanie 1 ilość stron 440 Format mobi, epub Spis treści 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. Proces 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. Proces 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. Drobne 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. Właściwości 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ć śladowego ś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