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Č

• 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. - Plán: Kirchoffova věta o počtu koster, Eulerovské tahy v multigrafech, Hamiltonovské kružnice
• W6b: 30.10. - Plán: Neseparovatelné grafy, bloková relace na hranách, ušaté lemma, hranová a vrcholová k-souvislost