Kombinatorická optimalizace, charakterizační věty a dualita v lineárním programování - Hahn, Viktor (2010)
Cílem této práce je dokázat charakterizační věty teorie grafů, konkrétně Königovu větu o párování maximální velikosti v bipartitních grafech a Fordovu-Fulkersonovu větu o toku maximální velikosti v dané síti. Uvedené problémy jsou nejprve formulovány jako úlohy lineárního programování, kde příslušné polyedry jsou popsány totálně unimodulárními maticemi. K těmto úlohám poté sestrojíme duální úlohy. Vyřešením duální úlohy a následnou interpretací řešení v řeči teorie grafů dostaneme očekávaný výsledek.