Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2019/2020

Základy teorie grafů A

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
01ZTGA ZK 4 4+0 česky
Přednášející:
Petr Ambrož (gar.)
Cvičící:
Předmět zajišťuje:
katedra matematiky
Anotace:

Obsahem předmětu je ucelený výklad základů moderní teorie grafů, doplněný pohledem na některé aplikace vykládané teorie.

Požadavky:
Osnova přednášek:

1. Základní pojmy teorie grafů.

2. Vrcholová a hranová souvislost (Mengerova věta).

3. Bipartitní grafy.

4. Stromy a lesy, mosty.

5. Kostry (Matrix-Tree Theorem).

6. Eulerovy cykly a tahy, Hamiltonovy kružnice.

7. Maximální a perfektní párování.

8. Hranová barevnost.

9. Toky v sítích.

10. Vrcholová barevnost.

11. Planární grafy (Kuratowského věta), barevnost planárních grafů.

12. Spektrum adjacenční matice.

13. Extremální teorie grafů.

Osnova cvičení:
Cíle studia:

Znalosti:

Pojmy z teorie grafů, jejich základní vlastnosti a vzájemné vztahy.

Schopnosti:

Použití uvedené teorie při modelování a řešení konkrétních otázek a úloh.

Studijní materiály:

Povinná literatura:

[1] J.A. Bondy, U.S.R. Murty: Graph theory. Graduate Texts in Mathematics 244. Springer, New York, (2008).

Doporučená literatura:

[2] R. Diestel: Graph theory. Graduate Texts in Mathematics 173. Springer-Verlag, Berlin, (2005).

[3] L. Lovasz, M.D. Plummer: Matching Theory. North-Holland Publishing Co., Amsterdam, (1986).

Poznámka:
Rozvrh na zimní semestr 2019/2020:
Rozvrh není připraven
Rozvrh na letní semestr 2019/2020:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 15. 9. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet24524505.html