1. SylabUZ
2. Faculty of Mathematics, Computer Science and Econometrics
3. winter term 2022/2023
4. Mathematics - Second-cycle studies leading to MS degree
5. Topics in Discrete Mathematics 2

Generate PDF for this page

Topics in Discrete Mathematics 2 - course description

Aim of the course

Poznanie zaawansowanych pojęć matematyki dyskretnej w aspekcie teoretycznym i algorytmicznym.

Prerequisites

Save changes

Matematyka dyskretna 1, Algebra liniowa 1

Scope

Wykład/ćwiczenia

1. Hipergrafy, podstawowe własności i sposoby reprezentacji.
2. Cykle w hipergrafie.
3. Hipergrafy konformalne, własność Helly.
4. Kolorowanie hipergrafów i jego złożoność obliczeniowa.
5. Skojarzenia, pokrycie i transwersale.
6. Definicja matroidu. Przykłady i podstawowe własności matroidu.
7. Matroidy dualne. Podmatroidy.
8. Transwersale, twierdzenie Halla. Matroidy transwersalne. Twierdzenie Rado o niezależnych transwersalach.
9. Algorytm zachłanny, twierdzenie Rado-Edmondsa. Twierdzenie Kruskala.

Teaching methods

Wykład: konwencjonalny, konwersatoryjny.

Ćwiczenia: klasyczna metoda problemowa.

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

Ocena końcowa przedmiotu: średnia pozytywnych ocen z ćwiczeń i z egzaminu.

Warunkiem zaliczenia ćwiczeń jest uzyskanie pozytywnej oceny ze sprawdzianów pisemnych, aktywności na ćwiczeniach oraz przygotowanego referatu.

Warunkiem zaliczenia sprawdzianu pisemnego jest uzyskanie ustalonej dla danego sprawdzianu minimalnej liczby punktów.

Warunkiem przystąpienia do egzaminu jest uzyskanie pozytywnej z ćwiczeń.

Recommended reading

1. C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973.
2. D. J. A. Welsh, Matroid theory, Academic Press, Inc., New York, 2010.
3. R.J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 1998.

Further reading

1. J. Oxley, Matroid Theory, Oxford University Press, 2006

Notes

Modified by dr Alina Szelecka (last modification: 19-05-2022 21:45)