Teorie grafů 01TG (ZS 2024/2025)

• Út 14:00 - 15:40 , místnost T-212
• St 10:00 - 11:40 , místnost T-210

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

• Teorie grafů – Aktuální zápisky A. Blažka
• 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

• Celkem bude alespoň 10 sérií domácích úloh, každá série bude obsahovat 5 úloh
• Každá domácí úloha bude ohodnocena 0 či 0.5 či 1 body, řešení se vždy odevzdává pomocí MS Teams
• Řešení odevzdáné nejvýše 48 hodin po deadline bude mít ohodnocení sníženo o 50%
• Řešení odevzdáné více než 48 hodin po deadline nebudou hodnocena
• Známka A – získat celkem alespoň 32 bodů z alespoň 8 různých serií, a prezentovat řešení 2 těžkých úloh
• Známka B – získat celkem alespoň 25 bodů z alespoň 7 různých serií, a prezentovat řešení 1 těžké úlohy
• Známka C – získat celkem alespoň 16 bodů z alespoň 6 různých serií, a prezentovat řešení 1 těžké úlohy
• Známky D a E – zkouška primárně zaměřená na úlohy ze sérií, které Vám dělaly problémy / vůbec jste je neřešili
• Nad Vašim řešením těžkých úloh může následovat diskuze (emailem či osobně) ujasňující Váš postup
• Řešení jedné těžké úlohy lze zaměnit za efektivní implementaci algoritmu pro výpočet váhy minimální kostry resp. průměru ve vážených grafech
• Deadline pro odevzdání řešení těžkých úloh je 16. květen 2025 23:59:59 SELČ

• Známka A – alespoň 3.5 bodu
• Známka B – alespoň 3 body
• Známka C – alespoň 2 body
• Známka D – alespoň 1.5 bodu
• Známka E – alespoň 1 bod

• 1. série ; deadline 10.10. 11:59:59 SELČ
• 2. série ; deadline 17.10. 11:59:59 SELČ
• 3. série ; deadline 24.10. 11:59:59 SELČ
• 4. série ; deadline 31.10. 11:59:59 SEČ
• 5. série ; deadline 15.11. 11:59:59 SEČ
• 6. série ; deadline 28.11. 11:59:59 SEČ
• 7. série ; deadline 5.12. 11:59:59 SEČ

• W1a: 24.9. – Úvod a formality, definice grafu a jeho doplňku, stupeň vrcholu a princip sudosti, věta o skóre
• W1b: 25.9. – Isomorfismus a automorfismus, počet neizomorfních grafů na n vrcholech, sled/tah/cesta, komponenty souvislosti, počet souvislých grafů, podgraf, faktor grafu a indukovaný podgraf
• W2a: 1.10. – Minimální/průměrný/maximální stupeň, most v grafu, stromy (různé definice a jejich vzájemná ekvivalence), kostra grafu
• W2b: 2.10. – Cayleyho formule, počet neizomorfních stromů, fundamentální cyklus vůči kostře, prostor cyklů v grafu
• W3a: 8.10. – Vážený graf, minimální kostra a Kruskalův algoritmus, nejkratší cesty a Dijkstrův algoritmus
• W3b: 9.10. – Multigrafy, kontrakce hran, rekurzivní počítání koster grafu, bipartitní grafy, bipartitní podgrafy s hodně hranami, podgrafy s velkým MIN stupněm
• W4a: 15.10. – Graham-Pollakova věta, matice sousednosti a matice incidence, počet sledů vs. mocnina matice sousednosti, největší vlastní číslo grafu vs. MIN/AVG a MAX stupeň
• W4b: 16.10. – Spektrum souvislého grafu, spektrum regularního grafu vs. jeho doplňku, Laplaceova matice, Laplaceova matice vs. souvislost
• W5: 22.10. a 23.10. – přednášky nebudou
• W6a: 29.10. – Kirchoffova věta o počtu koster, Eulerovské tahy v multigrafech, Hamiltonovské kružnice (Oreho a Diracova věta)
• W6b: 30.10. – Důkaz Oreho věty, neseparovatelné grafy, bloková relace na hranách
• W7a: 5.11. – Ušaté lemma, hranová a vrcholová k-souvislost, lokální a globální Mengerovy věty
• W7b: 6.11. – Důkaz lokální Mengerovy věty, operace zachovávající k-souvislost, hranová k-souvislost
• W8a: 12.11. – Digrafy a orientované grafy, turnaje, toky v sítích
• W8b: 13.11. – Ford-Fulkersonova věta, párování v grafech, Bergeova věta
• W9a: 19.11. – Párování v bipartitních grafech, Königova věta o párování vs. pokrytí, Hallova věta a její důsledky, Gallaiova věta, párování v obecných grafech
• W9b: 20.11. – Tutte-Bergeova formule a Tutteova věta, Petersenova věta, hranová barevnost grafu, Königova věta o hranové barevnosti, Vizingova věta (znění)
• W10a: 26.11. – Plán: Důkaz Vizingovy věty, hranová barevnost K_n, Shannonova věta, vrcholová barevnost grafu a vztah k hranové barevnosti, degenerovanost grafu, věta o součtu barevnosti G a doplňku
• W10b: 27.11. – Plán: k-kritické grafy, Brooksova věta, pravděpodobnostní metoda a její použití v teorii grafů, grafy s velkou barevností a velkým obvodem