Kombinatorika a grafy 2 v LS 25/26

Stránka přednášky a cvičení Pepy Tkadlece a Pavla Veselého z Kombinatoriky a grafů 2 (KG2) – přednáška bude ve středy od 14 h v S9 a cvičení budou v úterý od 14 h v S7 a ve středy od 12:20 v S8. Budeme navazovat na Pepovu přednášku z KG1. Představu o přednášce si můžete udělat z Pavlovy přednášky v roce 2023, loňské přednášky Honzy Hubičky či starších přednášek Zdeňka Dvořáka, Víta Jelínka a Martina Kouteckého.

Pokud máte nějaký dotaz, pište na {pepa, vesely} (zavináč) iuuk.mff.cuni.cz, případně se zeptejte po přednášce či cvičení. Také budeme rádi, když se během přednášek a cvičení budete ptát, jakmile vám nebude něco jasné. Chcete-li konzultaci, ozvěte se nám emailem nebo po přednášce/cvičení (vhodný čas může být po přednášce).

Přednáška

U každého tématu budou odkazy na literaturu níže. Prezentace (s obrázky z Wikipedie a od Z. Dvořáka)

1.

18. 2.

 Pepa: Edmondsův algoritmus pro hledání největšího párování.
Zdroje: [VM] (sekce 5.2), [P] (sekce 9.5-9.7), [Sh] (poměrně dobrý popis algoritmu i analýzy) a [T] (stručný text, ale obsahuje to hlavní)
Video od Tomáše Slámy

2.

25. 2.

 Pepa: Tutteova charakterizace grafů s perfektním párováním (s důkazem) a Petersenova věta o 3-reguárních grafech bez mostů (důkaz pomocí Tutteovy charakterizace)
Zdroje: [VM] (sekce 5.1), [P] (kapitola 9) a [D] (sekce 2.2)
3. 4. 3. Pepa: Tutteova charakterizace 3-souvislých grafů (Lemma o kontrahovatelné hraně: pouze idea důkazu, detaily důkazu se nezkouší), úvod do grafových minorů a topologických minorů. Charakterizace rovinných grafů: Kuratowského-Wagnerova věta (zatím bez důkazu hlavní implikace).
[VM] (sekce 7), [P] (sekce 10.1 a 10.2) a [D] (kapitola 4)
4. 11. 3. Důkaz hlavní implikace Kuratowského-Wagnerovy věty (tedy každý graf neobsahující K₅ nebo K₃,₃ jako minor lze nakreslit do roviny). Úvod do kreslení grafů na plochy (vysvětlení pojmu plochy).
Poznámky.
Zdroje k plochám: [P] (kap. 11), [Dv] (poznámky k plochám), [MT] (kapitola 3) a [R] (kapitoly 3-4)
Pár videí pro lepší intuici: projektivní rovina a Möbiova páska, Kleinova láhev, a dvojitý torus.
5. 18. 3. Kreslení grafů na plochy: vytváření pomocí přidávání uch a křížítek, zobecněná Eulerova formule (skeč důkazu indukcí ) a Heawoodovo číslo (důkaz barevnosti bude příště). Poznámka: domácí úkol bude zadán do čtvrtečního rána.
Poznámky.
Zdroje k plochám podobné jako minule: [P] (kap. 11), [Dv] (poznámky k plochám a poznámky k Heawood číslu), [MT] (kapitola 3 a sekce 8.3)

Cvičení

Cvičení jsou dvě, jedno v úterý od 14 h v S7 a druhé ve středu od 12:20 v S7. Pokud byste chtěli chodit na středeční, ale jste zapsaní na úterní, tak se nám ozvěte (opačný přesun by neměl být problém).

Příklady řešené na cvičeních

Zápočet bude za zisk alespoň 2/3 bodů za úkoly (očekávejte, že na zápočet bude potřeba cca 100 bodů z úkolů z alespoň 150 možných). Úkoly se odevzdávají přes Sovičku (přihlásíte se údaji jako do SISu, enrollment token je 99b3af017c3e )

Cílem úkolů je procvičit si probíranou látku a pomoci vám zjistit, jak dobře ji zvládáte. Pro zisk plného počtu bodů není nutné vyřešit celý úkol správně, ale je nutné: (i) odevzdat ho včas, (ii) přesvědčit nás, že jste vynaložili nějaké úsilí, a (iii) nepsat nepravdy a nemlžit. Pokud si nebudete vědět rady, doporučujeme dát si od úkolu pauzu. Můžete též 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 body nezískáte. O tom, jak sepisovat důkazy, si můžete přečíst na stránce Martina Kouteckého a/nebo na stránkách korespondenčního semináře MKS.

Zkouška

Zkouška bude ústní s písemnou přípravou. Více detailů řekneme ke konci semestru.

Literatura a zdroje

Většina zdrojů je v angličtině:

Mobius strip, double torus