Kombinatorika a grafy 2 (NDMI012) -- cvičení
Cvičení probíhá každou středu od 12:20 v učebně S6.
Cvičení vede Pepa Tkadlec. E-mail cvičícího: pepa (AT) iuuk.mff.cuni.cz
Přednášku vede Jan Hubička: Stránky přednášky (a loňské přednášky)
Kombinatorika a grafy 2 (NDMI012) -- cvičení
Cvičení probíhá každou středu od 12:20 v učebně S6.
Cvičení vede Pepa Tkadlec. E-mail cvičícího: pepa (AT) iuuk.mff.cuni.cz
Přednášku vede Jan Hubička: Stránky přednášky (a loňské přednášky)
Podmínky získání zápočtu:
Získání alespoň 100 bodů ze 150 dostupných bodů za průběžné domácí úkoly (resp. proporčně méně, pokud bude dostupných bodů méně, nakonec 80/120). Úkoly se odevzdávají přes Sovičku (přihlásíte se údaji jako do SISu, enrollment token je c4ac735ed751) a mají deadline do pátku za ~10 dní. K úkolům odevzdaným do neděle 23:59 se (snad) vyjádřím do následujícího cvičení.
Cílem úkolů je pomoci vám zjistit, jak dobře zvládáte látku. Pro zisk plného počtu bodů není nutné vyřešit úkol správně, ale je nutné: (i) odevzdat ho včas, (ii) přesvědčit mě, že jste vynaložili nějaké úsilí, a (iii) nepsat nepravdy a nemlžit. Pokud si nebudete vědět rady, silně doporučuju konzultovat úkol s někým nebo s něčím. Konzultace nemají žádný vliv na počet získaných bodů, ale musíte je přiznat. Příklad: Za "Sám jsem se dostal až po X, pak mi ChatGPT poradil Y, ale přijde mi, že Y funguje jen za extra předpokladu Z a bez něj nevím, jak dál." typicky dostanete plný počet bodů. Za psaní nepravd typicky získáte málo bodů.
O tom, jak sepisovat důkazy, si můžete přečíst na stránce Martina Kouteckého (link) a/nebo na stránkách korespondenčního semináře MKS (link).
Účast na cvičeních je nepovinná.
Jednotlivá cvičení:
19.2.2025: Párování, Hallova věta (PDF). Probrali jsme hlavně úlohy 1, 2, 3, 4, 5, 6, 7.
26.2.2025: Edmondsův kytičkový algoritmus (PDF). Probrali jsme hlavně úlohy 1, 2, 3a.
5.3.2025: [záskok J. Soukup] Tutteova věta (PDF). Probraly se hlavně úlohy 1, 2, 3. (Reseni ukolu o parovani skrz predepsanou hranu v kubickem grafu: tady)
12.3.2025: Minory (PDF). Probrali jsme hlavně úlohy 1, 2, 3, 4, 5.
19.3.2025: Ještě minory a trochu plochy (PDF). Probrali jsme hlavně úlohy 1, 2, 3, 4, 5, 6, 7. Odkaz na YT video s řešením 5 (>15 let stare).
26.3.2025: Kresleni na plochách (PDF). Probrali jsme hlavně úlohy 0, 1, 2, 3, 4.
2.4.2025: Barevnost (PDF). Probrali jsme hlavně úlohy 1, 2, 3, 4, 5, 6, 7, 8, 9.
9.4.2025: Hranová barevnost a perfektnost (PDF). Probrali jsme hlavně úlohy 1, 2, 3, 4, 5, 6, 7, 8.
16.4.2025: Perfektnost (PDF). Probrali jsme hlavně úlohy 1, 2, 3, 4, 5, 6.
23.4.2025: Chordální grafy (PDF). Probrali jsme hlavně úlohy 1, 2, 3, 4, 5, 6, 7. Odkaz na YT video s řešením 7.
30.4.2025: Grafové polynomy (PDF). Probrali jsme hlavně úlohy 1, 2, 3, 4, 5.
7.5.2025: Vytvořující funkce (PDF). Probrali jsme hlavně úlohy 1, 2, 3, 4, 6.
14.5.2025: Burnsideovo lemma (PDF). Probrali jsme hlavně úlohy 1, 2, 3b.
21.5.2025: Extremální kombinatorika (PDF). Probrali jsme hlavně úlohy 1, 2, 3, 4, 5.