Hledání optimální cesty v grafech

• Název práce v češtině: Hledání optimální cesty v grafech
• Název v anglickém jazyce: Searching for optimal path in graphs
• Klíčová slova: Graf; Ohodnocený graf; Optimalizace na grafu.
• Klíčová slova anglicky: Graph; Weighted graph; Optimization on a graph.
• Akademický rok vypsání: 2010/2011
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra pravděpodobnosti a matematické statistiky (32-KPMS)
• Vedoucí / školitel: doc. RNDr. Petr Lachout, CSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 04.10.2010
• Datum zadání: 05.10.2010
• Datum a čas obhajoby: 12.09.2011 00:00
• Datum odevzdání elektronické podoby: 04.08.2011
• Datum odevzdání tištěné podoby: 05.08.2011
• Datum proběhlé obhajoby: 12.09.2011
• Oponenti: doc. RNDr. Ing. Miloš Kopa, Ph.D.

Zásady pro vypracování

Ř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.

Seznam odborné literatury

[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