TEORIA GRAFURILOR

TEORIA GRAFURILOR. CONSIDERATII GENERALE

Introducere

Primele notiuni in teoria grafurilor ca parte integranta a matematicii au fost definite in anul 1736 de catre Euler in manuscrisul sau "The Seven Bridges of Königsberg". O atentie deosebita a fost acordata teoriei grafurilor de catre A. Cayley [8] in anul 1895, iar Kirchhoff a dezvoltat în aceeasi perioada primele aplicatii la studiul circuitelor electronice. Studiul teoriei grafurilor a fost stimulat de aparitia in 1936 a tratatului lui D. König [9]. Daca la inceput teoria grafurilor era utilizata la obtinerea unor solutii pentru jocuri si amuzamente matematice, astazi este aplicata in economie, in chimie, sociologie, psihologie si inginerie. La utilizarea teoriei grafurilor in diverse domenii si-au adus contributia si autorii romani, una din primele carti din acest domeniu apartinand matematicianului I. Tomescu [10].

1.2. Grafuri si subgrafuri

Graful este o pereche G = (V, E) ce satisface relatia E [V]² [10-12]. Elementele multimii V sunt varfuri (noduri sau puncte) ale grafului G iar elementele lui E sunt muchiile (liniile). Fiecare varf este indicat printr-un punct si fiecare muchie printr-o linie. Setul de varfuri al grafului G se refera la V(G) iar setul de muchii la E(G). Numarul de varfuri al grafului G, notat |G|, reprezinta ordinul acestuia iar numarul de muchii este notat prin ||G||. In Figura 1a si 1 b sunt prezentate doua tipuri de astfel de grafuri.

1a 1b

V = V =

1a E = ,,,,,,,,,}

1b E = ,,,,,,,,}

Figura 1. Grafuri si elementele constructive (varfuri-V, muchiile-E)

Grafurile pot fi finite sau infinite. Grafurile se numesc finite daca numarul varfurilor si muchiilor acestor grafuri este finit iar daca ordinul grafului este 0 sau 1 se numesc grafuri triviale. Un varf v este incident cu o muchie e daca v e. Doua grafuri A si B se numesc identice daca V(A) = V(B) si E(A) = E(B). Daca varfuri x si y ale unui graf G sunt adiacente atunci cele doua varfuri formeaza o muchie xy a lui G in timp ce doua muchii e≠ f sunt adiacente daca au un capat comun [10-12].

Daca pentru doua grafuri G = (V, E) si G^' = (V', E') exista o functie bijecta j:V V cu xy E j(x)j(y) E' pentru toate varfurile x, y V atunci grafurile se numesc izomorfe iar daca G = G' atunci se numesc grafuri automorfe. In Figura 2 sunt prezentate grafurile G si G^' izomorfe.

G G^'

Figura 2. Grafurile G si G^' cu proprietatea de izomorfism

Daca intr-un graf fiecare pereche de varfuri distincte este unita printr-o muchie se numeste graf complet in timp ce un graf partial al grafului G = (V, E) este graful G₁ = (V, E₁) unde E₁ E, deci graful partial se obtine prin suprimarea anumitor legaturi dintre varfurile lui G [10-12]. Figura 3 prezinta graful complet 3a si graful partial 3b corespunzator grafului complet 3a.

3a 3b

Figura 3. Graful complet 3a si graful partial 3b corespunzator grafului complet 3a

Daca multimea varfurilor unui graf G poate fi partitionata in doua multimi disjuncte de varfuri, V(G) = V₁U V₂, astfel incat fiecare muchie uneste un varf din V₁ cu un varf din V₂, graful G se numeste bipartit.

Un subgraf al unui graf G = (V, E) se defineste in mod asemanator cu notiunea de submultime: el este un graf G₁ = (V₁, E₁) unde V₁ V iar E₁ reprezinta toate legaturile dintre varfurile V₁ care existau in graful G.

Un graf G (4a) si unul din subgrafurile posibile 4b pentru graful G sunt prezentate in Figura 4.

4a 4b

Figura 4. Graful G (4a) si unul din subgrafurile posibile 4b

Grafuri conexe

