Základy teorie grafů (01ZTGA)

poslední změna: 10-10-2019

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

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

Podrobný sylabus 2019/2020

datum látka
23.9. Neorientovaný a orientovaný graf. Izomorfizmus grafů. Stupeň vrcholu a Handshaking lemma. Skóre. Věta o skóre.
26.9. Spernerovo lemma. Brouwerova věta o pevném bodě. Sled, cesta, cyklus, kružice. Souvislý graf.
30.9. Počet souvislých grafů. Adjacenční matice souvislého grafu. Bipartitní grafy.
3.10. Stromy a lesy. Eulerův vzorec. Izomorfizmus stromů.
7.10. Cayleyho formule (důkaz pomocí skóre, důkaz pomocí PoVyKoSů). Kostra a minimální kostra grafu.
10.10. Matrix-tree theorem. Eulerovské grafy.