Projekat 174033

Teorija grafova i matematičko programiranje sa primenama u hemiji i računarstvu

Rukovodilac: Slobodan Simić, naučni savetnik

Rezime

Predmet istraživanja su odabrane teme iz teorije grafova i matematičkog programiranja i neke njihove dodirne oblasti. Značajan deo istraživanja biće posvećen teoriji spektara grafova, strukturnoj teoriji grafova, nelinearnom programiranju i globalnoj optimizaciji. 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, računarstvu i drugim tehničkim disciplinama. Primene u hemiji uključuju pruočavanje matematičkih osobina molekulskih strukturnih deskriptora, naročito onih zasnovanih na spektrima i metrici grafova. Primene u računarstvu se odnose na strukturu i pretraživanje interneta, multiprocesorske mreže i kvantno računarstvo. U svim oblastima značajna pažnja se posvećuje konstrukciji algoritama i pruočavanju njihove kompleksnosti. U istraživanjima značajnu ulogu igra razvoj i korišćenje specijalizovanog softvera tako da projekat ima karakteristike teorijsko - eksperimentalnog projekta. Projekat ima oko 30 istraživača i predstavlja nastavak sličnih naučnih projekata iz nekoliko prethodnih decenija. Značajna pažnja se posvećuje radu sa doktorskim studentima kojih ima jedanaest u timu istraživača.

Ključne reči: teorija grafova, matematičko programiranje, spektri grafova, teorijska hemija, računarstvo

Opis istraživanja

U okviru rada projekta obrađivaće se sledeće istraživačke oblasti koje se međusobno prepliću:

1) Spektralna teorija grafova (rukovodilac S. Simić),
2) Hemijska teorija grafova (rukovodilac I. Gutman),
3) Matematičko programiranje (rukovodilac V. Vujčić),
4) Strukturna teorija grafova i algoritmi (rukovodilac K.Vušković),
5) Spektri grafova u računarstvu (rukovodilac D. Stevanović).

1) Spektralna teorija grafova
Spektralna teorija grafova je teorija u kojoj se grafovi pruočavaju uz pomoć sopstvenih vrednosti matrice M koja se na određeni način pridružuje grafu. Takva teorija se naziva M-teorija. često korišćene grafovske matrice su matrica susedstva A, Laplasova matrica L i nenegativna Laplasova matrica Q=D+A, gde je D dijagonalna matrica stepena čvorova. Koriste se i druge grafovske matrice. Najopštije uzev, spektralna teorija grafova je objedinjenje svih takvih posebnih teorija zajedno sa sredstvima za interakciju među njima.
Istraživanja iz oblasti teorije spektara grafova uključivala bi sledeću tematiku:

01. Ekstremalni problemi sa najvećom sopstvenom vrednošću grafa,
02. Grafovi sa ograničenom drugom sopstvenom vrednošću,
03. Grafovi sa najmanjom sopstvenom vrednošću -2,
04. Grafovi sa celobrojnim spektrom,
05. Pruočavanje sopstvenih potprostora grafova, a posebno uglova grafova,
06. Tehnika zvezdanih komplemenata,
07. Hereditarne spektralne osobine grafova,
08. Pruočavanje grafovskih invarijanti koje se koriste za opisivanje fizičko-hemijskih karakteristika organskih jedinjenja,
09. Pruočavanje energije grafa i srodnih grafovskih invarijanti,
10. Istraživanja u teoriji grafova u vezi sa prethodnom temom i sa rastojanjem u grafu, Laplasovim i nenegativnim Laplasovim spektrom grafa,
11. Tačke nagomilavanja za pojedine sopstvene vrednosti unutar nekih klasa grafova
12. Perturbacioni problemi vezani za najveću (najmanju) sopstvenu vrednost
13. Laplasov i neoznačeni Laplasov spektar (veze između odgovarajućih spektara)
14. Problemi određenosti grafova raznim spektrima
15. Razvoj i korišćenje odgovarajućeg softvera (paket newGRAPH, smallGRAPHS, nadogradnja programa Mathematica).

2) Hemijska teorija grafova
Grafovi predstavljaju prirodni matematički model molekula, i mnogo se koriste u hemijskim istraživanjima. Pogodno izabrane grafovske invarijante (poznate pod imenom "molekulski strukturni deskiptori" ili "topološki indeksi") odslikavaju pojedine detalje u strukturi molekula i primenjuju se pri matematičkom modeliranju fizičko-hemijskih, farmakoloških, toksikoloških i drugih osobina hemijskih jedinjenja. Naša istraživanja baviće se pruočavanjem matematičkih osobina molekulskih strukturnih deskriptora, naročito onih zasnovanih na spektrima i metrici grafova, kao i primenama dobijenih rezultata u hemiji.

3) Matematičko programiranje
U okviru ove istraživačke teme planira se rad na matematičkom modeliranju optimizacionih problema, kao i razvoj algoritama za rešavanje problema kombinatorne optimizacije, nelinearnog programiranja i globalne optimizacije.
Iz oblasti matematičkog programiranja planira se rad na sledećim problemima:

01. Numerička nestabilnost unutrašnjih metoda za linearno programiranje i implementacija stabilizacionih postupaka,
02. Egzaktne i heurističke metode za globalnu optimizaciju,
03. Unutrašnje metode za semidefinitno programiranje,
04. Stabilizacija metode težinskih najmanjih kvadrata.

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.

4) Strukturna teorija grafova i algoritmi
Kreiranje efikasnih algoritama za rešavanje kombinatornih problema je od izuzetne važnosti za moderno tehnološko društvo, zbog primena u različitim oblastima kao što su transport, telekomunikacije, molekularna biologija, inženjerstvo, itd. Mnoge od ovih primena se mogu modelirati uz pomoć grafova, i problemi se tada svode na optimizaciju određenih klasičnih parametara, kao što su bojenje grafova i traženje maksimalne klike u grafu. Ovi problemi su generalno netraktabilni, ali postaju traktabilni na specijalnim klasama grafova, posebno hereditarnim klasama. Mi predlažemo izučavanje strukture hereditarnih klasa grafova, u pokušaju da razvijemo generalne metode korišćenja strukture grafa u kreiranju efikasnih algoritama za kombinatornu optimizaciju.

5) Spektri grafova u računarstvu
Spektralne osobine grafova su među najvažnijim grafovskim invarijantama koje se mogu izračunati u polinomijalnom vremenu. u ovoj temi će se istraživati značenje i mogućnosti korišćenja sopstvenih vektora i sopstvenih prostora grafovskih matrica u većem broju problema iz oblasti računarstva:

- topološke karakteristike kompleksnih mreža: ekspanzivnost, određivanje topoloških i funkcionalnih uskih grla, organizacija klastera, globalna povezanost čvorova
- kvantno računarstvo: transfer kvantnih stanja, kontrolabilnost, određivanje hamiltonijana u modelima kvantnih mreža predstavljenih matricama susedstva i Laplasovom matricom grafa
- multiprocesorske mreže: algoritmi za balansiranje opterećenja, predlaganje mreža sa pogodnim spektralnim i kombinatornim osobinama
- prepoznavanje oblika: svojstva Iharine zeta funkcije i njihova primena