Un graf G se numeste conex daca are proprietatea ca oricare doua varfuri ale sale sunt legate printr-un drum (succesiune de varfuri conectate dintre oricare doua varfuri luate in considerare) din G. Notiunea de conexitate isi are aplicabilitate practica in diferite domenii cum ar fi telecomunicatiile, transporturi etc.

Se numeste graf neorientat, o pereche ordonata de multimi notata G = (X, U), unde X = este o multime finita si nevida de elemente numite varfuri, iar U = este o multime de perechi neordonate de elemente din X numite muchii.

Un graf G se numeste conex daca pentru orice pereche de varfuri distincte x, y ale lui G, exista un lant de extremitati x si y in G.

Un graf G se numeste graf fara circuite daca nodul initial cu care se incepe in parcurgerea grafului nu coincide cu cel final.

O proprietate speciala a grafurilor este acea ca grafurile in anumite conditii pot fi arbori.

Un arbore este un graf neorientat, conex si fara circuite. Pentru orice arbore este valabila relatia :

E = V - 1 (1)

unde E este numarul de muchii iar V este numarul de varfuri.

In Figura 5 este prezentat un astfel de tip de arbore.

Figura 5. Arbore neorientat si conex

Aplicatii ale teoriei grafurilor in chimie

Grafurile constitutionale reprezinta unul din tipurile de grafuri care prezinta interes pentru chimie. Formulele constitutionale au fost utilizate pentru prezicerea numarului izomerilor constitutionali din vremea cand teoria structurii chimice a fost creeata de Kekulé, Couper, Crum-Brown si Butlerov in 1850-1870. Fundalul matematic al teoriei grafurilor a fost formulat in acelasi timp de catre Cayley care propune un algoritm pentru calcularea numarului de izomeri constitutionali pentru alcani, C_nH_2n+2 si alchil derivati (ex. C_nH_2n+1Cl) [8, 13]. Astfel (chimia si in particular chimia organica) poate fi considerata prima sursa independenta din cele trei existente pentru inceputul teoriei grafurilor, celelalte doua surse fiind teoria retelelor electrice a lui Kirchhoff si topologia dupa Euler [14].

1.4.1. Izomerie constitutionala si sterica

Formulele stereochimice introduse in chimia organica de catre Van't Hoff [15] si Le Bel [16] si in chimia anorganica de catre Werner [17] sunt de fapt grafuri topologice in timp ce o formula de schelet reprezinta un subgraf, iar formula unui heterociclu sau carbociclu - un graf ciclic. Izomerii de catena se diferentiaza unii fata de altii prin formule care reflecta de fapt, conectivitatile lor diferite [14,18-23]. Algoritmul matematic propus de Cayley pentru calcularea numarului de izomeri constitutionali pentru alcani, C_nH_2n+2 si alchil derivati [8, 13] a fost ulterior imbunatatit de catre Henze si Blair [24] iar Polya a gasit o cale matematica eleganta pentru rezolvarea problemelor stereoizomerismului[25] solutie cunoscuta sub numele de teorema lui Polya.

Teoria grafurilor demonstreaza ca: i) exista doi heptani chirali 6a si 6b in care atomii de carbon chirotropici / stereogenici sunt prezentati cu un atom de hidrogen; ii) alcanul 6c izomer al octanului este meso [22, 26].

6a 6b 6c

6a 6b 6c

Figura 6. Reprezentarea grafurilor constitutionale pentru heptanii izomeri 6a si 6b si a meso-alcanul 6c isomer al octanului

1.4.2 Izomerie de valenta

Izomerii de valenta reprezinta o subclasa a izomerilor constitutionali care pot fi definiti utilizand conceptele teoriei grafurilor astfel: daca doua grafuri fara hidrogen au aceeasi partitie a gradelor varfurilor atunci acestea corespund la doi izomeri de valenta [22, 27]. Cel mai interesant caz de izomerie de valenta il prezinta anulenele (CH)_n care sunt grafuri de gradul 3 cand sunt reprezentate fara hidrogeni. Pentru n = 6 (CH)₆ sunt posibile sase grafuri cubice care sunt prezentate in Figura 7 [22] dar si 211 grafuri care sunt izomeri cu C₆H₆ (benzen) dar nu si izomeri de valenta cu benzenul [28].

7a 7b 7c

7d 7e 7f

7a 7b 7c 7d 7e 7f

