Title: Diskrétní a spojitá optimalizace / Diskrétní optimalizace (Zřím tě)

Matroid

Lemma o ekvivaletní definici matroidu

Sudá podmnožina hran

Matice incidence

Jádro matice incidence

Charakteristický vektor

Řádová funkce

Věta o řádové funkci matroidu

Věta řádová funkce a submodularita

Marginální hodnota

Q: Věta o marginální hodnotě a submodularitě
A: Ošklivej důkaz po tobě stejně určitě chtít nebudou

Hladový algoritmus a úloha kombinatorické optimalizace

Věta o hladovém algoritmu na matroidech

Operace součet a sjednocení na matroidech

Věta (sjednocení matroidů je matroid)

Mazání a kontrakce v matroidech

Věta (kontrakce matroidu je matroid)

Parition matroid

Q: Edmonsova MiniMaxová věta o průniku matroidů
A: takže ho po tobě chtít nebudou

Duální matroid

Věta (duální matroid je matroid)

Cobáze, conezávislost

Kružnice

Věta o cokružnici

Q: Co vytvořil sláma o perfektní párování?
A: video
https://www.youtube.com/watch?v=3roPs1Bvg1Q

Perfektní, největší, maximální a prosté párování

Pokrytí a defekt

Alternující cesta

párování je největší ptk nemá zlepšující cestu

Tutte-Berge

Edmonds-Gallai dekompozice

Magie s generujícíma funkcema

DeterminanT

Permanent

Věta o rovinném grafu

Věta (Kasteleyn)

Čínský pošťák a obchodní cestující

T-joiN

Věta o minimální trase čínského pošťáka

Algoritmus pro čínského pošťáka

Q: Algoritmus pro obchodního cetujícího
A: https://slama.dev/poznamky/aproximacni-algoritmy/