Stranica projekta Analizator trnovitih grafova

(zadnji update: 22. 08. 2005)

Puni naziv projekta

Analizator trnovitih ciklusa - ispitivač topoloških indeksa, valencija i valentnih povezanosti

vrh stranice

Ciljevi projekta

1. Razviti efikasne algoritme koji će davati odgovor na pitanje postoji li monociklički graf (propisanih tipova trnova) kojemu je zadana jedna od slijedećih osobina

a) valentne povezanosti

b) Randićev indeks i broj vrhova

c) Zagrebački indeks i broj vrhova

d) Modificirani zagrebački indeks i broj vrhova;

2. Razviti efikasne algoritme koji će efikasno davati odgovor na pitanje postoji li monociklički graf (propisanih tipova trnova) kojemu je zadana bilo koja kombinacija slijedećih osobina:

a) broj vrhova propisane valencije

b) Zagrebački indeks (verzija za vrhove)

c) Modificirani zagrebački indeks (verzija za vrhove)

d) Randičev indeks (verzija za vrhove)

Tipovi trnova koji se promatraju su:

a) metil

b) etil

c) propil

d) isopropil

e) butil

f) 1-metil-propil

g) 2-metil-propil

h) 1,1-dimetil-etil

3) Publicirati postignute znanstvene rezultate u 2-4 znanstvena rada

4) Na osnovi razvijenih algoritama napraviti u Visual Basic-u software koji će odgovarati na korisnikove upite u realnom vremenu (očekivano vrijeme odgovora za grafove do stotinjak vrhova bi bilo manje od minute)

vrh stranice

Kratki opis projekta

Povezanost između kemije i teorije grafova je vrlo snažna, naime molekule se prikazuju kao grafovi, pri čemu se atomi prikazuju kao vrhovi, a kemijske veze kao bridovi. Zbog toga je primjena metoda teorije grafova u kemiji jako važna. Često se pitamo postoji li molekula sa određenim svojstvima. To pitanje ponekad možemo preformulirati (zahvaljujući teoriji molekularnih deskriptora) u pitanje postoji li graf molekule sa traženim svojstvima. Nažalost traženje grafa sa propisanim svojstvima nije nimalo lako, jer broj grafova raste izuzetno brzo s obzirom na porast broja vrhova (eksponencijalno sa kvadratnim eksponentom).

Iz teorije algoritama je poznato da su nepolinomijalni algoritmi (uglavnom) neuporabljivi. Zbog toga je takve algoritme poželjno zamijeniti polinomijalnim algoritmima. Izrada polinomijalnih algoritama se često zasniva na složenim matematičkim kalkulacijama, a u ovom slučaju će za razvoj algoritama biti potrebno razviti izvorne znanstvene (matematičke) rezultate.

Na osnovu razvijenih teorema trebat će biti razvijeni algoritmi koji će ispunjavati zadaće opisane u rubrici ciljevi projekta.

vrh stranice

Autori projekta

Damir Vukicevic, Fakultet prirodoslovno-matematickih znanosti i odgojnih podrucja, Sveuciliste u Splitu, Split, Hrvatska, voditelj projekta

Nenad Trinajstic, Institut Rugjer Boskovic, Zagreb, Hrvatska

Darko Veljan, Prirodoslovno-matematicki fakultet, Sveuciliste u Zagrebu, Zagreb, Hrvatska

Damir Kalpic, Fakultet elektrotehnike i racunarstva, Sveuciliste u Zagrebu, Zagreb, Hrvatska

vrh stranice

Fileovi za download

Zip-file programa Analizator trnovitih ciklusa se može downloadati ovdje.

Uputstva za rad s programom Analizator trnovitih ciklusa se može downloadati ovdje.

Tehnicki detalji clanka Thorny graphs I. Valence connectivities, MATCH,  u pdf-u se mogu downloadati ovdje.

vrh stranice