Publikace: Aplikace úlohy o minimální kostře grafu
Diplomová práceopen accessNačítá se...
Datum
Autoři
Launerová, Monika
Název časopisu
ISSN časopisu
Název svazku
Nakladatel
Univerzita Pardubice
Abstrakt
Cílem práce je použití algoritmů minimální kostry grafu v reálných aplikacích. Jsou zde popsány tři nejznámější přístupy, Borůvkův, Jarníkův a Kruskalův. Tyto postupy se využívají v různých úlohách jako součást celkového řešení. Z těchto úloh práce zmiňuje problém obchodního cestujícího. Dále jsou zmíněny některé modifikace základní úlohy. V praktické části jsou pak tyto postupy použity v reálné aplikaci.
Popis
Klíčová slova
Borůvkův algoritmus, historie problému minimální kostry grafu, Christofidova metoda, Jarníkův algoritmus, Kruskalův (hladový) algoritmus, metoda zdvojení minimální kostry, minimální kostra grafu, minimální perfektní párování, problém obchodního cestujícího, teorie grafů, Borůvka's algorithms, history of minimal (cost) spanning tree, Christofides' algorithms, Jarník's algorithms, Kruskal's (hungry) algorithms, double minimum spanning tree, minimal (cost) spanning tree, minimum perfect matching, traveling salesman problem, graph theory