Teorie grafů 01TG (ZS 2024/2025)
| Kontakt: | jan [AT] ucw [DOT] cz
|
| Kancelář: | T-108a
|
Základní časo-prostorové informace
- Út 14:00 - 15:40 , místnost T-212
- St 10:00 - 11:40 , místnost T-210
Studijní materiály (ENG)
- 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)
Dodatečné studijní materiály (CZ)
Podmínky pro úspěšné splnění předmětu
- 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Č
Zkouška písemnou formou (4 úlohy, 180 minut)
- 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
Jednotlivé série domácích úloh (PDF)
1. série ; deadline 10.10. 11:59:59 SELČ
2. série ; deadline 17.10. 23:59:59 SELČ
- 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. - Plán: Vážený graf, MST a Kruskalův algoritmus, nejkratší cesta a Dijkstrův algoritmus
- W3b: 9.10. - Plán: Bipartitní grafy, bipartitní podgrafy, podgrafy velkého min. stupně, multigrafy a kontrakce hran, rekurzivní počítání koster
- W4a: 15.10. - Plán: Matice sousednosti a matice incidence, největší vlastní číslo grafu vs. MIN/AVG a MAX stupeň, spektrum souvislého regularního grafu a jeho doplňku, Friendship theorem
- W4b: 16.10. - Plán: Laplaceova matice, Laplaceova matice vs. souvislost, Kirchoffova věta o počtu koster, Graham-Pollakova věta
- W5: 22.10. a 23.10. - přednášky nebudou