Wybrane zagadnienia teorii grafów
Informacje ogólne
Kod przedmiotu: | 1000-2M09WZT |
Kod Erasmus / ISCED: |
11.303
|
Nazwa przedmiotu: | Wybrane zagadnienia teorii grafów |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: |
Przedmioty obieralne dla informatyki Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka |
Punkty ECTS i inne: |
(brak)
|
Język prowadzenia: | angielski |
Rodzaj przedmiotu: | monograficzne |
Skrócony opis: |
Na wykładzie omówimy szereg zagadnień ze współczesnej teorii grafów w ujęciu klasycznym (niealgorytmicznym). |
Pełny opis: |
Na wykładzie omówimy szereg zagadnień ze współczesnej teorii grafów w ujęciu klasycznym, bez opisywania czy implementowania algorytmów. 1. Skojarzenia. Tw. Halla, tw. Tutte i zastosowania. Tw. Kotziga. Rozkład Gallai-Edmondsa. Perfect Matching Polytope. Problem liczby doskonałych skojarzeń w różnych klasach grafów. 2. Ekspandery. Definicja, konstrukcje, zastosowania. 3. Szerokości. Pathwidth, treewidth, cliquewidth i inne. 4. Kolorowania. Metoda dischargingu. Tw. o czterech barwach. Tw. Brooksa, tw. Hajnala-Szemerediego. Tw. Vizinga. 5. Teoria minorów. Tw. Robertsona-Seymoura, przykłady. Strona przedmiotu: http://www.mimuw.edu.pl/~malcin/grafy/ |
Literatura: |
Książki: Reinhard Diestel, Graph Theory, Springer-Verlag 2005. Wersja elektroniczna: http://diestel-graph-theory.com/GrTh.html Laszlo Lovasz, M.D. Plummer, Matching Theory, AMS Chelsea Publishing, 2009. Bela Bollobas, Modern Graph Theory, Springer 1998. 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 |
Właścicielem praw autorskich jest Uniwersytet Warszawski.