Serwisy internetowe Uniwersytetu Warszawskiego Nie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Wybrane zagadnienia teorii grafów

Informacje ogólne

Kod przedmiotu: 1000-2M09WZT Kod Erasmus / ISCED: 11.303 / (0612) Database and network design and administration
Nazwa przedmiotu: Wybrane zagadnienia teorii grafów
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla III - V roku informatyki
Przedmioty obieralne dla informatyki
Punkty ECTS i inne: (brak)
zobacz reguły punktacji
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

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.