Odprto pakiranje povezav grafaKeše, Aleksandra (Avtor) Dravec, Tanja (Mentor) odprto pakiranje povezavpovezavno odprto pakirno številodrevočasovna zahtevnost algoritmaNP-poln problemV 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.[A. Keše]20252025-05-20 15:01:27Magistrsko delo/naloga92869UDK: 519.17(043.2)COBISS_ID: 241649923sl