Matematyka dyskretna. Podstawowe metody i algorytmy teorii grafów.

Skrypt zawiera wybrane pojęcia, twierdzenia i algorytmy matematyki dyskretnej i w znacznej części jest poświęcony teorii grafów. Teoria grafów ma wiele ważnych zastosowań praktycznych w naukach technicznych, chemii, biologii molekularnej itd.

Celem skryptu jest przedstawienie wybranych metod i koncepcji matematyki dyskretnej. Zawarte są ogólne podstawy matematyczne teorii grafów, zilustrowane przykładami zastosowań. Liczba przedstawionych dowodów jest niewielka, jest natomiast zamieszczonych wiele rozwiązanych przykładów zadań. Na końcu każdego rozdziału są zadania do samodzielnego rozwiązania, a odpowiedzi do tych zadań znajdują się na końcu skryptu. Znaczna część przykładów i zadań jest autorska, pozostałe zostały zaczerpnięte z pozycji zamieszczonych w spisie literatury.

Skrypt jest przeznaczony dla studentów informatyki, ale mogą z niego skorzystać osoby interesujące się praktycznymi zastosowaniami matematyki.

Do zrozumienia zawartych tutaj treści konieczna jest podstawowa wiedza z zakresu algebry i analizy matematycznej. Prezentowane algorytmy są zapisane za pomocą pseudojęzyka, co zapewnia ich krótki i przejrzysty zapis.

SPIS TREŚCI:

Wstęp 5

1. Elementy analizy kombinatorycznej 6

1.1. Obiekty kombinatoryczne 6

1.2. Równania rekurencyjne 14

1.3. Liczby Fibonacciego 18

1.4. Funkcje tworzące 20

1.5. Systemy reprezentantów. Permanent macierzy 25

1.6. Zagadnienia optymalnego przydziału - algorytm Königa 29

1.7. Zadania 32

2. Grafy 34

2.1. Definicje i oznaczenia 34

2.2. Algebraiczna reprezentacja grafu 38

2.3. Podgrafy 40

2.4. Przykłady grafów 43

2.5. Zadania 49

3. Drogi i cykle w grafach 52

3.1. Odległość w grafie 52

3.2. Spójność grafu 56

3.3. Grafy Eulera i grafy Hamiltona 57

3.4. Zadania 64

4. Drzewa 66

4.1. Definicje i podstawowe własności 66

4.2. Drzewa binarne 73

4.3. Drzewa rozpinające 76

4.4. Zadania 84

5. Topologiczna teoria grafów 86

5.1. Grafy planarne 86

5.2. Grafy na powierzchniach 91

5.3. Zadania 94

6. Niezależność w grafie 95

6.1. Zbiory niezależne 95

6.2. Liczby Fibonacciego w grafach 98

6.3. Skojarzenia 101

6.4. Zadania 108

7. Kolorowanie grafów 110

7.1. Kolorowanie wierzchołków 110

7.2. Kolorowanie krawędzi 120

7.3. Zadania 123

8. Grafy skierowane i sieci 126

8.1. Definicje i podstawowe własności 126

8.2. Maksymalny przepływ w sieci 133

8.3. Przepływ o minimalnym koszcie 141

8.4. Zadania 144

Odpowiedzi i wskazówki 147

Literatura 150

Skorowidz 151