Teorie grafů 01TG (ZS 2023/2024)

Přednášející – Jan Volec

Kontakt:	jan [AT] ucw [DOT] cz
Kancelář:	T-108a

Základní informace

St 12:00 - 13:40 T-210
Čt 14:00 - 15:40 T-210

Studijní materiály (CZ)

KOMB 2005/06 – zápisky P. Strachoty (PDF zde)
Barevnost grafů – studijní materíal E. Pelantové (aktualizované PDF zde)
Skriptíčka z kombinatoriky – skripta J. Matouška a T. Vally o Ramseyových větách, tocích v síti, párováních a Kuratowského větě (zde)
ad-hoc poznámky přednášejícího – Tutte-Bergeova formule, Brooksova věta

Studijní materiály (ENG)

Graph Theory (ETH Zürich) – studijní materiál B. Sudakova (PDF zde)
Graph Theory – kniha R. Diestela (dostupná online)
Graph Theory – kniha A. Bondyho a U.S.R Murtyho

Obsah přednášek (viz. též kapitánův deník z přednášek)

W1: 27.9. - Definice grafu a jeho doplňku, isomorfismus a automorfismus, počet neizomorfních grafů na n vrcholech, stupeň vrcholu a princip sudosti
W2a: 4.10. - Sled/tah/cesta, komponenty souvislosti, počet souvislých grafů, věta o skóre, podgraf, faktor grafu a indukovaný podgraf, most v grafu
W2b: 5.10. - Stromy (různe definice a jejich ekvivalence), kostra grafu, Cayleyho formule, počet neizomorfních stromů
W3a: 11.10. - Fundamentální cyklus vůči kostře, MST a Kruskalův algoritmus, nejkratší cesta v grafu a Dijkstrův algoritmus
W3b: 12.10. - Bipartitní grafy, bipartitní podgrafy, prostor cyklů v grafu
W4a: 18.10. - Multigrafy a kontrakce hran, rekurzivní počítání koster, matice sousednosti a matice incidence, největší vlastní číslo grafu vs. MIN/AVG a MAX stupeň, Laplaceova matice
W4b: 19.10. - Laplaceova matice vs. souvislost, Kirchoffova věta o počtu koster, Eulerovské tahy v multigrafech
W5: 25.10. a 26.10. - přednášky nejsou
W6a: 1.11. - Hamiltonovské kružnice, neseparovatelné grafy
W6b: 2.11. - Bloková relace na hranách, ušaté lemma, hranová a vrcholová k-souvislost, Mengerovy věty (lokální/globální a vrcholové/hranové varianty)
W7a: 8.11. - Důkaz lokální a globální vrcholové Mengerovy věty, operace zachovávající k-souvislost
W7b: 9.11. - Digrafy a orientované grafy, toky v sítích a Ford-Fulkersonova věta
W8a: 15.11. - Bergeova věta, párování v bipartitních grafech, Königova věta o párování vs. pokrytí, Hallova věta a její důsledky
W8b: 16.11. - Gallaiova věta, párování v obecných grafech a Tutte-Bergeova formule, Tutteova věta, Petersenova věta
W9a: 22.11. - Hranová barevnost grafu, Königova věta o hranové barevnosti, Vizingova věta, Shannonova věta
W9b: 23.11. - Vrcholová barevnost grafu a vztah k hranové barevnosti, degenerovanost grafu, věta o součtu barevnosti G a doplňku, Brooksova věta
W10a: 29.11. - k-kritické grafy, Mycelského konstrukce grafů bez trojúhelníku s velkou barevností, pravděpodobnostní metoda a její použití v teorii grafů, grafy s velkou barevností a velkým obvodem
W10b: 30.11. - Nakreslení grafu, Jordanova věta o kružnici (znění), rovinné grafy, Eulerova formule, stereografická projekce a Platónská tělesa
W11a: 6.12. - Podrozdělení a Kuratowského věta (znění), minory a Wagnerova věta (znění), ekvivalence Wagnerovy a Kuratowského věty, věta o 5 barvách, dualita rovinných grafů
W11b: 7.12. - Maderova věta o existenci minoru K_k, Thomassenova věta o 3-souvislých grafech, důkaz Kuratowského/Wagnerovy věty
W12a: 13.12. - K_6 na Möbiově pásce, lemma o počtu křížení (crossing lemma), Spernerovo lemma a Brouwerova věta o pevném bodě v rovině, Ramseyova věta
W12b: 14.12. - Erdősův dolní odhad na Ramseyova čísla, Goodmanova věta, Turánova věta, Erdősova věta o počtu hran grafu bez C₄, konstrukce grafu bez C₄
W13: 20.12. a 21.12. - samostatná příprava na úloh z domácí přípravy, přednášky nejsou
W14: 3.1. a 4.1. - Q&A pro úlohy domácí přípravy

Zkouška bude letos písemnou formou (180 minut)

Předetermín: Pátek 15.12.2023 v 15:15, místnost T-112
Termín 1: Úterý 9.1.2024 v 9:15, místnost T-210
Termín 2: Středa 17.1.2024 v 9:15, místnost T-210
Termín 3: Pondělí 29.1.2024 v 9:15, místnost v T-210

Bodové podmínky pro body z domácích úloh

Každá domácí úloha odpovídá 1 bodu, řešení se odevzdává skrz MS Teams
Známka A: je nutné získat celkem alespoň 34 bodů z alespoň 8 serií, a vyřešit alespoň 3 těžké úlohy
Známka B: je nutné získat celkem alespoň 26 bodů z alespoň 7 serií, a vyřešit alespoň 2 těžké úlohy
Známka C: je nutné získat celkem alespoň 17 bodů z alespoň 6 serií, a vyřešit alespoň 1 těžkou úlohu
Známky D a E: bude případně upřesněno do začátku prosince

Řešení jedné těžké úlohy lze zaměnit za efektnivní implementaci algoritmu pro výpočet váhy minimální kostry resp. průměru ve vážených grafech; viz. trenažér.

Těžké (zkouškové) úlohy a Trenažér pro grafové algoritmy

Domácí úlohy a úlohy

1. série ; deadline 10.10. 23:59:59 SELČ
2. série ; deadline 17.10. 23:59:59 SELČ
3. série ; deadline 24.10. 23:59:59 SELČ
4. série ; deadline 1.11. 11:59:59 SEČ
5. série ; deadline 15.11. 23:59:59 SEČ
6. série ; deadline neexisuje, určeno jen jako příprava na zkoušku
7. série ; deadline neexisuje, určeno jen jako příprava na zkoušku
8. série ; deadline neexisuje, určeno jen jako příprava na zkoušku
9. série ; deadline neexisuje, určeno jen jako příprava na zkoušku
10. série ; deadline neexisuje, určeno jen jako příprava na zkoušku