Problem krepkih povezavnih geodetskih množicVidrih, Eva (Avtor) Klavžar, Sandi (Mentor) problem krepkih povezavnih geodetskih množicpolni večdelni grafigrafi Sierpinskegakartezični produkt grafovProblem 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.20252025-10-02 08:15:05Doktorsko delo/naloga174411sl