20.500.12556/DKUM-95013 Hevristika za particijsko dimenzijo grafov magistrsko delo A Heuristics for the partition dimension of graphs na študijskem programu 2. stopnje Matematika V magistrskem delu razvijemo in predstavimo hevristiko za izračun particijske dimenzije grafa. Pričnemo s pregledom temeljnih pojmov iz teorije grafov in nekaterih osnovnih družin grafov, nato uvedemo pojem particijske dimenzije grafa, pri čemer posebno pozornost namenimo drevesom in monocikličnim grafom. V nadaljevanju obravnavamo temeljne koncepte teorije optimizacijskih problemov ter pojma hevristike in evolucijskega računanja. Sledi predstavitev zasnove in implementacije razvite hevristike v programskem jeziku Python. Zaključimo s predstavitvijo rezultatov testiranj razvite hevristike na različnih družinah grafov z znano optimalno vrednostjo particijske dimenzije ter rezultate preverjanja domneve »če je $T$ vpeto drevo monocikličnega grafa $G$, potem je $pd(G) \leq pd(T) + 1$«. Dobljene rezultate primerjamo z že znanimi vrednostmi. In this master’s thesis, we develop and present a heuristic for computing the partition dimension of a graph. We begin with a review of fundamental concepts from graph theory and some basic families of graphs, then we introduce the definition of the partition dimension of a graph, paying particular attention to trees and unicyclic graphs. Next, we discuss basic concepts from the theory of optimization problems, as well as the notions of heuristics and evolutionary computation. We then present the design and implementation of the developed heuristic in the Python programming language. Finally, we report the results of testing the developed heuristic on various families of graphs with known optimal partition dimension values, and the results of verifying the conjecture »if $T$ is a spanning tree of a unicyclic graph $G$, then $pd(G) \leq pd(T) + 1$«. These results are subsequently compared with those already established in the literature. particijska dimenzija grafa monociklični grafi hevristika evolucijski algoritem partition dimension of a graph monocyclic graphs heuristics evolutionary algorithm true true false [L. Denko] Slovenski jezik Angleški jezik Magistrsko delo/naloga 2025-09-01 22:16:19 2025-09-19 08:25:58 2025-09-29 14:06:45 0000-00-00 00:00:00 2025 0 Maribor 0 Maribor VIII, 51 str. 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17(043.2) 249541891 MAG_Denko_Laura_2025.pdf MAG_Denko_Laura_2025.pdf 1 FD8571876A457321BA6A429BD5BB86CF 085708278c0e2959d0d51c15fb4fd19a69d58bc32b4be4f255d56beb57b5b57a 663da284-883b-11f0-96a7-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=197396 Fakulteta za naravoslovje in matematiko 0 0 0