Figura 7. Grafurile constitutionale pentru anulenele (CH)₆

Chimia anulenelor, impulsionata de predictiile teoriei grafurilor a preocupat si preocupa multi chimisti [29, 30] un loc aparte ocupandu-l Profesorul Nenitzescu care impreuna cu echipa sa [31] sintetizeaza primul isomer de valenta pentru anulena (CH)₁₀ (Figura 8) care va fi numita mai tarziu de Doering [32] hidrocarbura Nenitzescu.

Figura 8. Hidrocarbura Nenitzescu si graful caracteristic

Conceptele teoriei grafurilor au fost utilizate si pentru dezvoltarea unor programe pentru calculator capabile sa genereze izomerii pentru o formula moleculara data. Programul dezvoltat de Lederberg si colaboratorii [33] numit DENDRAL alaturi de date RMN si de spectrometrie de masa poate genera izomeri pentru orice substanta cu masa moleculara mai mica de 1000.

1.4.3. Hidrocarburi aromatice policiclice

Hidrocarburile aromatice policiclice, cei mai cunoscuti compusi carcinogeni, sunt clasificati [21, 22] in doua mari clase : i) cata-condensate care nu au puncte comune la trei inele benzenice; ii) peri-condensate care au puncte comune la trei nuclee benzenice. In Figura 9 sunt prezentate grafurile pentru trei hidrocarburi cata-condensate (naftalina 9a, fenantrenul 9b si antracenul 9c) si pentru doua hidrocarburi peri-condensate(pirenul 9d si perilenul 9e).

9a 9b 9c 9d 9e

Figura 9. Grafurile constitutionale pentru cele mai cunoscute hidrocarburi aromatice cata- si peri-condensate

Acestor hidrocarburi aromatice din perspectiva teoriei grafurilor li se asociaza un al doilea tip de graf denumit graf dual [21, 22]. Aceste grafuri au ca varfuri centrele inelelor benzenice iar varfurile sunt conectate daca inelele benzenice sunt condensate. Sistemele cata-condensate au grafuri duale aciclice cat si ciclice dar nu pot avea trei inele ca membri iar cele peri-condensate au grafuri duale cu trei inele ca membri.

Pentru hidrocarburile aromatice benzenoide cata-anelarea se poate realiza pe diverse laturi ale inelului aromatic, pentru descrierea corecta a structurii propunandu-se o codare specifica[34]. In acest sistem de codare se utilizeaza cifra 0 pentru anelarea liniara si 1 sau 2 pentru simbolizarea directiilor alternative (Figura 9, naftalina 9a). Ulterior au fost dezvoltate o serie de programe pentru studiului fenomenului de cata-anelare in cazul hidrocarburilor aromatice benzenoide [35].

Pentru codarea sistemelor peri-condensate au fost propuse doua alternative [22, 36]. In prima alternativa se specifica prezenta inelelor benzenice (varfuri ale grafului dual) in zone concentrice in jurul unui centru topologic al sistemului hexagonal, acest centru nefiind specificat in notatie. Prima zona concentrica are numerele 1-6 in care 1 leaga partea de la suprafata stanga de centru printr-o linie orizontala iar a doua zona concentrica are numerele 1-12. Acest sistem este orientat astfel incat sa se minimizeze numerele in prima zona concentrica dupa anumite reguli bine precizate. Aceasta situatie in care sunt specificate inelele benzenice este prezentata in Figura 10.

Figura 10. Prima alternativa de codare a sistemelor peri-condensate

In a doua situatie se suprapune sistemul hexagonal peste o grila (Figura 11, 11a) astfel incat se minimiza suprafata paralelogramului circumscris si numarul de randuri pe care este suprapus sistemul. Prezenta unui varf al grafului dual este notata cu 1 iar absenta cu 0. Aceasta a doua forma de codare este prezentata pentru fenantren si crisen in Figura 11.

11a-Suprafata ,,grid'' 11b-[1,3]triacene 11c-[3,6]tetracene

Figura 11. A doua alternativa de codare a hidrocarburilor benzenoide

1.4.4. Concatenarea 3D-Protohelixurilor in poliedre regulate

Definitia 1. Protohelixurile sunt cele mai simple tipuri de structuri care prin procedee obisnuite conduc la structuri mai complicate.

