česky | 
englishTeorie grafů (01TG)
poslední změna: 13-01-2026
Anotace
Základní pojmy teorie grafů: graf, izomorfizmus, souvislost, matice sousednosti. Stromy a kostry. Toky v sítích. Eulerovy cykly, Hamiltonovy kružnice. Párování v grafech. Vrcholová a hranová barevnost. Planární grafy. Extremální úlohy na grafech. Spektrum matice sousednosti.
Literatura
- Zápisky z předmětu KOMB, akademický rok 2005/2006, autor: P. Strachota
- Vrcholová barevnost grafů, autor: prof. Edita Pelantová
- J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, The Maxmillan Press, 1982
- R. Diestel, Graph Theory, Springer-Verlag, New York, 2005
- Postupně uveřejňované pdf soubory s částmi textu.
Zkouška
Zkouška z předmětu ZTGA je ústní, počet studentů na termínu je omezen na 4. Zkouškové termíny budou vypsány v KOSu, přihlašování na zkoušky probíhá tamtéž.
skripta (možná jednou)
- kapitola 1.7 Matrix-Tree Theorem (verze 2010-10-15)
- kapitota 3.1 Vrcholová a hranová souvislost (verze 2010-10-15)
- kapitola 3.2 Mengerova věta (verze 2010-11-10)
- kapitola 4.1 Maximální párování (verze 2011-10-27)
- kapitoly 6.1 a 6.2 Toky v sítích (verze 2008-12-08)
- kapitola 6.3 Boolovské toky (verze 2008-12-08)
Podrobný sylabus 2025/2026
| datum | látka |
|---|---|
| 23.9. | Neorientovaný a orientovaný graf. Izomorfizmus grafů. Stupeň vrcholu a Handshaking lemma. Grafová posloupnost. |
| 27.9. | Sled, cesta, cyklus, kružice. Souvislý graf. Počet souvislých grafů. Adjacenční matice grafu. Vztah souvislosti grafu a jeho adjacenční matice. Stromy a lesy. |
| 30.9. | Eulerův vzorec. Cayleyho formule (důkaz pomocí skóre a pomocí PoVyKoSů). Kostra grafu. |
| 1.10. | Úloha minimální kostry. Kruskalův algoritmus. Počet koster grafu (Matrix-Tree theorem). |
| 7.10. | Spernerovo lemma. Brouwerova věta o pevném bodě. |
| 8.10. | Eulerovské grafy. Hamiltonovské kružnice. |
| 14.10. | Párování. Bergeova věta o maximálním párování. |
| 21.10. | Perfektní párování. Tutteho věta. |
| 22.10. | Hrahová barevnost grafů. |
| 4.11. | Vrcholová barevnost. K-kritické grafy. |
| 5.11. | Brooksova věta. Mycielského konstrukce. |
| 11.11. | Toky v sítích. |
| 12.11. | Fordův-Fulkersonův algoritmus pro nalezení max. toku. Max-flow min-cut teorém. Booleovské toky (alternativní dk Hallovy věty). |
| 18.11. | Planární grafy. |
| 19.11. | Barevnost planárních grafů. Minimální neplanární grafy, Kuratowského věta. |
| 25.11. | Kuratovkého věta (dokončení). Vrcholová a hranová souvislost. |
| 26.11. | Mengerova věta. |
| 2.12. | Mengerova věta (globální verze). Souvislost a hamiltonovskost grafu. |
| 3.12. | Spektrální vlastnosti adjacenční matice grafu. |
| 9.12. | Spektrum regulárního a bipartitního grafu. |
| 10.12. | Pravděpodobnost v teorii grafů. |
| 16.12. | Pravděpodobnost v teorii grafů (dokončení). |
| 17.12. | Turánova věta. |
