česky | 
englishZáklady teorie grafů (01TG/ZTG)
poslední změna: 07-10-2021
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 ZTGA
- 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)
- kapitola 9 Spektrum adjacenční matice (verze 2009-12-10)
Podrobný sylabus 2021/2022
| datum | látka |
|---|---|
| 20.9. | Neorientovaný a orientovaný graf. Izomorfizmus grafů. Stupeň vrcholu a Handshaking lemma. Skóre. Věta o skóre. |
| 21.9. | Spernerovo lemma. Brouwerova věta o pevném bodě. |
| 27.9. | Sled, cesta, cyklus, kružice. Souvislý graf. Počet souvislých grafů. Adjacenční matice souvislého grafu. Bipartitní grafy. |
| 28.9. | — |
| 4.10. | Stromy a lesy. Eulerův vzorec. Cayleyho formule (důkaz pomocí skóre). |
| 5.10. | Cayleyho formule (důkaz pomocí PoVyKoSů). Izomorfizmus stromů. |
