NDMI 058 -- Toky a cykly v grafech

V roce 2014/2015 přednáší Robert Šámal

Další info v SISu.
Pro lepší představu, co vás čeká: stránka minulého vydání, téhle přednášky.
Přednáška se koná v úterý 9:00 v S10.
Poznámky z přednášky (průběžně upravuji)

Formou domácích úkolů a předvádění ve škole, cca jednou za 2 týdny.

1. přednáška 24.2.2015: Úvod -- co je to CDC, co jsou to toky. Tokový polynom.
2. přednáška 3.3.2015: Nenulový tok celočíselný a modulo k. Grafy s 2-tokem, 3-tokem, 4-tokem. Zmínka o dualitě pro rovinné grafy.
3. přednáška 10.3.2015: Použití koster: elementární toky. Jaegerovy věty o 4-toku a 8-toku. Definice tenze.
4. přednáška 17.3.2015: Tenze a toky pomocí matic. Generátory, kolmost, atd. Jak je to s duály (a trochu i na jiných plochách). Huffmanovo cirkulační lemma. Definice nenulových k-toků pro reálné k. Balancované valuace -- další ekvivalentní podminka.
5. přednáška 24.3.2015: Cycle double cover. Souvislost s toky. Orientovaná verze. Stačí dokazovat pro kubické grafy. Vlastnosti minimálního protipříkladu.
6. přednáška 31.3.2015: Splitting lemma. Další vlastnosti minimálního protipříkladu na CDC. Berge-Fulkersonova hypotéza--úvod.
7. přednáška 7.4.2015: Hledání antisymetrického toku v grafech.
8. přednáška 14.4.2015 -- PLÁN: Užití Edmondsova matching polytopu.
9. přednáška 21.4.2015
10. přednáška 28.4.2015: Věta o 6-toku. Klasický důkaz je v poznámkách z přednášky, ukazovali jsme si nový důkaz.
není přednáška 5.5.2015 -- jarní škola
11. přednáška 12.5.2015: Slabá věta o 3-toku (Thomassen, Lovász, Zhang, Wu)
12. přednáška 19.5.2015: Dokončení z minula.