Teorie grafů 01TG (ZS 2022/2023)
| Kontakt: | jan [AT] ucw [DOT] cz
|
| Kancelář: | T-108a
|
Základní informace
- St 10:00 - 11:40 T-210
- Čt 14:00 - 15:35 T-210
Studijní materiály (CZ)
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
Bodové podmínky pro body z domácích úloh
- Každá základní úloha odpovídá 1 bodu, každá hvězdičková úloha (challenge) odpovídá 2 bodům
- Řešení hvězdičkových úloh lze odevzdávat i po deadline
- Je nutné získat celkem alespoň 17 bodů (součet za základní i hvězdičkové úlohy)
- Vyřešení alespoň 3 hvězdičkových úloh a získání celkem 40 bodů znamená automaticky známku A
Obsah přednášek
- W1a: 21.9. - Uvodní přednáška
- W1b: 22.9. - Graf, komplement, počet grafů, sled/tah/cesta, komponenty souvislosti, isomorfismus, automorfismus, podgraf, stupeň vrcholu, princip sudosti a věta o skóre (znění)
- W2: 28.9. + 29.9. - přednáška není
- W3a: 5.10. - Věta o skóre (důkaz), stromy (různe definice a jejich ekvivalence), most v grafu
- W3b: 6.10. - Faktor grafu a indukovaný podgraf, kostra grafu, Cayleyho formule, počet neizomorfních stromů, fundamentální cyklus vůči kostře, MST a Kruskalův algoritmus
- W4a: 12.10. - Nejkratší cesta v grafu a Dijkstrův algoritmus
- W4b: 13.10. - Bipartitní grafy, prostory cyklů grafu
- W5a: 19.10. - Bipartitní podgrafy, podgrafy velkého min. stupně, Hamiltonovské kružnice
- W5b: 20.10. - Eulerovské grafy, matice sousednosti a matice incidence grafu, Laplaceova matice a počet koster libovolného grafu (znění)
- W6a: 26.10. - Důkaz Kirchoffovy věty, největší vlastní číslo grafu vs. MIN/MAX stupeň, neseparovatelné grafy
- W6b: 27.10. - Bloková relace na hranách, ušaté lemma, definice k-souvislosti
- W7a: 2.11. - Hranová a vrcholová k-souvislost, Mengerova věta (vrcholová - lokální a globální verze)
- W7b: 3.11. - Digrafy a orientované grafy, toky v sítích a Ford-Fulkersonova věta
- W8a: 9.11. - Bergeova věta, Párování v bipartitních grafech, Königova věta o párování vs. pokrytí, Hallova věta
- W8b: 10.11. - Párování v obecných grafech a Tutte-Bergeova formule, Tutteova věta, Petersenova věta, Gallaiova věta
- W9: 16.11. - Hranová a vrcholová barevnost grafu, Königova věta o hranové barevnosti, Vizingova věta, Shannonova věta
- W10a 23.11. - Degenerovanost grafu, Mycelskeho konstrukce grafů bez trojúhelníku a velké barevnosti, Brooksova věta
- W10b 24.11. - Věta o součtu barevnosti G a doplňku, Pravděpodobnostní metoda a její použití v teorii grafů, grafy s velkou barevností a velkým obvodem
- W11a 30.11. - Nakreslení grafu, Jordanova věta o kružnici (znění), rovinné grafy, Eulerova formule, Kuratowského věta (znění), Lemma o počtu křížení (crossing lemma)
- W11b 1.12. - Minory, Wagnerova věta (znění) a ekvivalence s Kuratowského větou, věta o 5 barvách, dualita rovinných grafů, Hadwigerova domněnka pro grafy bez K4 minoru
- W12a: 7.12. - Sterografická projekce a Platónská tělesa, Thomassenova věta o 3-souvislých grafech, důkaz Kuratowského/Wagnerovy věty
- W12b: 8.12. - Erdős-Szekerésovo lemma, Ramseyova věta (grafová a hypergrafová), Schurova věta, Erdősův dolní odhad na R(k)
- W13a: 14.12. - Extremální teorie grafů, Goodmanova věta, Mantelova a Turánova věta, Erdősova věta o počtu hran grafu bez C4
- W13b: 15.12. - Konstrukce grafu bez C4, Kövari-Sós-Turánova věta, Bondyho-Simonovitsova věta (znění plné verze + důkaz slabší varianty), aplikace extremální kombinatoriky v geometrii, Maderova věta o existenci minoru Kk
- W14: 4.1. - Formule pro počet souvislých podgrafů, Spernerovo lemma a Brouwerova věta o pevném bodě v rovině, Gallai-Milgramova věta (znění)
Domácí úlohy