Název:
Barvení grafu, klika v grafu, algoritmy a aplikace
Překlad názvu:
Graph Colouring, Graph Clique, Algorithms and Applications
Autoři:
Valachová, Alžbeta ; Dvořák, Jiří (oponent) ; Šeda, Miloš (vedoucí práce) Typ dokumentu: Diplomové práce
Rok:
2023
Jazyk:
cze
Nakladatel: Vysoké učení technické v Brně. Fakulta strojního inženýrství
Abstrakt: [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.
Klíčová slova:
algoritmus; aplikácie; Farbenie grafu; heuristické metódy; maximálna klika; NP-úplný problém; algorithm; applications; Graph coloring; heuristic methods; maximal clique; NP-complete problem
Instituce: Vysoké učení technické v Brně
(web)
Informace o dostupnosti dokumentu:
Plný text je dostupný v Digitální knihovně VUT. Původní záznam: http://hdl.handle.net/11012/212262