Abstract (in Serbian)

Проблеми оптимизације на графовима подразумевају потрагу за графовима датих карактеристика који минимизују или максимизују одређену инваријанту или комбинацију инваријанти. Ови проблеми су обично NP-тешки и исцрпно набрајање свих могућности није прихватљиво. Ефикасно решавање ових проблема може помоћи теоретичарима да добију неке идеје и информације неопходне за извођење аналитичког (теоријског доказа). Рачунарски потпомогнути докази су уобичајени у теорији графова већ неко време. Развијено је неколико наменских софтверских пакета, као што су AutoGraphiX (https://www.autographix.ca), newGraph (https://www.mi.sanu.ac.rs/newgraph/),
PHOEG (https://phoeg.umons.ac.be/phoeg) и сл. Међутим, они су превише општи и у неким случајевима могу захтевати неприхватљиво дуго време рада рачунара да би пружили корисне резултате. Још један популаран приступ је развој метахеуристичких алгоритама прилагођених сваком појединачном проблему. Као примери оваквог приступа, илустроване су примене метахеуристике Метода променљивих околина (Variable Neighborhood Search, VNS) на спектралну реконструкцију графова и максимизацију спектралног радијуса повезаних графова. Предложени алгоритми су тестирани на репрезентативном скупу графова. Спроведена експериментална евалуација показује супериорност предложеног приступа у односу на примену наменског софтвера. Рад је делимично подржан од стране Фонда за науку Републике Србије, преко пројекта #6767: Lazy walk counts and spectral radius of graphs, LZWK.

Истраживања су спроведена у сарадњи са колегама Драганом Стевановићем, Предрагом Ђорђевићем, Робертом Дожом, Луком Радановићем, Марком Миленковићем и Милицом Анђелић. Програмирање и експерименте вршили су студенти у оквиру летње истраживачке праксе коју организује МИСАНУ.

      

Keywords: Екстремални проблеми на графовима, теоријски докази, исцрпно набрајање, наменски софтвер, непотпуна претрага