VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Problem krepkih povezavnih geodetskih množic : doktorska disertacija
    Vidrih, Eva
    Problem krepkih povezavnih geodetskih množic predstavlja iskanje take najmanjše podmnožice ▫$U$▫ vozlišč grafa ▫$G$▫, za katero je mogoče vsakemu paru vozlišč iz ▫$U$▫ prirediti tako najkrajšo pot ... med njima, da bodo te najkrajše poti pokrile vse povezave grafa ▫$G$▫. Ker je problem krepkih povezavnih geodetskih množic NP-težek problem, skozi disertacijo podamo rešitve problema na posameznih družinah grafov. V vsaki krepki povezavni geodetski množici grafa so vsa simplicialna vozlišča, kar nam da rešitev v primeru dreves, zvezd, polnih grafov in še mnogih drugih. Prav tako so v vsaki krepki geodetski množici tudi vsa vozlišča, ki imajo dominantnega soseda. S pomočjo te lastnosti, med drugim določimo grafe, za katere je edina krepka povezavna geodetska množica kar množica vseh vozlišč. Določimo tudi grafe, za katere je krepka povezavna geodetska množica moči ▫$n(G) − 1$▫. Velik del disertacije je namenjen raziskavi problema na kartezičnih produktih grafov. Za kartezične produkte ▫$P_n \square P_m$▫ podamo rešitev problema, če je ▫$m$▫ enak ▫$2$▫, ▫$3$▫ ali ▫$4$▫, ter dve splošni zgornji meji za ostale primere, medtem ko za krepke produkte podamo rešitev v vseh primerih. Problem je zanimiv tudi na polnih večdelnih grafih, za katere tudi podamo rešitev. Problem na grafih Sierpińskega je soroden problemom geodetskih množic, krepkih geodetskih množic ter povezavnih geodetskih množic. V disertaciji sicer podamo zgornjo mejo velikosti najmanjše krepke povezavne geodetske množice, a domnevamo, da je ta meja točna.
    Vrsta gradiva - disertacija ; neleposlovje za odrasle
    Založništvo in izdelava - Ljubljana : [E. Vidrih], 2025
    Jezik - slovenski
    COBISS.SI-ID - 251412483

    Povezava(-e):

    Repozitorij Univerze v Ljubljani – RUL

Knjižnica/institucija Kraj Akronim Za izposojo Druga zaloga
FMF in IMFM, Matematična knjižnica, Ljubljana Ljubljana MAKLJ v čitalnico 1 izv.
Narodna in univerzitetna knjižnica, Ljubljana Ljubljana NUK v čitalnico 1 izv.
ni za izposojo 1 izv.
loading ...
loading ...
loading ...

Vnos na polico