5027720017

Matematyka, st. 2, 2009/2010

Analiza kombinatoryczna

TYP PRZEDMIOTU: DODATKOWY A

FORMA ZAJĘĆ	W	C
LICZBA GODZIN	30	30
FORMA ZALICZENIA	E	O
ECTS	7

SEMESTRY
1	2	3	4	5	6
	■		■

WYKŁADOWCA dr Ewa Drgas-Burchardt WYMAGANIA WSTĘPNE Matematyka dyskretna 1.

EFEKTY KSZTAŁCENIA

Poznanie wybranych, zaawansowanych, obiektów kombinatoiycznych oraz związków między nimi.

PROGRAM NAUCZANIA

1.    Zagadnienia minimaksowe.

2.    Dualność twierdzeń minimaksowych, grafy doskonale, rodziny refleksywne.

3.    Ekstremalne własności rodzin zbiorów.

4.    Systemy różnych reprezentantów (wersja nieskończona), selektory, selektory częściowe.

5.    Twierdzenia typu Ramsey’a..

6.    Redukowalne własności grafów.

7.    Graty' zabronione (Ramsey’a) dla własności redukowalnych. Liczności rodzin grafów zabronionych.

8.    Jednoznaczność faktoiyzacji redukowalnych własności grafów.

9.    Złożoność obliczeniowa omawianych zagadnień.

LITERATURA

•    W.Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa 1986.

•    M. Borowiecki, P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theoiy (1991), 41-68.

•    A. Farrugia, Uniąueness and compleńty of generalized coloring, PhD thesis, Waterloo, Ontario. Canada 2003.

•    I.E. Zverovich, r-bounded k-complete bipartite bihypergraphs and generalized split graphs, Discrete Mathematics 247 (2002), 261-270.

WARUNKI ZALICZENIA

Opanowanie materiału prezentowanego podczas wykładu (zdanie egzaminu). Umiejętność wykorzystania zdobytej podczas wykładu w iedzy dla potrzeb rozwiązywania nowych problemów (zaliczenie sprawdzianów).

5