NDMI 058 -- Toky a cykly v grafech

V roce 2018/2019 přednáší Robert Šámal

Literatura

Cvičení

1. přednáška 25.2.2019

Úvod -- co je to CDC, co jsou to toky. Tokový polynom. Grafy s 2-tokem, 3-tokem, 4-tokem. Nenulový tok celočíselný a modulo k. Přednesená látka

2. přednáška 11.3.2019

Vztah tokovosti grafu a barevnosti jeho rovinného duálu. Tuttova věta o ekvivalenci nenulových $k$-toků a $\Z_k$-toků. Konstrukce toků pomocí koster (4-tok pro hranově 4-souvislé grafy). Přehled známých výsledků a hypotéz. Přednesená látka

3. přednáška 18.3.2019

Toky, tenze (pohled lineární algebry). Huffmanovo cirkulační lemma a frakcionální toky. Přednesená látka

4. přednáška 25.3.2019

Huffmanovo cirkulační lemma -- důkaz. Definice nenulových k-toků pro reálné k. Snarky -- definice, motivace, konstrukce (2-řez, 3-řez, dot-product). Přednesená látka

5. přednáška 1.4.2019

Pokročilejší konstrukce snarků: Isaacs dot product, Flower snarks, Kocholova superpoziční metoda. Přednesená látka

6. přednáška 8.4.2019

Cycle double cover. Souvislost s toky. Orientovaná verze. Stačí dokazovat pro kubické grafy. Vlastnosti minimálního protipříkladu. Přednesená látka

7. přednáška 15.4.2019

Berge-Fulkersonova hypotéza. Užití Edmondsova matching polytopu. Splitting lemma. Přednesená látka

8. přednáška 29.4.2019

Důkaz popisu polytopu párování. Důkaz splitting lemmatu. Přednesená látka

9. přednáška 6.5.2019

Samostatná četba důkazu věty o existenci 6-toku: klasický nebo nový důkaz.

10. přednáška 13.5.2019

Ekviv. podmínka pro existence 5-toku (pro kubické grafy). Přednesená látka

11. přednáška 20.5.2019

Grupová souvislost. Hypotéza o 3-toku a její verze. $\Z_k$-orientace. Věta [LTWZ]: Každý hranově 6-souvislý graf je $\Z_3$-souvislý. Část důkazu. Přednesená látka