Planirana istraživanja predstavljaju prirodan nastavak uspešnih višedecenijskih istraživanja i međunarodne saradnje. Specijalno, delatnost ove grupe istraživača 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. u periodu 2006 - 2010 istraživanja su nastavljena u okviru projekta br. 144015G osnovnih istraživanja "Teorija grafova i matematičko programiranje u hemiji i tehničkim naukama" (http://www.mi.sanu.ac.rs/projects/project144015.htm)

Naša istraživačka grupa je u prošlosti objavila i sledeće monografije na kojima se u dobroj meri zasnivaju i današnja istraživanja:

Cvetković D., Doob M., Gutman I., Torgašev A., Recent Results in the Theory of Graph Spectra, North-Holland, Amsterdam, 1988.
Cvetković D., Doob M., Sachs H., Spectra of Graphs, Theory and Application, 3rd edition, Johann Ambrosius Barth Verlag, Heidelberg--Leipzig, 1995.
Cvetković D., Rowlinson P., Simić S. K., Eigenspaces of Graphs, Cambridge University Press, Cambridge, 1997.
Cvetković D., Rowlinson P., Simić S., Spectral generalizations of line graphs: On graphs with least eigenvalue -2, Cambridge University Press, Cambridge, 2004.

Očekivani rezultati istraživanja

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.
Takođe se očekuje suorganizovanje 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.
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.
U spektralnoj teoriji grafova očekuju se rezultati posvim temama navedenim u opisu istraživanja a posebno rezultati u vezi ekstremnih problema sa sopstvenim vrednostima za matricu susedstva, Laplasovu i nenegativnu Laplasovu matricu. Dalje će se raditi na razvoju spektralne teorije grafova bazirane na nenegativnoj Laplasovoj matrici. Rešiće se jedan broj problema sa integralnim grafovima.
Očekuje se veliki broj radova iz hemijske teorije grafova: između ostalog obrađivaće se problemi sa energijom grafa, Randićevim i Vienerovim (Wiener) indeksom. Određivaće se grafovi sa ekstremalnim vrednostima molekularnih deskriptora.
Objaviće se nova monografija o primenama spektara grafova i monografija o spektralnoj teoriji grafova koja je bazirana na nenegativnoj Laplasovoj matrici.

Plan istraživanja za prvu godinu rada projekta

Među mnogobrojnim rezultatima iz spektralne teorije grafova koji će se objaviti u 2011. godini očekuju se i sledeći: karakterizacija grafova sa maksimalnim indeksom za nenegativnu Laplasovu matricu, određivanje integralnih grafova maksimalnog stepena 4, izračunavanje permanentnog polinoma grafova, kvazi-k-ciklični grafovi maksimalnog A-indeksa, grafovi sa minimalnim indeksom, rezultati o zvezdanim komplemetima, uređenje bicikličkih grafova u odnosu na Laplasov indeks.
Objaviće se veći broj radova u vezi sa molekulrnim deskriptorima: energija, Randićev i Vienerov (Wiener) indeks i dr. Određivaće se grafovi sa ekstremalnim vrednostima molekularnih deskriptora.
Očekuju se rezultati primene metaheuristika na problem određivanja metričke dimenzije grafa i na razne probleme kombinatorne i globalne optimizacije.
Izradiće se i objaviti nova monografija o primenama spektralne teorije grafova.
Zaključno sa prvom godinom rada projekta odrediće se mentori i teme disertacija za doktorske studente.

Plan istraživanja za drugu i ostale godine rada projekta

Nastaviće se istraživanja u spektralnoj i strukturnoj teoriji grafova, u primenama spektara grafova na hemiju i računarstvo i u oblasti kombinatorne i globalne optimizacije.
Planira se hibridizacija metaheurističkih i ekzaktnih metoda, paralelizacija i metaheuristika i hibrida i njihove primene na razne optimizacione probleme u raspoređivanju, teoriji lokacija, transportu i mnogim drugim oblastma.
Izradiće se i objaviti monografija o spektralnoj teoriji grafova koja je bazirana na nenegativnoj Laplasovoj matrici.
Doktorski studenti će objaviti prve radove u međunarodnim časopisima, izraditi i odbraniti svoje doktorske disertacije.

Značaj istraživanja

Spektralna teorija grafova je važna interdisciplinarna oblast nauke koja koristi metode linearne algebre za rešavanje problema u teoriji grafova i, s druge strane, je korišćena za modeliranje i tretiranje problema u hemiji, računarstvu, fizici, operacionim istraživanjima, kombinatornoj optimizaciji, biologiji, geografiji, ekonomiji i socijalnim naukama i dr.
Pored klasičnih i dobro dokumentovanih primena u hemiji, svedoci smo pojavljivanja sopstvenih vrednosti i sopstvenih vektora grafova u različitim istraživanjima u računarstvu.
Jedna od glavnih primena teorije spektara grafova u hemiji je primena u teoriji nezasićenih konjugovanih ugljovodonika koja je poznata kao Huckel-ova teorija molekularnih orbitala.
U poslednjih desetak godina je uočeno da spektri grafova imaju razne, veoma važne primene u računarstvu. Spektri grafova se pojavljuju u internet tehnologijama, racunarskoj obradi slike, prepoznavanju oblika, obradi masovnih skupova podataka, statističkim bazama podataka i u mnogim drugim oblastima. Postoji više hiljada takvih naučnih radova.
Pored klasičnih i dobro dokumentovanih primena u hemiji, svedoci smo pojavljivanja sopstvenih vrednosti i sopstvenih vektora grafova u različitim istraživanjima u računarstvu.
Treba zabeležiti da se spektri raznih grafovskih matrica pojavljuju u primenama. Matrica susedstva i Laplasova matrica se najčešće pojavljuju ali takođe i nenegativna Laplasova matrica i normirane verzije ovih matrica. Matrice incidencije, matrica rastojanja i druge matrice se takođe mogu sresti. Ponekad se u razmatranje uključuju opšte matrice umesto grafovskih, što znači da težinski grafovi preuzimaju ulogu grafova bez težina. u nekim slučajevima se pojavljuju digrafovi i hipergrafovi.
Naravno, matematičari moraju reagovati na eksploziju broja radova u računarstvu koji koriste spektre grafova biranjem za svoja sopstvena istraživanja teme iz takvih primena ili inspirisane takvim primenama.
Danas svakako nedostaje monografija koja bi sveobuhvatno tretirala primene teorije spektara grafova, kako u računarstvu tako i uopšte. Naša istraživanja mogu da dovedu do stvaranja uslova za izradu takve monografije.

REFERENCE ISTRAŽIVAČKOG TIMA

01. Cvetković D., Rowlinson P., Simić S., An Introduction to the Theory of Graph Spectra, Cambridge University Press, Cambridge, 2010, XI+364, ISBN 987-0-521-13408-8.
02. Cvetković D., Simić S.K., Towards a spectral theory of graphs based on the signless Laplacian, II, Linear Algebra and its Applications, 432 (2010), 2257-2272.
03. M. Aouchiche, F.K. Bell, D. Cvetković, P. Hansen, P. Rowlinson, S.K. Simić, D. Stevanović, Variable neighborhood search for extremal graphs, 16. Some conjectures related to the largest eigenvalue of a graph, European Journal of Operations Research, 191 (3) (2008), 661-676.
04. D. Stevanović, M. Milošević, A spectral proof of the uniqueness of strongly regular graph with parameters (81,20,1,6), European Journal of Combinatorics, 30 (2009), 957-968.
05. I. Gutman, X. Li, J. Zhang, Graph energy, in: M. Dehmer, F. Emmert-Streib (Eds.), Analysis of Complex Networks. From Biology to Linguistics, Wiley-VCH,Weinheim, Chapter 7, 2009, pp. 145-174, ISBN 987-3-527-32345-6.
06. I. Gutman, B. Furtula, M. Petrović, Terminal Wiener index, Journal of Mathematical Chemistry 46 (2009) 522-531.
07. I. Gutman, B. Furtula, A. T. Balaban, Algorithm for simultaneous calculation of Kekule and Clar structure counts, and Clar number of benzenoid molecules, Polycyclic Aromatic Compounds 26 (2006) 17-35.
08. M.Chudnovsky, G. Cornuejols, X. Liu, P. Seymour, K. Vušković, Recognizing Berge graphs, Combinatorica 25 (2) (2005) 143-186.
09. T. Kloks, H. Muller, K. Vušković, Even-hole-free graphs that do not contain diamonds: a structure theorem and its consequences, Journal of Combinatorial Theory B 99 (2009) 733-800.
10. N. Mladenović, M. Dražić, V. Kovačević-Vujčić, M. Čangalović, General variable neighborhood search for the continuous optimization, European Journal of Operations Research, 191 (3) (2008), 753-770.