Kombinatorika a grafy 2 (NDMI012) -- cvičení
Cvičení probíhá každé úterý od 10:40 v učebně S7.
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ždé úterý od 10:40 v učebně S7.
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 efc7a03e588c) 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í:
18.2.2025: Párování, Hallova věta, PDF. Probrali jsme hlavně úlohy 1, 2, 3, 4, 5, 6, 7.
25.2.2025: Edmondsův kytičkový algoritmus (PDF). Probrali jsme hlavně úlohy 1, 2, 3a.
4.3.2025: Tutteova věta (záskok Jan Hubička, bude něco jako tohle PDF). (Reseni ukolu o parovani skrz predepsanou hranu v kubickem grafu: tady)
11.3.2025: Minory (PDF). Probrali jsme hlavně úlohy 1, 2, 3, 4, 5.
18.3.2025: Ještě minory a trochu plochy (PDF). Probrali jsme hlavně úlohy 1, 2, 3, 4, 5. Odkaz na YT video s řešením 5 (>15 let stare).
25.3.2025: Kresleni na plochách (PDF). Probrali jsme hlavně úlohy 1, 2, 3, 4, 5.
1.4.2025: Barevnost (PDF). Probrali jsme hlavně úlohy 1, 2, 3, 4, 5, 6, 7, 8, 9.
8.4.2025: Hranová barevnost a perfektnost (PDF). Probrali jsme hlavně úlohy 1, 2, 3, 4, 5, 7, 8.
15.4.2025: Perfektnost (PDF). Probrali jsme hlavně úlohy 1, 2, 3, 4, 5, 6.
22.4.2025: Chordální grafy (PDF). Probrali jsme hlavně úlohy 1, 2, 3, 4, 5, 6. Odkaz na YT video s řešením 7.
29.4.2025: Grafové polynomy (PDF). Probrali jsme hlavně úlohy 1, 2, 3, 4, 5.
6.5.2025: Vytvořující funkce (PDF). Probrali jsme hlavně úlohy 1, 2, 4, 6.
13.5.2025: Cvičení se nekoná (rektorský den).
20.5.2025: Burnsideovo lemma (PDF). Probrali jsme hlavně úlohy 1, 2, 3.