Wydział Matematyki i Informatyki
SEMINARIUM LICENCJACKIE
Profesor UWM Yury Muranov
TEORIA GRAFÓW I TOPOLOGIA ALGEBRAICZNA
Podstawowe poj¸ teorii grafów, sposoby prezentacji grafów,
ecia
macierz s¸
asiedztwa, macierz incydencji, typy grafów, klasy grafów,
przykłady. Izomorfizm i homomorfizm grafów (digrafów). Oper-
acje na grafach. Reprezentacja grafów przez macierze. Drzewa w
teorii grafów i ich własności. Cykly Eulera i Hamiltona w grafach.
Grafy planarne i ich własności. Niezmienniki algebraiczne w teorii
grafów. Homotopii grafów i digrafów. Problem maksymalnego
skojarzenia w grafie dwudzielnym. Przeszukiwanie grafów i sor-
towanie topologiczne. Elementy teorii kategorii, funktory, alge-
braiczne kategorii. Kategorii grafów i skierowanych grafów. Kom-
pleks łańcuchowy, homologii, kohomologii, przykłady. Grupy ho-
mologii i kohomologii dla grafów i skierowanych grafów, przykłady
obliczeń.
Tematy prac licencjackich.
Imi¸ i nazwisko studenta
e
Nr alboma
Kierunok studiów Yury Muranov
,
Specjalność Matematyka stosowana
Tryb studiów stacjonarne
Temat pracy
Tematy 2014
1
1. " Homomorfizmy i równoważność grafów.
2. " Cykly Eulera i Hamiltona w grafach.
3. " Zastosowanie grafow do zaawansowanych zagadnień matem-
atyki szkolnej.
4. " Właściwości grafów na powierzchniach.
5. " Ścieżki i cykly w grafach i grafach skierownych.
6. " Różne kategorii grafów i skierowanych grafów.
7. " Reprezentacja grafów przez macierze.
8. " Drzewa w teorii grafów i ich własności.
9. " Grafy planarne i ich własności.
10. " Algorytmy znajdowania minimalnego drzewa rozpinaj¸
acego
w grafie.
11. " Algorytmy znajdowania najkrótszej Å›cieżki mi¸ wierz-
edzy
chołkami w grafie.
12. " Kolorowanie grafów.
Tematy 2015
1. J. Bałdyga. Grupy automorfizmów grafów (podgraf, pod-
grupa, macierz s¸
asiedztwa, macierz incydencji, graf pełny, graf
dwudzielny, kostka, graf krawiendzowy, etc.).
2. M. Boczkowski. Grupy automorfizmów grafów skierowanych
(podgraf, podgrupa, macierz s¸
asiedztwa, macierz incydencji, graf
pełny, graf dwudzielny, kostka, (graf krawiendzowy?), etc.)
3. S. Dzierbun. Kategorie homotopii grafów i grafów skierowanych.
4. M. Sztybor. Algorytmy grafowe: problem maksymalnego
skojarzenia w grafie dwudzielnym i problem komiwojażera.
5. A. Tyc. Klasy homotopijnej równoważności grafów i grafów
skierowanych (cykl, simpleks, kostka, ...).
2
6. E. Szczypin. Przeszukiwanie grafów i sortowanie topolog-
iczne.
7. E. Wi¸
eckowska. Budowa nowych grafów i właściwości
indukowanych homomorfizmów (iloczyn kartezjański, iloczyn z
przek¸ a, bukiet, Å‚¸
atn¸ aczenie (join) dwóch grafów, cylinder, stożek
(konus), zawieszenie (suspension) SG grafu G, Hom(X, Y ), iloczyn
w kategorii, etc. Automorfizmy tech konstrukcij i automorfizmy
grafu. Cylinder homomorfizmu. )
8. K. Waszkiewicz. Operacje na grafach i grafach skierowanych
i ich wÅ‚aÅ›ciwoÅ›ci (iloczyn kartezjaÅ„ski, iloczyn z przek¸ a, bukiet,
atn¸
Å‚¸
aczenie (join) dwóch grafów, cylinder, stożek (konus), zawieszenie
(suspension) SG grafu G, Hom(X, Y ), iloczyn w kategorii, etc.
Automorfizmy tech konstrukcij i automorfizmy digrafu. Cylinder
homomorfizmu. Macierz nowego grafy.)
9. K. Gutowska. Grafy i macierze.
10. E. Karczewska. Deformacja ścieżkę w grafie skierowanym
i grupa podstawowa.
11. Grupy homologii grafów skierowanych.
12. BÅ‚¸
adzenie losowe na grafie.
13. Zastosowanie przestrzeÅ„ funkcjonaln¸ na grafach.
a
14. Homologii kompleksów symplicjalnych i grafy.
15. Triangulacji powierzchni i grupy homologii.
16. Zastosowanie grafów w teorii algorytmów (algorytmy grafowe).
17. M. Marcinek. Grafy i kolorowanie mapy (planarny grafy,
grafy na powierzchniach).
18. B. Lejk. Graf kraw¸
edziowy i ego własnośći.
19. A. Krzemieniewska. Liczba chromatyczna i indeks chro-
matyczny grafów (wielomian chromatyczny).
3