Wybrane zagadnienia teorii grafów 1000-2M12WTG
Na wykładzie omówimy szereg zagadnień ze współczesnej teorii grafów w ujęciu klasycznym, bez opisywania czy implementowania algorytmów.
1. Ekspandery. Definicja, konstrukcje, zastosowania (szkice dowodów: L=SL oraz twierdzenia PCP).
2. Teoria minorów. Tw. Robertsona-Seymoura, przykłady. Twierdzenia dekompozycyjne. Strukturalne parametry grafów (treewidth i inne).
3. Kolorowania. Metoda dischargingu. Tw. o czterech barwach. Tw. Brooksa, tw. Vizinga. Grafy doskonałe.
Rodzaj przedmiotu
Koordynatorzy przedmiotu
Efekty kształcenia
Wiedza:
Ma zaawansowaną wiedzę z trzech działów na pograniczu matematyki i informatyki:
* teoria minorów i jej zastosowania w algorytmice
* ekspandery i spektralna teoria grafów
* kolorowania grafów
(K_W01, K_W02)
W szczególności, po zajęciach student jest w stanie zrozumieć zaawansowane użycie ww. technik w studiowanym materiale (np. artykule naukowym) oraz rozpoznać potrzebe użycia tych technik w własnej pracy.
Umiejętności:
* potrafi zaaplikować nowe techniki we własnej pracy badawczej (K_U01)
* potrafi korzystać z tekstów źródłowych i podręczników w języku angielskim (K_U14)
Kompetencje
* rozumie potrzebę systematycznego zapoznawania się z czasopismami naukowymi i popularnonaukowymi w celu poszerzania i pogłębiania wiedzy (K_K08).
* potrafi precyzyjnie formułować pytania, służące pogłębieniu własnego zrozumienia danego tematu lub odnalezieniu brakujących elementów rozumowania (K_K02).
Kryteria oceniania
Będą 3 serie prac domowy, po 4 zadania każda, na podstawie których będzie wyznaczony modyfikator do oceny z egzaminu z przedziału [-1,+1.5]. Dodatkowo, po każdym wykładzie będzie do rozwiązania krótki test przez Moodle; zaliczenie wszystkich testów w terminie jest warunkiem dopuszczenia do egzaminu w pierwszym terminie. Egzamin ustny, na ocenę.
Przedmiot można zaliczać w ramach studiów doktoranckich jako przedmiot "metodologiczny"; wówczas dodatkowym warunkiem zaliczenia jest rozwiązanie co najmniej jednego najtrudniejszego (ostatniego) zadania z jednej z serii prac domowych.
Literatura
Książki:
Reinhard Diestel, Graph Theory, Springer-Verlag 2005. Wersja elektroniczna: http://diestel-graph-theory.com/GrTh.html
Bela Bollobas, Modern Graph Theory, Springer 1998.
Mike Krebs, Anthony Shaheen, Expander Families and Cayley Graphs: A Beginner's Guide, Oxford University Press, USA, 2011.
Artykuły poglądowe i materiały dydaktyczne dostępne w sieci, między innymi:
Shlomo Hoory, Nathan Linial, Avi Wigderson, Expander Graphs and Their Applications, Bulletin of AMS 2006.
http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf
Michael A. Nielsen, Introduction to Expander Graphs, 2005.
http://www.qinfo.org/people/nielsen/blog/archive/notes/expander_graphs.pdf
Laszlo Lovasz, Graph Minor Theory, Bulletin of AMS 2005.
http://www.ams.org/bull/2006-43-01/S0273-0979-05-01088-8/S0273-0979-05-01088-8.pdf
Petr Hlineny, Discharging Technique in Practice.
http://kam.mff.cuni.cz/~kamserie/serie/clanky/2000/s475.ps
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: