Topologia Moleculara - Grafuri

Introducere in Topologia Moleculara

Teoria grafurilor aplicata in studiul structurilor moleculare se constituie ca ramura interdisciplinara numita Topologie Moleculara. Caracterizarea topologica a structurilor chimice permite ordonarea acestora dupa criterii de simetrie si similaritate.

Din studii comparate, asupra unui set de molecule, topologia moleculara descifreaza factorii structurali implicati in relatia structura-proprietate/activitate biologica. Partitionarea unor proprietati moleculare si recompunerea lor, prin modele aditive, cu ajutorul descriptorilor moleculari si a analizei statistice, ca si modelarea de noi structuri, cu proprietati dorite, reprezinta unul din obiectivele topologiei moleculare. Inainte de detalierea problemelor specifice toplogiei moleculare vor fi prezentate cateva definitii¹ de baza ale teoriei grafurilor.

Grafuri

Graf G = G(V, E), este o pereche a doua multimi V = V(G), unde V este o multime finita si nevida, iar E = E(G), reprezinta o relatie binara definita pe multimea V. Graful, obisnuit, este vizualizat reprezentand elementele multimii V prin puncte si unind fiecare pereche de puncte (v_i, v_j) sau, mai simplu i, j) cu o linie, e_i,j, daca si numai daca (i,j)IE(G). Daca perechea de varfuri i, j) este neordonata, graful G este neorientat; punctele se cheama varfuri iar liniile se numesc muchii. Numarul varfurilor in G se noteaza cu v si este egal cu |V| (cardinalitatea multimii V(G)) iar numarul muchiilor cu e, care egaleaza |E| (cardinalitatea multimii E). Graful G(v, e) are ordinul v si dimensiunea e. Daca doua laturi distincte sunt incidente intr-un punct, ele se numesc laturi adiacente. Daca perechea de varfuri i, j) este ordonata, graful G se cheama orientat; elementele multimii E se cheama linii directe sau arce.¹ Termenul de graf a fost introdus de Sylvester. Exista numeroase tipuri de grafuri, unele dintre ele fiind mentionate mai jos.

Intr-un multigraf doua puncte pot fi unite prin mai mult de o linie. Figura 1.1 arata cele trei tipuri de grafuri mentionate mai inainte.

O cale P (path) este un lant catena) neramnificat(a). Un arbore T (tree), este o structura ramnificata. O stea (star) este un set de varfuri unite cu un varf comun si se noteaza S_v' , cu v' = v-1. Un ciclu C este un lant care pleaca si revine in unul si acelasi varf. (Figura 1.2).

Un graf complet, K_v, este un graf cu oricare doua varfuri adiacente. Numarul laturilor intr-un graf complet este v(v-1)/2. In Figura 1.3, sunt prezentate grafuri complete de la v=1 pana la 5.

Un graf bipartit este graful al carui set de varfuri V poate fi impartit in doua subseturi: V₁ V₂ =V; V₁ V₂ = astfel incat orice latura (i,j) I E(G) uneste V₁ cu V₂. Un graf este bipartit daca si numai daca toate ciclurile sale sunt pare.⁴ Daca oricare varf iIV₁ este adiacent cu fiecare varf jIV₂, atunci G este un graf bipartit complet si este simbolizat K_m,n, cu m = |V₁| si n = |V₂|. O stea este un graf bipartit complet K_1,n. Este evident ca K_m,n are m n laturi. Figura 1.4 prezinta cateva grafuri bipartite.

Un graf marcat, este garful in care heteroatomul sau atomul de carbon cu un electron neamperechiat este matcat.^5,6(Figura 1.5)

Un graf homeomorf este graful obtinut prin inserarea unor varfuri de valenta 2 pe muchiile unui graf G. (Figura 1.6)

Un graf planar este graful care poate fi desenat in plan, astfel incat oricare doua laturi se intersecteaza cel mult in punctele lor terminale. Regiunile definite de un graf planar se numesc fete, f, regiunea nemarginita fiind fata exterioara¹(e.g., f₄ in Figura 1.7). Pentru orice poliedru sferic cu |V| varfuri, |E| laturi si |F| fete este valabila formula lui Euler: Un graf este planar daca si numai daca nu are subgrafuri homeomorfe cu K₅ sau K_3,3 (teorema lui Kuratowski).⁹

Un graf-linie L(G) al grafului G se construieste punand cate un punct pe liniile lui G si unind doua astfel de puncte daca liniile corespunzatoare in G sunt incidente intr-un punct comun. Figura 1.8 ilustreaza aceasta derivata a grafului.

Un graf complementar al unui graf G (V, E) este graful (V, ), avand acelasi set de varfuri unite prin legaturi daca si numai daca ele nu exista in G. Valenta fiecarui varf in este egala cu diferenta dintre valenta varfului in graful complet K_v si varful corespunzator in G⁷ (Figura 1.9).

Un graf G se cheama indexat (labeled), G(Lb), cand punctele sale sunt indicate diferit de acelea ale grafului abstract corespunzator.¹⁰ Exista v! posibilitati de numerotare a unui graf de ordin v, G(Lb_i); i = 1,2,v!

Doua grafuri G=(V, E) si H=(V₁, E₁) sunt izomorfe, G H, daca exista o functie f : V V₁ care sa respecte conditiile:

f este bijectiva

(2) pentru oricare doua varfuri i, jIV; (i,j)IE (f(i), f(j))IE₁

Functia f se numeste izomorfism. In grupul izomorfismelor, exista cel putin o numerotare H(Lb), care pastreaza adiacenta din G: H(Lb) = G(Lb)

Un subgraf al unui graf G= (V, E) este un graf H = (V₁, E₁), unde V₁ V si E₁ E reprezinta toate muchiile care au ambele extremitati in V₁. Altfel spus, un subgraf H al lui G se obtine din G eliminand anumite varfuri si pastrand doar acele muchii care au ambele extremitati in multimea varfurilor ramase. (Figura 1.11).

Un arbore de deschidere (spanning tree) este un subgraf conex G₁ = (V, E₁) continand toate varfurile lui G dar E₁ E (Figura 1.12.).

Un graf G este conex daca intre oricare doua varfuri ale sale exista o cale.¹¹ (Figura 1.13).

1.2. Drumuri

Drum (walk) w: este o secventa alternanta de varfuri si muchii, w(1,n) = (v₁, e₁, v₂, e₂, , v_n-1, e_m, v_n), v_i I V(G ), e_i I E(G ), m n - 1, parcursa astfel incat oricare doua muchii succesive sunt adiacente: (v_i-1, v_i) I E(G) Este permisa revizitarea varfurilor si a muchiilor. Daca V(w(1,n)) = este sirul varfurilor drumului w(1,n) iar E(w(1,n)) = este sirul muchiilor sale, atunci l(w(1,n))= E(w_1,n) V(w_1,n) reprezinta lungimea drumului, care este egala cu numarul muchiilor traversate. Daca nici o alta conditie nu este impusa, drumul se numeste drum aleator. Conditii aditionale specifica un anumit tip de drum:^13-16

Drum inchis (Self-returning walk, srw) este drumul care porneste si sfarseste in acelasi varf, v_n=v₁ ; altfel drumul este deschis.

Cale (Self-avoiding walk, path p): este drumul care are toate varfurile si muchile distincte: v_i v_j, (v_i-1, v_i) (v_j-1, v_j), pentru oricare 1 i < j n. Altfel spus, calea viziteaza varfurile si muchiile o singura data si nu se admite nici o ramificare. Lungimea caii este l(p(1,n))= E(p(1,n)) V(p(1,n))

Drum Eulerian (trail): este drumul ale carui muchii e₁,e₂, , e_n sunt distincte, in timp ce varfurile pot fi revizitate.

Ciclu (circuit): este calea ale carei puncte de plecare si intoarcere coincid.

Cale Hamiltoniana: este calea deschisa ce viziteaza o data toate varfurile din graf.

Circuit Hamilton: este o cale Hamiltoniana inchisa (Figura 1.14).

Distanta topologica d(i,j): este lungimea caii celei mai scurte (daca exista) care uneste varfurile i si j: , altfel d(i,j)= Distanta dintre doua varfuri adiacente este egala cu unitatea. Cea mai scurta cale este numita si geodezica.

Excentricitatea unui varf i, ecc(i), intr-un graf conex este distanta maxima dintre i si oricare varf j al grafului: ecc(i) = max d(i,j).

raza unui graf, r(G), este excentricitatea minima in G: r(G) = min ecc(i) = min max d(i,j). diametrul unui graph, d(G), este excentricitatea maxima in G: d(G) = max ecc(i) = max max d(i,j). Multimea tuturor distantelor (geodezicelor) in G se noteaza cu D(G).

detur d(i,j), reprezinta calea cea mai lunga (daca exista) ce uneste varfurile i si j: , altfel d(i,j)= Setul tuturor detururilor in G se noteaza cu D(G).

Intr-un graf conex, distanta si deturul reprezinta metrici, adica, pentru oricare varfuri i, j, k:

m(i,j) 0; m(i,j)= 0 daca i= j

m(i,j) = m(j,i)

m(i,j) m(i,k) m(j,k)

Distanta metrica: este distanta, masurata in metri sau submultipli ai acestuia (nm, Angstroms), dintre doua varfuri i si j. Tabelul 1.1 illustreaza aceste notiuni.

Tabelul 1.1. Distante topologice si metrice

Valenta sau gradul varfului i, va_i: este numarul muchiilor incidente in varful i.¹ Daca toate varfurile au acelasi grad, graful se numeste regulat; altfel se numeste neregulat (Figura 1.15).

Invariant: este o proprietate a grafului theoretic, care se pastreaza prin izomorfism.^14-16 Cu alte cuvinte, valoarea numerica a proprietatii ramane neschimbata indiferent de numerotarea sau reprezentarea pictoriala a grafului.

1.3. Grafuri Moleculare

Un graf molecular este un model al unui system chimic, utilizat pentru caracterizarea interactiunii componentelor sale: atomi, legaturi, grupuri de atomi sau molecule. Formula structurala a unei substante chimice poate fi reprezentata ca graf molecular, varfurile lui fiind atomii, iar laturile corespunzand legaturilor covalente. In mod obisnuit, atomii de hydrogen se neglijeaza (Figura 1.16) si de asemenea unghiurile dintre legaturi. Atomii grei altii decat carbonul (heteroatomii) pot fi reprezentati ca in Figura 1.5. Similar, transformarea unei molecule (o reactie chimica) poate fi vizualizata printr-un graf de reactie, ale carui varfuri sunt specii chimice iar laturile cai de reactie.

Referinte

1. Harary , F. Graph Theory, Addison ‑ Wesley, Reading, M.A., 1969.

2. Sylvester, J. J. On an application of the new atomic theory to the graphical

representation of the invariants and covariants of binary quantics - with three

appendices, Am. J. Math. 1874, 1, 64-90.

3. Trinajstić, N. Chemical Graph Theory , CRC Press, Inc., Boca Raton, Florida, 1983.

4. Kőnig, D. Theorie der endlichen und unendlichen Graphen. Leipzig

Reprinted Chelsea, New York, 1950.

5. Kier, L. B.; Hall, L.H. Molecular Connectivity in Chemistry and Drug Research,

Acad. Press, 1976.

6. Balaban, A. T.; Filip, P. Computer program for topological index J (average distance

sum connectivity), MATCH, Commun. Math. Comput. Chem.

7. Ionescu, T. Grafuri‑Aplicatii, Ed. Ped. Bucharest

8. Euler, L. Elementa doctrinae solidorum et demonstratio nonnularum insignium proprietatum quibus solida heddris planis inclusa sunt praedita, Novi Comment. Acad. Sci. I. Petropolitanae,

Kuratowski, K. Sur le problème des courbes gauches en topologie, Fund. Math

1930, 15, 271-283.

Klin, M.H.; Zefirov, N.S. Group theoretical approach to the investigation of

reaction graphs for highly degenerate rearrangements of chemical compounds. II. Fundamental

concepts. MATCH Commun. Math. Comput. Chem., 1991, 26, 171-190.

Oprescu, D.; Bejan, L.; Patrascu, V. Informatica, Ed. Niculescu, Bucuresti, 2001

Cayley E. , Phil. Mag., 67 (1874) 444.

Berge, C. Teoria Grafurilor si Aplicatiile Ei, Ed. Tehnica , Bucuresti , 1969.

Kier, L. B. ; Hall, L. H. Molecular connectivity in chemistry and drug research, Acad.

Press, 1976.

Diudea, M. V.; Gutman, I.; Jäntschi, L. Molecular Topology, Nova, New York, 2002.

Diudea, M. V.; Florescu, M. S.; Khadikar, P. V. Molecular Topology and Its Applications, Eficon, Bucharest, 2006.