20.500.12556/DKUM-92869 Odprto pakiranje povezav grafa na študijskem programu 2. stopnje Izobraževalna matematika Edge open packing sets in graphs magistrsko delo V magistrskem delu preučujemo lastnosti odprtega pakiranja povezav grafa. Za lažje razumevanje obravnavanega pojma najprej predstavimo osnovne pojme in rezultate iz teorije grafov ter opišemo osnovne družine grafov. V drugem delu magistrske naloge opišemo pojma odprto pakiranje povezav in povezavno odprto pakirno število ter ju predstavimo na osnovnih družinah grafov. Tretji del magistrske naloge je namenjen preučevanju mej za povezavno odprto pakirno število poljubnega grafa in identificiranju družin grafov, ki te meje dosežejo. V zadnjem delu magistrske naloge obravnavamo problem odprtega pakiranja povezav grafa kot NP-poln problem za grafe z univerzalnim vozliščem, Eulerjeve dvodelne grafe in ravninske grafe z maksimalno stopnjo največ 4. Opišemo postopek za izračun povezavnega odprtega pakirnega števila dreves in zapišemo, da obstaja algoritem, ki to število poišče v linearnem času. In this thesis we study the properties of edge open packing sets in graphs. To facilitate the understanding of investigated concept, we first introduce fundamental concepts and results from graph Theory and describe basic graph families. We also explain the concept of algorithm complexity and NP-completeness. In the second part of the thesis we define the concepts of edge open packing set and edge open packing number of a graph and investigate the both concepts in special graph families. The third part is dedicated to studying the bounds for the edge open packing number and identifying graph families that achive these bounds. In the final part of the thesis we examine the problem of edge packing sets as an NP-complete problem for graphs with universal vertex, Eulerian bipartite graphs and planar graphs of maximum degree at most 4. We describe the procedure for computing the edge open packing number of trees and state that there exists an algorithm that finds said number in linear time. odprto pakiranje povezav povezavno odprto pakirno število drevo časovna zahtevnost algoritma NP-poln problem edge open packing set edge open packing number tree time complexity of an algorithm NP-complete problem true true false [A. Keše] Slovenski jezik Angleški jezik Magistrsko delo/naloga 2025-05-20 15:01:27 2025-07-07 14:30:19 2025-07-08 03:06:49 0000-00-00 00:00:00 2025 0 Maribor 0 Maribor VIII, 60 f. 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17(043.2) 241649923 MAG_Kese_Aleksandra_2025.pdf MAG_Kese_Aleksandra_2025.pdf 1 93126F933B5ADF11F682BD9D02779D71 b5abeb1ad0e197f7c517fd1b2dda23ee616da3e3836ea6dbf0a32313dfb35eb2 aa687158-357d-11f0-88c4-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=191139 Fakulteta za naravoslovje in matematiko 0 0 0