Definitia 2: Un obiect n-dimensional care nu se suprapune prin nici rotatie in spatial n-dimensional peste imaginea sa in oglinda se numeste chiral [37].

Definitie3: Concatenarea reprezinta fenomenul de asociere a doua sau mai multe protohelixuri astfel incat doua varfuri se contopesc intr-unul [37].

Prin concatenarea unor protohelixuri se pot obtine poliedre achirale. Un astfel de exemplu in constituie cele 13 poliedre Arhimedice semiregulate din care doua sunt chirale. Un alt exemplu binecunoscut il reprezinta Buckminsterfulerena care este tot un poliedru Arhimedic semiregulat achiral [37].

Un exemplu spectaculos il reprezinta un cub format din doua semicuburi astfel incat ansamblul celor patru protohelixuri poate avea aceasi chiralitate sau exista doua perechi de antipozi (Figura 12, 12a, 12b). Prin intoarcerea unor astfel de protohelixuri se formeaza doua cuburi (Figura 12, 12c, 12d).

12a 12b 12c 12d

Figura 12. Formarea cubului din protohelixuri cu aceasi chiralitate sau chiralitate in opozitie (diagrama Schlegel)

Un alt exemplu interesant de poliedru chiral este reprezentat de izomerii cu pentagoane izolate ai fulerenelor. Fulerena C₆₀ numita si buckminsterfulerena prezinta 1812 izomeri constitutionali dar numai unul prezinta pentagoane isolate; la fel, pentru fulerena C₇₀ exista un singur izomer cu pentagoane izolate.

1.4.5. Grafuri de reactie

O alta clasa de grafuri cu aplicatii in chimie [21, 22] care asociaza varfurilor dintr-un graf ansambluri de atomi si muchiilor tranzitii elementare intre doua astfel de ansambluri se numesc grafurilor de reactie. Primul graf de reactie descrie [38] izomerizarea intramoleculara a unui cation etil cu doi atomi de carbon ce se pot distinge de exemplu prin marcarea izotopica (Figura 13) si pentasubstituit cu cinci grupe diferite.

Figura 13. Cationul etil pentasubstituit utilizat in primul graf reactie publicat

Acest tip de graf reactie este utilizat pentru descrierea izomerizarile intramoleculare ale complecsilor pentacoordinati cu structura de bipiramida trigonala cum sunt fosforanii [39] sau complecsi organometalici [40].

Izomerizarea intramoleculara a structurilor bipiramida trigonala include mai multe moduri de rearanjare [41] fiecare decurgand prin mecanisme diferite, cele mai plauzibile fiind insa pseudorotatiile Berry [42]. Graful de reactie prezinta o anumita simetrie globala [21] care sugereaza o anumita codificare a celor 20 de varfuri ale grafului prin utilizarea a maxim cinci simboluri care sunt apropiate de notatia propusa de Ugi [43]. Conceptele teoriei grafurilor au fost utilizate in domeniul chimiei organometalice de catre Gielen, Brocas si Willem pentru rationalizarea datelor lor experimentale.[44]

1.4.6. Grafuri Sinton

Notiunea de graf sinton a fost utilizata pentru prima data de catre Hendrickson [45]. Grafurile sinton au varfurile simbolizand sintonurile si muchiile simbolizand setul de legaturi prezente intre sintonuri [21, 22, 46]. Un astfel de exemplu este prezentat in Figura 14 unde scheletul steroidic este format din patru sintonuri . Setul de legaturi este notat prin linii intrerupte iar sintonul prin linii continue.

Figura 14. Scheletul steroidic si grafurile sinton din care e format

Grafurile sinton au fost utilizate intr-o serie de programe sofisticate de calculator [46, 47] dedicate generarii de cai de retrosinteza. Uneori utilizarea acestor programe a permis obtinerea de rezultate exceptionale cum ar fii explicarea modului in care are loc reactia Gattermann-Kock: la compusii aromatici via cation formil in timp ce in seria alchenelor are loc via ion alchilcarbeniu si monoxid de carbon.

1.4.7. Teoria grafurilor in modelarile topologice

