Hevristični algoritem za 3-barvanje grafov

magistrsko delo

Luka Arnečič (Author), Andrej Taranenko (Mentor)

Abstract

Magistrsko delo obravnava hevristični algoritem za 3-barvanje grafov, ki temelji na hibridiziranem evolucijskem algoritmu in se lahko uporabi za ugotavljanje dobre 3-obarvljivosti navadnih neusmerjenih grafov. Najprej razložimo matematične osnove problema in predstavimo algoritme, na katerih temelji naš hevristični algoritem, nato ga opišemo, na koncu pa predstavimo primerjavo hevrističnega algoritma z algoritmi uporabljenimi in opisanimi v osnovnem članku [9]. V prvem delu razložimo matematične osnove, ki so potrebne za razumevanje problema dobrega 3-barvanja grafov in predstavimo osnovne zasnove algoritmov, na katerih temelji hevristični algoritem. V drugem delu predstavimo hevristični algoritem po komponentah ter podatkovne strukture, ki so uporabljene v hevrističnem algoritmu. Vsako komponento algoritma natančno opišemo in predstavimo idejo, za katero je bila uporabljena. V tretjem delu predstavimo primerjavo hevrističnega algoritma z algoritmi, uporabljenimi in opisanimi v osnovnem članku [9].

Keywords

barvanje grafov;algoritmi na grafih;diskretni algoritmi;hevristike;magistrska dela;

Data

Language:	Slovenian
Year of publishing:	2015
Typology:	2.09 - Master's Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[L. Arnečič]
UDC:	004.421.2:519.174.7(043.2)
COBISS:	21895944
Views:	1300
Downloads:	123
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	A heuristic algorithm for graph 3-coloring
Secondary abstract:	This thesis focuses on a heuristic algorithm for 3-coloring of graphs, based on hybrid evolutionary algorithm. It can be used for testing, if a normal unidirectional graph can be properly 3-colored. First, we explain the mathematical background of the problem and present the algorithms on which our heuristic algorithm is based on, then we describe the heuristic algorithm itself. At the end, we present a comparison of the heuristic algorithm with algorithms used and described in [9]. In the first part we explain the mathematical basis necessary for the understanding of the problem of proper 3-colorings of graphs and present the basic algortihm concepts on which our heuristic algorithm is based on. In the second part we present the heuristic algorithm by components and data structures used in the heuristic algorithm. We describe each component of the algorithm and present an idea of why it was used. In the third part we present a comparison of a heuristic algorithm with algorithms used and described in [9].
Secondary keywords:	force-directed algorithms;graphs;graphs drawing;master theses;
URN:	URN:SI:UM:
Type (COBISS):	Master's thesis/paper
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	IX, 49 f.
ID:	9077130