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)

Domácí cvičení

Formou domácích úkolů a předvádění ve škole, cca jednou za 2 týdny.
  • Cvičení vede Peter Korcsok
    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.