Teorie grafů

Garant předmětu:

Petr Ambrož

Přednášející:

Petr Ambrož, Jan Volec

Cvičící:

Předmět zajišťuje:

katedra matematiky

Anotace:

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ů.

Požadavky:

Osnova přednášek:

Osnova cvičení:

Cíle studia:

Studijní materiály:

Povinná literatura:

[1] A. Bondy, U.S.R. Murty: Graph Theory, Springer-Verlag London 2008.

[2] R. Diestel: Graph Theory (5th ed.), Springer-Verlag Berlin Heidelberg 2017.

Další literatura:

[3] M. Rigo: Advanced Graph Theory and Combinatorics, Wiley-ISTE 2016.

[4] B. Sudakov: Graph Theory (lecture notes), ETH Zürich, 2016.

Poznámka:

Rozvrh na zimní semestr 2025/2026:

Rozvrh není připraven

Rozvrh na letní semestr 2025/2026:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů: