Posplošena električna dominacijaOMERZEL, ALEŠ (Avtor) Klavžar, Sandi (Mentor) električna dominacijaposplošena električna dominacijadrevoJavaNP-poln problem.Problem električne dominacije je optimizacijski problem, ki se je pojavil v novodobnem času skupaj z razvojem električnih omrežij. V električnem omrežju je potrebno nadzorovati tok in napetost na vseh stičiščih in povezavah. Merilne naprave so drage, zato vlada težnja h postaviti najmanjšega števila naprav tako, da bi omrežje ostalo v celoti nadzorovano. Problem električne dominacije se posploši na problem k-električne dominacije. V diplomski nalogi so z definicijo obeh problemov predstavljena pravila za širjenje nadzora v omrežju. Za tem je podan in dokazan linearen algoritem za iskanje optimalne k-električne dominantne množice na drevesih. Sledi implementacija algoritma v programskem jeziku Java. V zaključku pa je dokazana NP-polnost problema električne dominacije na dvodelnih grafih.20142014-09-12 15:55:03Diplomsko delo/naloga29455VisID: 14051COBISS_ID: 10783828sl