20.500.12556/DKUM-57048 Hibridni algoritmi za barvanje grafov Hybrid algorithms for graph coloring Tema magistrskega dela je barvanje grafov s pomoˇcjo hibridnih algoritmov. V magistrskem delu predstavimo algoritem za barvanje grafa z variabilnim lokalnim iskanjem in hibridni algoritem za barvanje grafa, ki združuje evolucijski algoritem z lokalnim iskanjem. Nazadnje še predstavimo hibridni algoritem za barvanje grafa, ki deluje po principu algoritma za variabilno lokalno iskanje. Magistrsko delo je razdeljeno v osem sklopov. V prvem sklopu so navedeni osnovni pojmi in definicije. V drugem sklopu sledi pregled hevristiˇcnih metod za barvanje grafa. V tretjem sklopu je opisan standardni algoritem za variabilno lokalno iskanje. V ˇcetrtem sklopu je predstavljen prilagojen algoritem za variabilno lokalno iskanje za optimizacijski problem barvanja grafa. V petem sklopu so predstavljeni evolucijski algoritmi. V šestem sklopu so predstavljeni splošni hibridni algoritmi za barvanje grafa. Sklop zakljuˇcimo s hibridnim algoritmom za barvanje grafa, ki deluje po principu algoritma za variabilno lokalno iskanje. V sedmem sklopu je opis programa v programskem jeziku C++. V zadnjem sklopu so predstavljeni rezultati algoritmov za reševanje problema barvanja grafa na nekaterih izbranih primerih. This thesis focuses on graph coloring with the use of hybrid algorithms. In the work we present the algorithm for graph coloring with variable neighborhood search as well as the hybrid algorithm for graph coloring, which unites evolutionary algorithm and local search. Last but not the least we present hybrid algorithm for graph coloring that operates according to the variable neighborhood search principle. This master thesis is divided into eight parts. In the first part, we describe basic concepts and definitions. Following in the second part is an overview of heuristic methods for graph coloring. The third part describes standard variable neighborhood search algorithm. The fourth part presents adapted variable neighborhood search algorithm for the graph coloring optimization problem. In the fifth part, evolutionary algorithms are described. In the sixth part, hybrid algorithms for graph coloring are presented. We conclude this part with the hybrid algorithm for graph coloring that operates according to the variable neighborhood search principle. In the seventh part, the program description in the programming language C++ is presented, and in the final part, the results of algorithms for solving the graph coloring problems are presented. algoritmi grafi barvanje grafa lokalno iskanje variabilno lokalno iskanje evolucijski algoritmi hibridni algoritmi algorithms graphs graph coloring local search variable neighborhood search evolutionary algorithms hybrid algorithms true true false [M. Duh] Slovenski jezik Angleški jezik Magistrsko delo/naloga 2016-01-06 18:22:28 2016-02-15 15:40:59 2022-06-13 03:05:33 2021-05-15 03:37:20 2016 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.421.2:519.174.7(043.2) 21896456 URN:SI:UM:DK:E4PC6S81 MAG_Duh_Martin_2016.pdf MAG_Duh_Martin_2016.pdf 1 87E3E6D26735D7F0C5A483469942EC4C 194c77a935561c734baf7d398a139dcb4720a40a1885c2705bab539b9eac570f dbb320ca-7c0b-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=85316 Fakulteta za naravoslovje in matematiko 0 0 0