Un alt domeniu important de aplicatii ale teoriei grafurilor este acela al obtinerii relatiilor cantitative structura-activitate QSAR (Quantitative Structure - Activity Relationshis) sau structura proprietati QSPR (Quantitative Structure - Property Relationships) prin intermediul indicilor topologici asociati structurilor chimice.

Aceste modele topologice reprezinta tentative de asociere a unor marimi cantitativa structurii moleculare, marimi care sa caracterizeze topologia legaturilor chimice si stereochimia grafurilor moleculare constitutionale sau structurale[5-7, 14, 22, 23]

Conform teoriei grafurilor in molecula organica sunt codate doua nivele globale de informatie structurala :

1. Structura completa, atat electronica cat si geometrica, obtinuta prin calcule cuanto-mecanice.
2. Informatia structurala moleculara bazata pe notiunea de legatura chimica, care se refera la conexiunile dintre atomi si modul de ramificare cunoscuta si sub numele de topologie moleculara.

Topologia ca si teoria grafurilor este o ramura a matematicii care implica concepte complexe si care in chimie se ocupa cu studiul unor proprietati metrice ale moleculelor precum lungimile de legatura, unghiurile de valenta, suprafetele si volumele dar si proprietati homeomorfe care sunt independente de marimea si forma spatiala a moleculelor.

Notiunea de ,,topologie moleculara'' nu este in intregime adecvata deoarece structurile chimice sunt discrete si de aceea e mai indicat ca molecula sa fie considerata in termenii teoriei grafurilor [14].

Kier si Hall au propus termenul de ,, conectivitate moleculara''[48] pentru a distinge intre diferitele modele cantitative ale topologiei moleculare. Conectivitatea moleculara este necesara pentru o caracterizare numerica formala a informatiei structurale in scopul corelarii structurii chimice cu proprietatile moleculelor (proprietati fizice, activitati biologice, toxicitate ). Scopul final al acestor metode este acela de a furniza o serie de descriptori numerici care sa codifice numeric informatie suficienta referitoare la numarul de atomi si vecinatatile acestora(topologia moleculelor). Acesti descriptori poarta numele de indici topologici [14].

Acestia trebuie sa fie unici pentru o structura data dar metoda prin care sunt fost calculati urmeaza algoritmi variati si uneori complecsi.

Asa cum s-a amintit in subcapitolul 1.4 cele mai importante grafuri utilizate in chimie sunt asa numitele grafuri moleculare sau constitutionale in care formulele de constitutie sunt reprezentate prin puncte (atomi) unite prin linii (legaturi). Se deduce usor ca aceste grafuri chimice sunt de fapt un mijloc de reprezentare a topologiei moleculare. In Figura 15 sunt prezentate cateva exemple de grafuri chimice.

(a)

(b)

(c)

Figura 15. Exemple de grafuri chimice : (a)- n-pentan ; (b)- etena ; (c)- toluen

Dupa cum este bine cunoscut graful chimic asociat unei formule de schelet cu atomii de hidrogen presupusi implicit in conformitate cu valenta atomului de carbon sau a altor heteroatomi, se numeste graf fara hidrogeni.

(a) (b)

(c)

Figura 16 Grafuri chimice pentru molecula 2,4-dimetil-hexan

b-formula structurala cu hidrogeni

c- formula structurala fara hidrogeni

Relatiile topologice fundamentale din teoria grafurilor isi gasesc aplicatii directe in chimia organica.

O teorema fundamentala a teoriei grafurilor este urmatoarea [18] : Daca un graf G contine v varfuri, v₁, v₂ ,..,v_n fiecare avand valenta (gradul) d d d_n si e muchii e₁, e₂,.,e_n atunci intre acestea exista urmatoarea relatie :

Din ec. (2) se observa ca suma valentelor varfurilor este un numar par. Aceasta relatie este foarte cunoscuta in chimia organica pentru a stabili daca un compus exista sau nu in stare fundamentala.

Exemplu : C₇H₁₁O₂ Sd_i 2=43 (numar impar)- compusul nu exista in stare fundamentala dar poate exista sub forma de radical sau ion.

Pentru grafurile care descriu sisteme spatiale este valabila relatia lui Euler : m=n+c-2 

unde : m este numarul de muchii, v reprezinta numarul de varfuri iar c reprezinta numarul de cicluri ale figurii spatiale.