Grafy. Teoria i zadania
Andrzej Nowak
rok wydania: 2006
stron: 146
oprawa: miękka
format: B5
wydawnictwo: Politechnika Śląska
Niniejsza książka stanowi pomoc dydaktyczną dla studentów matematyki i powinna przyczynić się do doskonalenia procesu nauczania przedmiotu teoria grafów. W podręczniku zamieszczono materiał teoretyczny z tego przedmiotu wraz z przykładami ilustracyjnymi oraz zadaniami do samodzielnego rozwiązania.
W książce zawarto:
- podstawowe pojęcia z Teorii grafów w formie definicji, uzupełnione ilustracjami z zakresu typizacji grafów,
- podstawy aksjomatyki grafów Berge’a, sformułowane na gruncie teorii relacji,
- najważniejsze twierdzenia z Teorii grafów, niektóre z nich również z dowodami, dotyczące własności strukturalnych grafów,
- własności metryczne grafów i digrafów,
- modele algebraiczne grafów w ujęciu algebry liczb strukturalnych i ich pochodnych algebraicznych,
- najważniejsze algorytmy Teorii grafów w zakresie wyznaczania baz grafów, chromatyki i cyklomatyki oraz łańcuchów Eulera i Hamiltona,
- zagadnienie grupy automorfizmów grafów, zilustrowane na przykładach grup symetrii i obrotów sześcianu, czworościanu i grupy kwaternionowej, wykazując również izomorfizm niektórych z tych grup z grupa Kleina.
SPIS TREŚCI:
WYKAZ OZNACZEŃ 5
WSTĘP 7
1. PODSTAWOWE POJĘCIA TEORII GRAFÓW 9
1.1. Relacja i jej własności 9
1.2. Określenie grafu 10
1.3. Izomorfizm i homeomorfizm grafów 12
1.4. Algebra grafów w opisie teorii relacji 13
1.4.1. Działania algebraiczne na grafach 13
1.4.2. Graf jako obraz relacji 16
1.5. Klasyfikacja grafów i digrafów 17
1.6. Graf dualny i sprzężony 25
1.7. Drzewa i karkasy grafu 29
1.8. Zadania do rozdziału l 32
1.9. Literatura 35
2. MACIERZOWA REPREZENTACJA I DZIAŁANIA NA GRAFACH 36
2.1. Macierze opisowe grafów 36
2.2. Macierzowa reprezentacja działań na grafach 41
2.3. Liczba strukturalna i funkcja wyznacznikowa grafu 46
2.4. Zadania do rozdziału 2 51
2.5. Literatura 54
3. WŁASNOŚCI METRYCZNE GRAFÓW I DIGRAFÓW 55
3.1. Łańcuchy i drogi w grafach 55
3.2. Metryka grafu 57
3.3. Własności metryczne digrafu 61
3.4. Twierdzenia o metryce grafów 65
3.5. Zadania do samodzielnego rozwiązania 67
3.6. Literatura 69
4. CHROMATYKAI CYKLOMATYKA GRAFÓW. ŁAŃCUCH EULERA I HAMILTONA 70
4.1. Chromatyka grafów i liczba chromatyczna 70
4.1.1. Pokrycie grafu i pokrycie minimalne. Graf chromatyczny 70
4.1.2. Algorytm Maghouta wyznaczania pokrycia chromatycznego 72
4.1.3. Algorytm Greenberga wyznaczania liczby chromatycznej grafu 75
4.1.4. Kolorowanie map. Chromatyka cyklowa grafu 75
4.2. Droga i łańcuch Eulera w grafie 77
4.3. Droga i łańcuch Hamiltona w grafie 80
4.4. Przestrzeń quasi - cykli i quasi - przekrojów 84
4.5. Zadania do samodzielnego rozwiązania 88
4.6. Literatura 90
5. WŁASNOŚCI STRUKTURALNE GRAFÓW. BAZY I SPÓJNOŚĆ 91
5.1. Pojęcia topologiczne w teorii grafów 91
5.2. Baza grafu i zbiory stabilne wewnętrznie 94
5.3. Algorytm Maghouta wyznaczania zbiorów bazowych grafu 95
5.4. Zbiory stabilne strukturalnie grafu nieskierowanego 98
5.5. Wyznaczanie zbiorów bazowych grafu metodą dekompozycji na podgrafy 100
5.6. Spójność wierzchołkowa i krawędziowa grafu 103
5.7. Pokrycie cykliczne digrafu i graf Hertza 106
5.8. Algorytm redukcji digrafu cyklicznego do grafu Hertza 108
5.8.1. Metoda zbiorów osiągalnych i kontrosiągalnych 108
5.8.2. Algorytm wyznaczania warstw digrafu metodą Leifmana 113
5.9. Baza gałęziowa grafu. Algorytm binarny Maghouta 119
5.10. Zadania do samodzielnego rozwiązania 121
5.11. Literatura 127
6. PRZEKSZTAŁCENIA HOMOMORFICZNE GRAFÓW 128
6.1. Grupa automorfizmów grafów 128
6.2. Grafy Cayleya grup cyklicznych i działań grupowych 134
6.3. Automorfizm grupy permutacji grafów 138
6.4. Endomorfizm grupy grafów 142
6.5. Grupa hamiltonowska i jej grafy 144
6.6. Literatura 146
