Projekat 144015

Teorija grafova i matematičko programiranje sa primenama u hemiji i tehničkim naukama

Rukovodilac: akademik Dragoš Cvetković

Rezime

Predmet istraživanja su odabrane teme iz teorije grafova i matematičkog programiranja i neke njihove dodirne oblasti. Teorija grafova spada u prioritetne teme diskretne matematike, a matematičko programiranje u prioritetne teme numeričke matematike (operaciona istraživanja i optimizacija). Značajan deo istraživanja biće posvećen teoriji spektara grafova, linearnom I semidefinitnom programiranju. Objedinjujuća disciplina za teoriju grafova i matematičko programiranje je kombinatorna optimizacija u kojoj će pažnja biti posvećena interakcijama teorije spektara grafova i semidefinitnog programiranja. Obrađivaće se primene grafova i njihovih spektara u matematičkoj hemiji, racunarstvu i drugim tehnickim disciplinama.

Predmet, opis i značaj istraživanja

Istraživanja iz oblasti teorije spektara grafova uključivala bi sledeću tematiku:
1. Ekstremalni problemi sa najvećom sopstvenom vrednošću grafa,
2. Grafovi sa ograničenom drugom sopstvenom vrednošću,
3. Grafovi sa najmanjom sopstvenom vrednošću -2,
4. Grafovi sa celobrojnim spektrom,
5. Proučavanje sopstvenih potprostora grafova, a posebno uglova grafova,
6. Tehnika zvezdanih komplemenata,
7. Hereditarne spektralne osobine grafova,
8. Proučavanje grafovskih invarijanti koje se koriste za opisivanje fizičko-hemijskih karakteristika organskih jedinjenja,
9. Proučavanje energije grafa i srodnih grafovskih invarijanti,
10. Istraživanja u teoriji grafova u vezi sa rastojanjem u grafu, Laplasovim i običnim spektrom grafova,
11. Spektralne osobine fulerena,
12. Razvoj i korišćenje odgovarajućeg softvera (paket newGRAPH).

Iz oblasti matematičkog programiranja planira se rad na sledećim problemima:
1. Numerička nestabilnost unutrašnjih metoda za linearno programiranje i implementacija stabilizacionih postupaka,
2. Egzaktne i heurističke metode za globalnu optimizaciju,
3. Unutrašnje metode za semidefinitno programiranje,
4. Stabilizacija metode težinskih najmanjih kvadrata.

U oblasti kombinatorne optimizacije posebna pažnja biće posvećena problemu trgovačkog putnika zbog njegove interesantnosti u teorijskim istraživanjima (nalazi se na listi 10 najpoznatijih nerešenih problema matematike) i značaja u primenama. Obrađivaće se posebno semidefinitna relaksacija problema trgovačkog putnika i metode grananja, ograničavanja i odsecanja zasnovane na semidefinitnoj relaksaciji. Metode grananja, ograničavanja i odsecanja biće primenjene i u transportu pri tretiranju optimizacije upravljanja saobraćajem na signalisanim raskrsnicama. Značajna pažnja će se posvetiti metaheuristikama a posebno metodi promenljivih okolina i genetskim algoritmima kao i primenama metaheuristika i spektralnih tehnika na probleme paralelizacije računarskih procesa.

Korišćenje dekompozicionih teorema za grafove u cilju dobijanja polinomijalnih algoritama za nalaženje dimenzije najveće klike ili stabilnog skupa ili za određivanje hromatskog broja grafa. Iako su ovi problemi NP-potpuni u opštem slučaju, dokazano je na primer za perfektne grafove da se oni mogu rešiti u polinomijalnom vremenu uz korišćenje elipsoidnog algoritma. Od interesa je da se ispita da li se ovi optimizacioni problemi za perfektne grafove mogu rešiti pravim kombinatornim algoritmima u polinomijalnom vremenu.

Planirana istraživanja predstavljaju prirodan nastavak uspešnih višedecenijskih istraživanja i međunarodne saradnje. Specijalno, delatnost ove grupe istraživaca je bila objedinjena u periodu 2001 - 2005 u okviru projekta br. 1389 osnovnih istraživanja "Teorija grafova I matematičko programiranje sa primenama u hemiji i transportu" koji je bio finansiran od strane odgovarajućeg ministarstva Republike Srbije. I dalje se očekuje objavljivanje naučnih monografija u inostranstvu, organizovanje međunarodnih skupova, predavanja po pozivu na međunarodnim skupovima, studijski boravci u inostranstvu po pozivu i druge aktivnosti, dobrim delom finansijski pokrivene od stranih partnera.

Planirani rezultati projekta

Sva planirana istraživanja imaju originalan karakter, što će biti verifikovano objavljivanjem u odgovarajućim uglednim publikacijama uključujući naučne monografije kod renomiranih inostranih izdavača. Glavni cilj je publikovanje većeg broja kvalitetnih radova i izvesnog broja monografija.Očekuje se da se time održi visoka međunarodna pozicija grupe istraživača koja se bavi teorijom spektara grafova i primenama u matematičkoj hemiji. Potvrdiće se visok kvalitet istraživanja iz matematičkog programiranja. Negovaće se međunarodna saradnja uključivanjem inostranih koautora u obradu pojedinih tema. Vodiće se računa o primenljivosti rezultata čemu će doprineti razvoj algoritama i pratećeg softvera.