Neprerezne neodvisne množiceKerkoč, Matija (Avtor) Klavžar, Sandi (Mentor) neprerezne neodvisne množicepovezana vozliščna pokritjaneodvisnostno število$\mathcal{Z}$-množicekartezični produkt grafovnačrtovanje omrežijV magistrski nalogi obravnavamo neprerezne neodvisne množice. Začeli bomo z definicijo neprereznega neodvisnostnega števila grafa ter njegovimi osnovnimi lastnostmi. Pokažemo povezavo med neprereznimi neodvisnimi množicami ter povezanimi vozliščnimi pokritji v grafu. Glavnina magistrske naloge je posvečena problemu iskanja največjih neprereznih neodvisnih množic (problem MaxNNM). Najprej pokažemo, da je problem rešljiv v polinomskem času za kubične grafe, tetivne grafe ter hiperkocke, nato pa se ukvarjamo z družinami za katere je problem NP-težek. Glavni rezultat je določitev neprereznega neodvisnostnega števila za kartezične produkte dveh ciklov. Ker je problem tesno povezan z računalništvom, bomo v nalogi raziskali algoritme za reševanje problema MaxNNM ter njihovo računsko zahtevnost za različne grafe. Omenili bomo tudi nekatere druge različice problema. Reševanje omenjenega problema porodi bogate aplikacije v vsakdanjem življenju, zato bomo zaključili s pregledom le teh.20242024-09-22 08:15:10Magistrsko delo/naloga162403sl