Kombinatorická optimalizace, charakterizační věty a dualita v lineárním programování
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é...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Typ dokumentu: | VŠ práce nebo rukopis |
| Jazyk: | Čeština |
| Vydáno: |
2010
|
| Témata: | |
| On-line přístup: | http://is.muni.cz/th/268804/prif_b/ |
| Shrnutí: | 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. The aim of the thesis is to prove characterization theorems of the graph theory, concretely König´s theorem on matching of maximum amount in bipartite graphs and the theorem of Ford and Fulkerson on the flow of maximum amount in the given network. At first, the mentioned matters are formulated as problems of linear programming where appropriate polyhedrons are described by totally unimodular matrices. After that, dual problems are formed. The expected result will be achieved by the solution of the dual problem and consequent interpretation of the solution in the language of graph theory. |
|---|---|
| Popis jednotky: | Vedoucí práce: Michal Kunc |
| Fyzický popis: | 43 l. |