Hevristični algoritem za 3-barvanje grafov

magistrsko delo

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

Povzetek

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].

Ključne besede

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

Podatki

Jezik:	Slovenski jezik
Leto izida:	2015
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[L. Arnečič]
UDK:	004.421.2:519.174.7(043.2)
COBISS:	21895944
Št. ogledov:	1300
Št. prenosov:	123
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	A heuristic algorithm for graph 3-coloring
Sekundarni povzetek:	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].
Sekundarne ključne besede:	force-directed algorithms;graphs;graphs drawing;master theses;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Magistrsko delo/naloga
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	IX, 49 f.
ID:	9077130