POLECAMY
Wydawca:
Format:
epub, mobi
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).
Rok wydania | 2013 |
---|---|
Liczba stron | 440 |
Kategoria | Algorytmy |
Wydawca | Wydawnictwo Naukowe PWN |
ISBN-13 | 978-83-01-19323-2 |
Numer wydania | 1 |
Język publikacji | polski |
Informacja o sprzedawcy | ePWN sp. z o.o. |
POLECAMY
Ciekawe propozycje
Etno-grafie, kulturo-grafie
do koszyka
Polska, której nie znajdziecie w...
do koszyka
Wakacje poza siecią
do koszyka
Najbardziej upragnione dziecko wszech...
do koszyka
Najbardziej upragnione dziecko wszech...
do koszyka
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. 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 |