Základy teorie grafů (01TG/ZTG)

poslední změna: 01-10-2020

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 2020/2021

datum látka
21.9. Neorientovaný a orientovaný graf. Izomorfizmus grafů. Stupeň vrcholu a Handshaking lemma. Skóre. Věta o skóre.
22.9. Spernerovo lemma. Brouwerova věta o pevném bodě.
29.9. Sled, cesta, cyklus, kružice. Souvislý graf. Počet souvislých grafů. Adjacenční matice souvislého grafu. Bipartitní grafy.