Hledání optimální cesty v grafech
| Thesis title in Czech: | Hledání optimální cesty v grafech |
|---|---|
| Thesis title in English: | Searching for optimal path in graphs |
| Key words: | Graf; Ohodnocený graf; Optimalizace na grafu. |
| English key words: | Graph; Weighted graph; Optimization on a graph. |
| Academic year of topic announcement: | 2010/2011 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | čeština |
| Department: | Department of Probability and Mathematical Statistics (32-KPMS) |
| Supervisor: | doc. RNDr. Petr Lachout, CSc. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 04.10.2010 |
| Date of assignment: | 05.10.2010 |
| Date and time of defence: | 12.09.2011 00:00 |
| Date of electronic submission: | 04.08.2011 |
| Date of submission of printed version: | 05.08.2011 |
| Date of proceeded defence: | 12.09.2011 |
| Opponents: | doc. RNDr. Ing. Miloš Kopa, Ph.D. |
| Guidelines |
| Řadu rozhodovacích a konfliktních situací v reálném životě je možno modelovat pomocí
vhodného grafu s ohodnocením. Druhým přirozeným krokem je pak optimalizace průchodu grafem vzhledem k daným kritériím. Vyhledávání a popis optimalizačních úloh na grafech aplikovatelých v praxi bude předmětem této bakalářské práce. Práce by měla být přednostně zaměřena na úlohy typu: problém obchodního cestujícího, nejkratší cesty grafem, nejlacinější cesty grafem, optimální tok sítí, atd. |
| References |
| [1] M. Maňas: Optimalizační metody, Státní nakladatelství technické literatury, Praha, 1979
[2] J. Matoušek, J. Nešetřil : Kapitoly z diskrétní matematiky, Nakladatelství Karolinum, 2007 [3] Hammer et al. editors : Annals of Discrete Mathematics 4 -Discrete Optimization I, North-Holland Publishing Company, 1979 [4] W. Kocay, D.L. Kreher : Graphs, Algorithms, and Optimization, Chapman & Hall/CRC Press, 2005 [5] J. Plesník: Grafové algoritmy, VEDA, Vydavatel'stvo Slovenskej Akadémie Vied, Bratislava, 1983 |