Katalog przedmiotów
Grafy i sieci
CeleCelem kształcenia jest przekazanie oraz ugruntowanie wiedzy z wybranych działów teorii grafów i przepływów w sieciach. Wykład ma zapoznać słuchaczy z podstawowymi definicjami i twierdzeniami oraz zasygnalizować szeroki zakres zastosowań omawianych kwestii w informatyce. Ćwiczenia mają wyrobić umiejętnośc korzystania z warunków podanych w twierdzeniach w trakcie badania przykładowych grafów i nauczyć formułowania praktycznych zagadnień w języku teorii grafów.
Zakres
Podstawowe pojęcia: graf i graf skierowany (rysunek grafu), graf pochodny dla grafu skierowanego, dopełnienie grafu i graf krawędziowy, stopnie wierzchołków (wierzchołki incydentne, sąsiednie, izolowane), stopień wyjściowy i wejściowy wierzchołka grafu skierowanego, podstawowe zależności wykorzystujące stopnie wierzchołków, macierz incydencji wierzchołków i krawędzi (łuków), macierz sąsiedztwa wierzchołków, izomorfizm grafów, grafy pełne, regularne, dwudzielne, planarne. Twierdzenie Kuratowskiego (homeomorfizm grafów). Drogi i cykle w grafach: droga prosta i droga elementarna (cykl elementarny), twierdzenie Diraca, spójność i silna spójność grafu (składowe spójne). Zależność liczby wierzchołków, liczby krawędzi i liczby składowych spójnych. Warunek konieczny i dostateczny dwudzielności grafu, warunki konieczne planarności grafu (wzór Eulera). Przeszukiwanie grafu w głąb i wszerz. Drogi i cykle Eulera w grafie: twierdzenie Eklera, algorytm wyznaczania drogi Eulera (Fleury’ego), drogi i cykle Eulera w grafie skierowanym. Drogi i cykle Hamiltona: związek kodu Gray’a z cyklami Hamiltona, twierdzenia o istnieniu cyklu Hamiltona w grafach dwudzielnych, warunki dostateczne na istnienie cyklu Hamiltona w grafie (tw. Diraca, Ore, Chvàtala) i w grafie skierowanym (tw. Nasha-Williamsa i Meyniela), turnieje (twierdzenie Camiona). Drzewa i lasy: drzewa rozpinające i twierdzenie Cayley’a (konstrukcja kodu Prüfera), drzewa przeglądu grafu w głąb i wszerz, cykle fundamentalne. K-spójność grafu: zbiory rozspajające, rozdzielające i rozcięcia grafu, spójność wierzchołkowa i krawędziowa grafu, drogi krawędziowo i wierzchołkowo rozłączne, twierdzenie Mengera w wersji krawędziowej i wierzchołkowej. K-spójność grafów skierowanych: separatory i konektory, uogólnione twierdzenia Mengera. Przepływy w sieciach: podstawowe definicje i stwierdzenia, minimalny przekrój i ścieżka powiększająca przepływ, twierdzenie Forda i Fulkersona, wyznaczanie maksymalnego przepływu. Skojarzenia w grafie: droga powiększająca (tw. Berge’a). Zbiory wewnętrznie stabilne. Pokrycia wierzchołkowe i krawędziowe: twierdzenia Gallai i Königa. Skojarzenia: pełne (tw. Halla) i doskonałe (tw. Tutte’a). Kolorowanie wierzchołków grafu: tw. o 4 barwach.
Literatura podstawowa
1. M. Libura, J. Sikorski: Wykłady z matematyki dyskretnej. Cz. II: Teoria grafów, WSISiZ (2003).
2. R. Wilson: Wprowadzenie do teorii grafów, PWN (2007).
Literatura uzupełniająca
1. N. Deo: Teoria grafów i jej zastosowania w technice, PWN (1980).
2. K. Ross, Ch. Wright: Matematyka dyskretna, PWN (2005).
Punkty ECTS
5 - niestacjonarne
Rodzaje studiów, na których przedmiot jest realizowany
niestacjonarne - 1-go stopnia
Specjalności, na których przedmiot jest realizowany
Informatyka w telekomunikacji,
Bazy danych,
Inżynieria oprogramowania,
Komputerowe wspomaganie grafiki,
Sieci komputerowe
Prowadzący
dr Grażyna Grygiel, dr inż. Jarosław Sikorski, dr Leszek Pysiak, mgr inż. Elżbieta Janaszewska
