Original title: Barvení grafu, klika v grafu, algoritmy a aplikace
Translated title: Graph Colouring, Graph Clique, Algorithms and Applications
Authors: Valachová, Alžbeta ; Dvořák, Jiří (referee) ; Šeda, Miloš (advisor)
Document type: Master’s theses
Year: 2023
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta strojního inženýrství
Abstract: [cze] [eng]
Táto diplomová práca sa zaoberá problematikou farbenia grafu a hľadaním kliky v grafe, s dôrazom na popis algoritmov a ich aplikácie. Farbenie grafu je proces priraďovania farieb jednotlivým vrcholom grafu tak, aby susedné vrcholy mali odlišné farby. Táto problematika je dôležitá pre riešenie rôznych optimalizačných úloh. Práca sa zameriava aj na hľadanie kliky v grafe, čo je dôležitý problém v analýze sociálnych sietí alebo rozpoznávaní obrazov. Cieľom práce je poskytnúť komplexný prehľad o~farbení grafu, hľadaní kliky v grafe, predstaviť a analyzovať existujúce algoritmy a ukázať ich aplikácie v praxi. This thesis deals with the problem of graph coloring and finding cliques in a graph, with a focus on the description of algorithms and their applications. Graph coloring is the process of assigning colors to individual vertices of a graph so that adjacent vertices have different colors. This issue is important for solving various optimization problems. The work also focuses on finding cliques in a graph, which is an important problem in social network analysis or image recognition. The aim of this thesis is to provide a complex overview of graph coloring, finding cliques in a graph, introduce and analyze existing algorithms and show their applications in practice.
Keywords: algorithm; applications; Graph coloring; heuristic methods; maximal clique; NP-complete problem; algoritmus; aplikácie; Farbenie grafu; heuristické metódy; maximálna klika; NP-úplný problém

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/212262

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


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