Grafy i sieci

• Druk: Warszawa, 2013
• Autor: Jacek Wojciechowski, Krzysztof Pieńkosz
• Wydawca: Wydawnictwo Naukowe PWN

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

• Kategorie:
  1. Ebooki i Audiobooki »
  2. Ebooki »
  3. Ebooki popularnonaukowe i specjalistyczne »
  4. Matematyka
• Język wydania: polski
• ISBN: 978-83-01-19323-2
• ISBN druku: 978-83-01-17436-1
• Liczba stron: 440

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