Original title: Teorie grafů - implementace vybraných problémů
Translated title: Graph theory - implementation of selected problems
Authors: Stráník, František ; Rajmic, Pavel (referee) ; Koutný, Martin (advisor)
Document type: Master’s theses
Year: 2009
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií
Abstract: [cze] [eng]
Tato práce je zaměřena na seznámení se základními problémy z oblasti teorie grafů. Jsou zde popsány základní pojmy i složitější problémy. Jedna část práce je zaměřena na práci s jednotlivými typy grafů. Začíná se s jednosměrně vázaným seznamem, přes obousměrně vázaný seznam až po stromy, které reprezentují nejjednodušší grafové struktury. Další část práce se potom věnuje grafu jako celku a popisuje složitější problémy a jejich řešení. Mezi tyto problémy patří vyhledávání v grafech pomocí metod DFS (Depth First Search) a BFS (Breadth First Search). Dále potom hledání nejkratší cesty za pomoci specifických algoritmů jako jsou: Dijkstrův algoritmus, Floyd-Warshallův algoritmus a Bellman-Fordův algoritmus. Poslední část je věnována problematice vyhledávaní minimálních koster grafu s využití metod Kruskalova haldového algoritmu, Jarníkova (Primova) algoritmu a Borůvkova algoritmu. This work is intended on identification with basic problems from the graphs theory area. There are the basic conceptions as well more complicated problems described. The one part of this work is specialized in working of individual types of graphs. It starts with single linked list through double linked list after as much as trees which represented the simplest graphs textures. The other part of this work devotes to the whole graph and describes more complicated problems and their resolution from the theory graphs area. Among these problems belongs to searching in graphs help by Depth First Search and Breadth First Search methods. Then searching the shortest way help by the specific algorithms as are: Dijkstra´s algorithm, Floyd-Warshall´s algorithm and Bellman-Ford´s algorithm. The last part is devoted to problems with searching minimal frames of graphs with usage Kruskal´s algorithm, Jarnik´s algorithm and Boruvka´s algorithm methods.
Keywords: Bellman-Ford´s algorithm; BFS; Boruvka´s algorithm; DFS; Dijkstra´s algorithm; Floyd-Warshall´s algorithm; graphs theory; Jarnik´s algorithm; Kruskal´s algorithm; search tree; Bellman-Fordův algoritmus; BFS; Borůvkův algoritmus; DFS; Dijkstrův algoritmus; Floyd-Warshallův algoritmus; Jarníkův algoritmus; Kruskalův algoritmus; teorie grafů; vyhledávací strom

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/10188

Permalink: http://www.nusl.cz/ntk/nusl-218082


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses