MagistrskodeloMentor:prof.dr.SandiKlavžarLjubljana,2021 M-POLINOM UNIVERZAVLJUBLJANIFAKULTETAZAMATEMATIKOINFIZIKOMatematika–2.stopnjaSaraBrezec

UNIVERZA V LJUBLJANI

FAKULTETA ZA MATEMATIKO IN FIZIKO Matematika – 2. stopnja

Sara Brezec

M-POLINOM

Magistrsko delo

Mentor: prof. dr. Sandi Klavžar

Ljubljana, 2021

Kazalo

Program dela ix

1 Uvod 1

2 M-polinomi 1

2.1 Topološki indeks . . . 1

2.1.1 Nekaj znanih topoloških indeksov . . . 2

2.1.2 Posplošitve in parametrizacija . . . 6

2.1.3 Kateri topološki indeksi so dobri v praksi? . . . 7

2.2 M-polinom . . . 8

2.2.1 Izračun M-polinoma . . . 9

2.2.2 Razširitev Gutmnovega pristopa za ravninske grafe . . . 10

2.3 Izračun BID indeksov s pomočjo M-polinoma . . . 12

2.4 Izračun M-polinoma za nekaj molekulskih struktur . . . 15

2.4.1 Zvezdasta drevesa . . . 15

2.4.2 Verige kaktusov . . . 17

2.4.3 Rombični in cikcak benzenoidni sistemi . . . 19

3 Spletna stran M-polinomov 25 3.1 Struktura spletne strani M-polinomov . . . 25

3.1.1 Zavihek Search . . . 25

3.1.2 Zavihek Contribute . . . 26

3.1.3 Zavihek Instructions . . . 31

3.2 Izdelava spletne strani M-polinomov . . . 32

3.2.1 Django in Elasticsearch . . . 32

3.2.2 Kreacija spletne strani . . . 33

4 Zaključek 61

Literatura 63

Kazalo slik

1 Poliominska veriga. . . 9

2 Primer grafa G(p, q). . . 11

3 Primer zvezdastega drevesa. . . 16

4 Primer ortoverižnega kaktusa. . . 18

5 Orto verigaQ(m, n). . . 19

6 Cikcak benzenoidni sistem. . . 20

7 Rombični benzenoidni sistem. . . 23

8 ZavihekSearch . . . 25

9 Podroben prikaz rezultata iskanja . . . 26

10 Osnovna stran sistema administracije . . . 27

11 Obrazec za dodajanje novih M-polinomov . . . 28

12 Tabela M-polinomov, ki jih lahko spreminjamo . . . 29

13 Obrazec za urejanje M-polinomov . . . 30

14 Tabela M-polinomov, ki jih lahko komentiramo . . . 31

15 Ustvarjanje novih uporabnikov . . . 32

Kazalo izvorne kode

1 Razred Mpolynom . . . 34

2 Funkcija unique_rand . . . 34

3 Druge funkcije datoteke models.py . . . 36

4 Funkcija rewrite_mpolynomial_see . . . 38

5 Funkcija fin_outer_parentheses_clousure . . . 39

6 Funkcija read_number . . . 40

7 Funkcija rewrite_mpolynomial . . . 43

8 Nastavitve za bazo . . . 43

9 Datoteka documents.py . . . 45

10 Oblika url povezav . . . 46

11 Enostavne funkcije datoteke views.py . . . 47

12 Funkcija index . . . 48

13 Funkcija mpoly_query . . . 49

14 Razred CommentAdmin . . . 52

15 Razred CommentAdminForm . . . 53

16 Razred MpolynomModelAdmin . . . 58

17 Razred MpolynomAdminForm . . . 60

18 Razred Comment . . . 61

Program dela

V prvem delu magistrskega dela predstavite M-polinom ter razložite njegovo upo- rabnost v matematični kemiji. Podajte tudi nekaj konkretnih primerov njegove uporabe. V drugem, aplikativnem delu magistrskega dela, pa izdelajte aplikacijo - spletna stran baze M-polinomov - ki bo omogočala kreiranje obsežne baze M- polinomov kemijsko zanimivih družin grafov.

Osnovna literatura

[6] E. Deutsch in S. Klavžar, M-polynomial and degree-based topological indices, Iranian Journal of Mathematical Chemistry 6 (2015) 93–102

[12] I. Gutman,Degree-based topological indices, Croatica Chemica Acta86(2013) 351–361

Podpis mentorja:

M-polinom Povzetek

V delu predstavimo M-polinom. To je polinom, s pomočjo katerega enostavno dolo- čimo mnoge topološke indekse stopenj vozlišč. Najprej spoznamo topološke indekse, nato definiramo M-polinom in si ogledamo postopek izračuna le-tega ter nekate- rih topoloških indeksov stopenj vozlišč. Prvi del zaključimo z dodatnimi primeri izračunov.

Drugi del magistrske naloge predstavi spletno stran M-polinomov. Stran omo- goča brskanje po bazi M-polinomov. Če smo vpisani uporabnik, pa lahko tudi ko- mentiramo in dodajamo nove M-polinome. V delu so opisani razdelki spletne strani.

Nato sledi nekaj besed o uporabljenih orodjih za izdelavo ter podrobna razlaga iz- delave strani.

M-polynomial Abstract

In this work, we present M-polynomial, the polynomial which simplifies the calcu- lation of many degree-based topological indices. First, we introduce the topological indices, then we define the M-polynomial and familiarise ourselves with the proce- dure of its calculation and the calculation of the degree-based topological indices.

We conclude the first part with additional calculation examples.

In the second part, the M-polynomials website is presented. The site empowers search through the M-polynomials database. Logged users can also comment and contribute new M-polynomials. The work describes the website sections. This is followed by a few words about the tools used to develop the website and a detailed explanation of how the site is built.

Math. Subj. Class. (2020): 05C09, 05C31, 05C92

Ključne besede: topološki indeks stopenj vozlišč, M-polinom, polinom grafa, za- grebški indeks, Randićev indeks, spletna stran, Elasticsearch, Django

Keywords: degree-based topological index, M-polynomial, graph polynomial, Za- greb index, Randić index, website, Elasticsearch, Django

1 Uvod

M-polinom je koncept novejšega datuma, vpeljala sta ga Deutsch in Klavžar v [6]

leta 2015. Omogoča nam enostaven in hiter izračun večje podskupine topoloških in- deksov stopenj vozlišč, imenovane BID indeksi. Včasih je bilo potrebno za določeno družino grafov izračunati vsak topološki indeks posebej, sedaj pa lahko določimo M-polinom in nato iz njega s preprostimi funkcijami, kot sta odvajanje in integrira- nje, izračunamo različne topološke indekse stopenj vozlišč. Vlogo M-polinoma lahko primerjamo z vlogo Hosoyevega polinoma [5] za topološke indekse, ki so definirani kot funkcije razdalj med vozlišči grafa.

Topološki indeksi se pogosto uporabljajo v matematični kemiji za določitev raz- ličnih fizikalnih in kemijskih lastnosti molekul. Kemijsko molekulo upodobimo z grafom, za katerega potem izračunamo različne numerične invariante (topološke in- dekse). Te so tesno kolerirane z različnimi molekulskimi lastnostmi. Tako lahko brez eksperimentalnega dela pridobimo različne informacije o molekulah in s tem prihranimo čas in denar.

Spletna stran baze M-polinomov je namenjena iskanju različnih M-polinomov ter podatkov o njih. Iščemo lahko preko različnih vrednosti. V iskalno vrstico lahko vpi- šemo npr. M-polinom, ime kemijske strukture, avtorja vnosa, komentar, referenco, ključno besedo in podobno. Stran omogoča tudi dodajane novih M-polinomov ter urejanje in komentiranje obstoječih M-polinomov.

V magistrskem delu bomo najprej definirali različne vrste topoloških indeksov in si ogledali nekaj znanih primerov topoloških indeksov stopenj vozlišč ter njihovih lastnosti. Nadalje bomo na primeru Randićevega indeksa naredili postopka gene- ralizacije in parametrizacije. Ker je prisoten problem, da veliko vpeljanih indeksov ni primernih za praktično uporabo, bomo določili nekaj kriterijev uporabnosti. V poglavju 2.2 bomo definirali M-polinom in ga izračunali z uporabo Gutmanovih zvez. Poglavje 2.3 je namenjeno izpeljavi formul za izračun različnih BID inde- ksov iz M-polinoma. V poglavju 2.4 si bomo ogledali še nekaj primerov izračuna M-polinoma. V drugem delu magistrske naloge si bomo ogledali strukturo sple- tne strani M-polinomov. Nato se bomo poglobili v njeno izdelavo in delovanje. V poglavju 3.1 so opisani razdelki spletne strani M-polinomov; Search, Contribute in Instructions ter stran za administracijo. Poglavje 3.2 predstavi uporabljeni orodji za izdelavo spletne strani, Django in Elasticsearch, ter se poglobi v izvorno kodo le te.

2 M-polinomi

Prvi del magistrskega dela je teoretične narave. Spoznali se bomo z M-polinomi.

2.1 Topološki indeks

Preden definiramo topološki indeks, ponovimo nekaj osnovnih pojmov teorije grafov.

Naj bo G = (V, E) graf. Potem postavimo n(G) = |V(G)| in m(G) = |E(G)|.

Z d_v(G) oz. d_v označimo stopnjo vozlišča v ∈ V, z ∆(G) pa maksimalno stopnjo vozlišč grafa G.

Definicija 2.1. Kemijski graf je enostaven povezan graf, ki ponazarja atomsko strukturo organske molekule. Vozlišča predstavljajo atome, povezave grafa pa kemij- ske vezi. Zaradi kemijske zgradbe molekul je maksimalna stopnja vozlišč v kemijskih grafih največ štiri.

Topološki indeks je numerična vrednost, ki karakterizira topologijo grafa. Je invarianta grafa, torej je odvisna le od strukture grafa in se ne spreminja glede na reprezentacijo grafa.

Definicija 2.2. Topološki indeks je numerična invarianta, ki izraža korelacijo med kemijsko strukturo in določeno fizikalno lastnostjo, kemijsko reaktivnostjo ali biolo- ško aktivnostjo.

Topološke indekse, ki so definirani kot funkcije stopenj vozlišč, imenujemotopo- loški indeksi stopenj vozlišč. Pomembna podskupina teh indeksov so BID indeksi.

Definicija 2.3. Za dani grafG= (V, E)jeBID indeks (bond incident degree index) invarianta grafa oblike

I(G) = ∑

e=uv∈E

f(d_u, d_v),

kjer je f =f(x, y) primerno izbrana funkcija, uporabna v kemiji.

Primer BID indeksa je Randićev indeks

∑

uv∈E

√1 d_ud_v, Randićev indeks tretjega reda oblike

∑

vi1,vi2,vi3

1

√d_vi

1d_vi

2d_vi

3

,

kjer seštevanje poteka po vseh poteh dolžine tri, pa je topološki indeks stopenj vozlišč, ki ne spada med BID indekse.

V magistrskem delu se bomo osredotočili na BID indekse, vendar bomo običajno namesto BID indeks pisali kar topološki indeks. Izjema so poglavja, v katerih želimo posebej poudariti, da gre za BID indeks.

2.1.1 Nekaj znanih topoloških indeksov

V tem razdelku si bomo ogledali pomembnejše topološke indekse in predstavili nekaj krajših matematičnih rezultatov povezanih z njimi. Vsebina je povzeta po [12].

2.1.1.1 Randićev indeks oz. indeks povezanosti

Zgodovinsko gledano je prvi topološki indeks stopenj vozlišč definiral Milan Randić.

Imenuje se Randićev indeks ali indeks povezanosti in je največkrat preučevan in uporabljen indeks. Pred Randićevim indeksom so bili sicer že vpeljani zagrebški indeksi, vendar so bili ti vpeljani za drug namen in so se med topološkimi indeksi matematične kemije pojavili kasneje.

Definicija 2.4. Naj bo G= (V, E) graf. Randićev indeks ali indeks povezanosti je definiran kot

R(G) = ∑

uv∈E

√1 d_ud_v.

Eden od zanimivih rezultatov preučevanja Randićevega indeksa je enačba R(G) = n

2 −1 2

∑

1≤i<j≤n−1

( 1

√i− 1

√j )2

m_ij, (2.1)

kjer je m_ij število povezav s krajiščema stopnje i in j. Iz izraza (2.1) lahko takoj razberemo, da je n/2 največja vrednost Randićevega indeksa za grafe z n vozlišči in je dosežena na regularnih grafih. Izpeljimo sedaj rezultat (2.1). Najprej bomo dokazali uteženo obliko leme o rokovanju [18].

Trditev 2.5 (Utežena lema o rokovanju). Naj bo f poljubna kompleksna funkcija definirana na množici vozlišč grafa G= (V, E). Potem je

∑

uv∈E

(f(u) +f(v)) =∑

v∈V

d_vf(v).

Dokaz. Vsak izrazf(v)se na levi strani enačbe pojavid(v)-krat, kar je enako število pojavitev kot na desni strani.

Z f(v) = 1 za vsak v ∈V dobimo lemo o rokovanju, če pa definiramo f(v) = 1/d_v, dobimo naslednjo enakost

∑

uv∈E

( 1 d_u + 1

d_v )

=n. (2.2)

Enačbo Randićevega indeksa odštejemo od enačbe (2.2) in dobimo želeno enačbo n

2 −R(G) = 1 2

∑

uv∈E

( 1 d_v + 1

d_u − 2

√d_ud_v )

oziroma

R(G) = n 2 − 1

2

∑

1≤i<j≤n−1

( 1

√i − 1

√j )2

m_ij.

2.1.1.2 Zagrebški indeksi

Prvi in drugi zagrebški indeks sta bila vpeljana za analiziranje strukturne odvisnosti od skupne π-elektronske energije [13].

Definicija 2.6. Naj bo G= (V, E) graf. Prvi zagrebški indeks je enak M₁(G) =∑

v∈V

d²_v, drugi zagrebški indeks pa

M₂(G) = ∑

uv∈E

d_ud_v.

Indeksa sta primerna tudi za merjenje razvejanosti molekul [4].

2.1.1.3 ABC indeks

Definicija 2.7. Naj boG= (V, E)graf. Indeks povezanosti atomskih vezi, imenovan tudi ABC indeks, je topološki indeks oblike

ABC(G) = ∑

uv∈E

√d_u+d_v−2 d_ud_v .

Opazimo lahko podobnost z Randićevim indeksom. V imenovalcu ulomka ima ABC indeks produkt stopenj krajišč povezaveuv, enako kot Randićev indeks, števec pa je enak številu povezav, ki so sosednje povezavi uv.

ABC indeks dobro meri termodinamične lastnosti alkanov. To je tudi edini topo- loški indeks, za katerega obstaja teoretična razlaga za njegovo korelacijo s kemijskimi lastnostmi [10].

2.1.1.4 Povečani zagrebški indeks

Povečani zagrebški indeks je modificirana verzija ABC indeksa.

Definicija 2.8. Naj bo G= (V, E) graf z n≥3 vozlišči. Povečani zagrebški indeks je definiran kot

AZI(G) = ∑

uv∈E

( d_ud_v d_u+d_v−2

)3

.

Ko vpeljemo nov topološki indeks, običajno želimo določiti njegovo zgornjo in spodnjo mejo. V nadaljevanju si bomo ogledali zgornjo mejo za AZI [15].

Naj bo G kemijski graf z n ≥ 3 vozlišči in naj bo A_i,j = _i+j−2^ij , kjer sta i, j pozitivni celi števili. Če z m_ij označimo število povezav s krajiščema stopnje i inj, potem lahko povečani zagrebški indeks zapišemo kot

AZI(G) = ∑

1≤i≤j≤∆

i+j̸=2

m_ijA³_ij.

Trditev 2.9.

1. A_1j je padajoča za j ≥2.

2. A_2j = 2 za j ≥2.

3. Za izbrani j ≥3 vrednost A_ij narašča za i≥3.

Dokaz.

1. A_1j = ₁₋¹1 j

je padajoča zaj ≥2.

2. A_2j = _2+j−2^2j = 2 zaj ≥2.

3. Naj boj ≥3 fiksen, potemA_ij = ^j

1+^j−2_i narašča zai≥3.

Iz trditve 2.9 sledi Trditev 2.10.

A_1∆= ∆

∆−1 ≤A_1i ≤A₁₂ =A_2j = 2< A₃₃= 9

4 ≤A_kl ≤A_∆∆ = ∆² 2∆−2, kjer je 2≤i, j ≤∆ in 3≤k≤l ≤∆.

Trditev 2.11. Naj bo G graf z m≥2 povezavami. Potem je AZI(G)≤ 512m

27 , kjer enakost velja za 4-regularne grafe.

Dokaz. Ker je ∆≤4, po trditvi 2.10 velja A₁₄ = 4

3 ≤A₁₃= 3

2 ≤A₁₂ =A₂₂ =A₂₃

=A₂₄= 2 < A₃₃ = 9

4 ≤A₃₄= 12

5 ≤A₄₄ = 8 3. Sledi

AZI(G) = ∑

1≤i≤j≤∆

i+j=2

m_ijA³_ij ≤mA³₄₄ = 512m 27 in enakost velja za 4-regularne grafe.

2.1.1.5 Harmonični indeks

Še ena variacija Randićevega indeksa je harmonični indeks.

Definicija 2.12. Naj bo G= (V, E) graf. Harmonični indeks je enak H(G) = ∑

uv∈E

2 d_u+d_v. Med indeksoma velja zveza

H(G)≤R(G), v kateri enakost velja za regularne grafe

∑

uv∈E

2

d_u +d_v ≤ ∑

uv∈E

√1 dudv

⇐⇒

2

d_u +d_v ≤ 1

√d_ud_v ∀uv ∈E ⇐⇒

0≤(d_u−d_v)² ∀uv ∈E.

Od tod sledi, da je zgornja meja harmoničnega indeksa enakan/2 in je dosežena na regularnih grafih.

Oglejmo si še spodnjo mejo harmoničnega indeksa za drevesa [19]. Tu sS_n ozna- čimo graf zvezde z n vozlišči.

Trditev 2.13. Naj bo T drevo z n ≥3 vozlišči. Potem je H(T)≥ ²⁽ⁿ⁻¹⁾_n . Enakost velja natanko tedaj, ko je T ∼=S_n

Dokaz. Edino drevo na treh vozliščih jeS₃ ∼=P₃. Trditev v tem primeru velja:

H(S₃) = 2 2

2 + 1 = 4

3 = 2(3−1) 3 .

Naj trditev velja za n=k ≥3. Dokazujemo, da velja za n=k+ 1. Naj bo T drevo s k+ 1 vozlišči. Potem ima T vsaj dva lista. Naj bo uv povezava z d_v = 1. Ker je k ≥3, velja 2 ≤ d_u =d ≤k. Naj bo N(u)\{v}= {v₁, v₂, ..., vd−1}, kjer je d_vi =p_i za vsak 1≤i≤d−1 in naj bo T^′ :=T − {v}. Potem je T^′ drevo sk vozlišči in po indukcijski predpostavki velja H(T^′)≥ ²⁽ⁿ⁻¹⁾_n . Sledi

H(T) =H(T^′) + 2 d+ 1 +

d−1

∑

i=1

2 p_i+d −

d−1

∑

i=1

2 p_i+d−1

=H(T^′) + 2 d+ 1 −

d−1

∑

i=1

2

(p_i +d−1)(p_i+d)

≥ 2(k−1)

k + 2

d+ 1 −

d−1

∑

i=1

2 d(d+ 1)

= 2(k−1)

k + 2

d(d+ 1) ≥ 2(k−1)

k + 2

k(k+ 1) = 2k k+ 1 in enakost velja za T ∼=S_k+1.

2.1.1.6 Indeks povezanosti vsote

Tudi indeks povezanosti vsote je različica Randićevega indeksa. Ker ni nobenega posebnega razloga za uporabo produkta dudv v Randićevem indeksu, lahko tega nadomestimo z vsoto d_u+d_v.

Definicija 2.14. Naj bo G= (V, E)graf. Indeks povezanosti vsote je enak SCI(G) = ∑

uv∈E

√ 1

d_u+d_v.

Glede na definicijo 2.14, se Randićev indeks včasih poimenuje tudi indeks pove- zanosti produkta. Oba indeksa imata zelo podobne korelacijske lastnosti.

2.1.2 Posplošitve in parametrizacija

Topološke indekse lahko na različne načine modificiramo in posplošimo. V tem raz- delku si bomo postopka modifikacije in posplošitve ogledali na primeru Randićevega indeksa, analogno pa lahko spreminjamo tudi druge topološke indekse. Tudi v tem razdelku sledimo [12].

Enačbo Randićevega indeksa prepišemo v obliko R=R(G) = ∑

uv∈E

[d_ud_v]^λ, λ=−1 2.

Za parameterλ bi lahko izbrali tudi kako drugo vrednost. Tako dobimo neskončen razred topoloških indeksov, ki jih imenujemo posplošeni Randićevi indeksi:

Rλ(G) = ∑

uv∈E

[dudv]^λ, λ∈Q.

S kemijskega vidika je najbolje izbrati tako vrednost λ, da je indeks R_λ najbolje koleriran z izbrano kemijsko lastnostjo. Izkazalo se je, da je optimalna vrednost parametra λ različna za različne kemijske lastnosti.

Randićev indeks vsebuje člene, ki opisujejo povezave molekulskega grafa G. In- deks lahko posplošimo tako, da v enačbe vključimo še bolj kompleksne strukturne lastnosti.

Naj boGmolekulski graf inu, v inwtri vozlišča, ki tvorijo pot dolžine dva, torej veljau∼v in v ∼w. Indeks povezanosti drugega reda je definiran z

2R(G) = ∑

uvw

√ 1

dudvdw

,

kjer vsota teče po vseh poteh dolžine dva. Analogno je indeks povezanosti tretjega reda definiran kot

3R(G) = ∑

uvwx

√ 1

d_ud_vd_wd_x,

kjer vsota teče po vseh poteh uvwx dolžine 3. Podobno definiramo indeks poveza- nosti n-tega reda za n≥0. Pri tem je indeks povezanosti ničtega reda enak

0R(G) = ∑

u

√1 du

.

2.1.3 Kateri topološki indeksi so dobri v praksi?

V matematični kemiji najdemo veliko oz. kar preveč topoloških indeksov. Mnogi med njimi ne zadostijo niti definiciji topološkega indeksa in so zato v kemijski pra- ksi neuporabni. I. Gutman je v [12] izpostavil problematiko pomanjkanja kriterijev, s katerimi bi določili ustreznost topoloških indeksov in posledično tudi omejili vpe- ljevanje neustreznih. Da bi lažje ločili uporabne od neuporabnih, sta I. Gutman in J.

Tošović v [14] opravila tudi primerjalni test, v katerem sta merila korelacijo topolo- ških indeksov z dvema fizikalno-kemijskima lastnostma, in sicer, merila sta korelacijo z lastnostma oktanovih izomerov: standardno tvorbeno entalpijo (termodinamična lastnost) in točko vrelišča (medmolekulski, van-der-Waalsov tip lastnosti). Rezul- tati so pokazali, da sta prvi in drugi zagrebški indeks slabo kolerirana z omenjenima lastnostma in zato v praksi precej neuporabna. Zanimivo je tudi, da modificiran Randićev indeks R_λ za λ = −1 dosega precej boljše rezultate kot običajno upora- bljeni Randićev indeks R. Vendar pa posplošeni Randićevi indeksi R_λ za λ = 2,3 dosegajo slabe rezultate in v praksi niso uporabni. Daleč najboljši korelacijski ko- eficient ima povečani zagrebški indeks, zato bi bil lahko pogosteje uporabljen. Kot drugi najboljši se je izkazal indeks povezanosti atomskih vezi oz. ABC indeks.

Eden od kriterijev, ki določa, ali je indeks primeren za uporabo (in je s tem tudi upravičen njegov obstoj oz. vpeljava), je, da se mora indeks spreminjati postopoma s postopnim spreminjanjem molekulske strukture. Za merjenje te lastnosti sta bili vpeljani dve meri: strukturna občutljivost (SS) in naglost (Abr).

Definicija 2.15. Naj bo G molekulski graf in T I dani topološki indeks. Z Γ(G) označimo množico vseh povezanih grafov, dobljenih iz grafa G tako, da eno iz- med povezav grafu G odstranimo, hkrati pa mu dodamo neko novo povezavo (tako dobimo množico grafov, ki so strukturno najbolj podobni grafu G). Strukturna ob- čutljivost je enaka

SS(T I, G) = 1

|Γ(G)|

∑

γ∈Γ(G)

⏐

⏐

⏐

⏐

T I(G)−T I(γ) T I(G)

⏐

⏐

⏐

⏐ ,

naglost pa je definirana z

Arb(T I, G) =maxγ∈Γ(G)

⏐

⏐

⏐

⏐

T I(G)−T I(γ) T I(G)

⏐

⏐

⏐

⏐ .

Strukturna občutljivost SS torej meri povprečno relativno občutljivost topo- loškega indeksa T I na majhne strukturne spremembe grafa G. Vrednost Abr pa pove, v kolikšni meri lahko mala strukturna sprememba povzroči veliko spremembo v vrednosti topološkega indeksa. V praksi je zato želeno imeti čim večjo vrednost strukturne občutljivosti SS in čim manjšo vrednost naglosti Abr [11].

Za topološke indekse iz poglavja 2.1.1 so v [11] merili vrednosti SS in Abr na množici vseh dreves zn∈ {6,7, . . . ,13}vozlišči. Rezultati so pokazali, da so indeksi razvrščeni v enakem vrstnem redu glede na vrednost meritve za vse vrednosti n.

Najvišjo vrednost strukturne občutljivosti SS imata povečani zagrebški indeks ter drugi zagrebški indeksM2. Žal pa imajo indeksi z najvišjo vrednostjo mereSS tudi najvišje vrednosti Abr in obratno. Indeks ABC, ki je bil po kriterijih korelacije z lastnostmi oktanovih izomerov precej uspešen, ima najnižjo vrednost SS. Zanimivo je tudi, da imata Randićev indeks in indeks povezanosti vsote skoraj enake vrednosti SS, te pa so precej nizke.

2.2 M-polinom

V tem poglavju si bomo ogledali potek izračuna M-polinoma. Pri določitvi njegovih koeficientov si lahko pomagamo z Gutmanovimi zvezami, pri ravninskih grafih pa dodatno še z Eulerjevo formulo. Osnovna vira poglavja sta [6] in [7].

Definicija 2.16. Naj boGgraf inm_ij(G),i, j ≥1,število povezave =uv grafaG, kjer je {d_v(G), d_u(G)}={i, j}. Potem je

M(G;x, y) = ∑

i≤j

m_ij(G)xⁱy^j

M-polinom grafaG.

2.2.1 Izračun M-polinoma

M-polinom lahko izračunamo za poljubne grafe, mi pa se bomo osredotočili na ke- mijske grafe. Spomnimo se, da so to povezani grafi, ki imajo maksimalno stopnjo vozlišč največ 4.

Naj bo Gkemijski graf. Z n_i za1≤i≤4 označimo število vozlišč stopnje i. Če ima povezan graf G vsaj tri vozlišča, velja m₁₁ = 0. Gutman je za koeficiente m_ij navedel naslednje zveze:

n₁ +n₂+n₃+n₄ =n (2.3)

m12+m13+m14=n1 (2.4)

m₁₂+ 2m₂₂+m₂₃+m₂₄= 2n₂ (2.5) m₁₃+m₂₃+ 2m₃₃+m₃₄= 3n₃ (2.6) m₁₄+m₂₄+m₃₄+ 2m₄₄= 4n₄ (2.7) n₁+ 2n₂+ 3n₃+ 4n₄ = 2m (2.8) Prvih pet zvez je linearno neodvisnih. Kadar je težko določiti koeficiente m_ij di- rektno, si lahko pomagamo z gornjimi zvezami. Postopek si bomo v nadaljevanju ogledali na primeru poliominskih verig.

Poliomina je ravninski lik, sestavljen iz enega ali več neprekrivajočih enotskih kvadratov, ki so med seboj povezani s skupnimi stranicami. Poliominska veriga pa je poliominski sistem, v katerem povezovanje centrov kvadratov z njihovimi pravimi sosedi tvori potc₁c₂...c_n, kjer je c_i center i-tega kvadrata.

Naj bo B(k;r;l₁, l₂, ..., l_r) poliominska veriga s k kvadrati in r odseki dolžin l₁, l₂, ..., l_r; l_i ≥2. Naja označuje število ekstremnih odsekov dolžine2, tj. odsekov

Slika 1: Poliominska veriga B(11; 6; 3,4,2,2,3,2). Vrednosti parametrov sta a = 1 inb = 2.

dolžine 2, ki so na koncu verige. Možno število takih odsekov je torej a = 0,1,2.

Z b označimo število ne-ekstremnih oz. notranjih odsekov dolžine 2. Za primer iz

slike 1 je a = 1 in b = 2. Izkaže se, da parametri k, r, a in b zadoščajo za določitev M-polinoma.

Trditev 2.17. Za poliominsko verigo B(k;r;l1, l2, ..., lr) je M-polinom enak M(B_n;x, y) = 2x²y²+ (2r−a−2b+ 2)x²y³+ (a+ 2b)x²y⁴

+ (3k−6r+ 1 +a+ 3b)x³y³+ (4r−a−4b−4)x³y⁴+bx⁴y⁴. Dokaz. Najprej opazimo, da je n = 2k + 2 in m = 3k+ 1. Določimo še število vozlišč stopnje i, n_i. Števili n₂ in n₄ sta enaki številu zunanjih oz. notranjih robov poliominske verige, torej n2 = r+ 3 in n4 = r−1. Vrednost n1 = 0, ker nimamo vozlišč stopnje 1 in n₃ = n−n₂ −n₄ = 2(k −r). Velja m₂₂ = 2, saj imata obe krajišči stopnje dve le skrajni povezavi. Število povezav, ki razpolavljajo notranje odseke dolžine dve, je enako številu notranjih odsekov dolžine dve in je zatom44=b.

Določimo še m₂₄ = a+ 2b, saj vsak ekstremni odsek dolžine dve prispeva po eno ustrezno povezavo, vsak notranji odsek dolžine dve pa po dve ustrezni povezavi. Iz enačb (2.3) - (2.8) lahko sedaj izračunamo še m₂₃, m₃₃ in m₃₄.

m₂₃= 2n₂−m₁₂−2m₂₂−m₂₄= 2r−a−2b+ 2 m33 = (3n3 −m13−m23−m34)/2 = 3k−6r+ 1 +a+ 3b m₃₄ = 4n₄−m₁₄−m₂₄−2m₄₄ = 4r−a−4b−4 Od tod dobimo M-polinom

M(B_k;x, y) = 2x²y²+ (2r−a−2b+ 2)x²y³+ (a+ 2b)x²y⁴+

(3k−6r+ 1 +a+ 3b)x³y³+ (4r−a−4b−4)x³y⁴+bx⁴y⁴. Oglejmo si še poseben primer linearne verigeL_k zak ≥3, ki ustreza poliominski verigi z r= 1 in a=b= 0. Dobimo

M(L_k;x, y) = 2x²y²+ 4x²y³+ (3k−5)x³y³.

Za primer cik-cak verige Z_k zr=k−1, a= 2, b=r−2 =k−3dobimo M-polinom M(Z_k;x, y) = 2x²y²+ 4x²y³+ 2(k−2)x²y⁴+ 2x³y⁴+ (k−3)x⁴y⁴.

2.2.2 Razširitev Gutmnovega pristopa za ravninske grafe Zgoraj navedenim enačbam (2.3) - (2.8) dodamo še Eulerjevo formulo

∑m_ij −∑

n_i =f−2.

Uporabimo jo za ravninske grafe, pri katerih lahko enostavno določimo število lic f.

Oglejmo si sedaj uporabo sistema enačb na primeru grafa G(p, q).

GrafG(3,4)je narisan na sliki 2. Graf G(1,1)pa je sestavljen iz osemkotnika, ki ima zgoraj in spodaj dodana po dva šestkotnika. Iz omenjenih primerov bi morala biti splošna definicija grafa jasna.

Slika 2: Graf G(3,4), sestavljen iz šestkotnikov in osemkotnikov.

Trditev 2.18. Graf G(p, q) ima M-polinom oblike

M(G(p, q);x, y) = (2p+ 6)x²y²+ (8p+ 8q−4)x²y³+ (15pq−10p+ 2q−1)x³y³. Dokaz. Graf G(p.q) ima vozlišča stopenj 2 in 3, zato so neničelni koeficienti le m_2,2, m_2,3 in m_3,3. Koeficient m_2,2 izračunamo direktno:

m_2,2 = 2(p+ 1) + 4 = 2p+ 6. (2.9) Tukaj je2(p+ 1)število stranskih robov z obema krajiščema stopnje dva, prištejemo pa še 4 vogalne robove takega tipa. Enostavno je določiti tudi število vozlišč stopnje dva n₂ = 4q+ 4(p+ 1) + 2p = 6p+ 4q+ 4, kjer je 4q število zgornjih in spodnjih vozlišč,4(p+ 1)število stranskih vozlišč šestkotnikov,2ppa število stranskih vozlišč, ki pripadajo osemkotnikom. V našem primeru iz enačbe (2.6) dobimo2m2,2+m2,3 = 2n₂ oziroma

m_2,3 = 8p+ 8q−4. (2.10)

Enačba (2.7) je oblike m_2,3+ 2m_3,3 = 3n₃ in tako je

3n₃ −2m_3,3 = 8p+ 8q−4. (2.11) Graf ima pq osemkotnikov, 2q(p+ 1) šestkotnikov in 2p(q −1) petkotnikov, kar uporabimo v Eulerjevi enačbi. Dobimo

m_3,3−n₃ = 5pq−6p−2q+ 1. (2.12) Iz (2.11) in (2.12) dobimo n₃ = 10pq−4p+ 4q−2 in

m_3,3 = 15pq−10p+ 2q−1. (2.13) Iz enačb (2.9) (2.10) in (2.13) dobimo M-polinom

M(G(p, q);x, y) = (2p+ 6)x²y²+ (8p+ 8q−4)x²y³+ (15pq−10p+ 2q−1)x³y³.

2.3 Izračun BID indeksov s pomočjo M-polinoma

V tem poglavju sledimo viroma [6] in [7]. M-polinom omogoča enostaven in rutinski izračun BID indeksov. Preden si ogledamo natančnejši postopek izračuna, se spo- mnimo definicije BID indeksa:

Za dani graf G= (V, E)je BID indeks invarianta grafa oblike I(G) = ∑

e=uv∈E

f(d_u, d_v), (2.14)

kjer jef =f(x, y)primerno izbrana funkcija, uporabna v kemiji. Opazimo, da lahko enačbo (2.14) zapišemo v obliki

I(G) =∑

i≤j

m_ij(G)f(i, j). (2.15) Definirajmo sedaj operatorja D_x in D_y na odvedljivih funkcijah dveh spremen- ljivk:

D_x(f(x, y)) = x∂f(x, y)

∂x , D_y(f(x, y)) = y∂f(x, y)

∂y . Trditev 2.19. Naj bo G = (V, E) graf in I(G) = ∑

uv∈E

f(d_u, d_v), kjer je f(x, y) polinom v spremenljivkah x, y. Potem je

I(G) = f(D_x, D_y)(M(G;x, y))⏐

⏐x=y=1. Dokaz. Naj bostar ≥0in s≥0 fiksni števili. Velja

D_x^rD^s_y(M(G;x, y)) = D_x^rD^s_y (

∑

i≤j

m_i,j(G)xⁱy^j )

=D^r_x (

∑

i≤j

m_i,j(G)j^sxⁱy^j )

=∑

i≤j

m_ij(G)i^rj^sxⁱy^j. Za f(x, y) = ∑

r,sα_r,sx^ry^s je f(D_x, D_y)(M(G;x, y)) =∑

r,s

α_r,sD^r_xD_y^s(M(G;x, y)) =∑

r,s

α_r,s∑

i≤j

m_ij(G)i^rj^sxⁱy^j

=∑

i≤j

m_ij(G)∑

r,s

α_r,si^rj^sxⁱy^j.

Od tod velja

f(D_x, D_y)(M(G;x, y))⏐

⏐x=y=1 =∑

i≤j

m_ij(G)∑

r,s

α_r,si^rj^s =∑

i≤j

m_ij(G)f(i, j).

Rezultat sledi iz (2.15).

Definirajmo še operatorja S_x in S_y:

S_x(f(x, y)) =

∫

0

f(t, y)

t dt, S_y(f(x, y)) =

∫

0

f(x, t) t dt.

Trditev 2.20. Naj bo G= (V, E) graf in I(G) = ∑

uv∈E

f(d_u, d_v), kjer je f(x, y) = ∑

i,j∈Z

α_ijxⁱy^j.

Potem lahko I(G) dobimo iz M(G;x, y) z operatorji D_x, D_y, S_x, S_y. Dokaz. Naj bosta r≥0 ins ≥0.

S_x^rS_y^s(M(G;x, y)) =S_x^rS_y^s (

∑

i≤j

m_i,j(G)xⁱy^j )

=S_x^r (

∑

i≤j

m_i,j(G)j^−sxⁱy^j )

=∑

i≤j

m_ij(G)i^−rj^−sxⁱy^j.

Zaf(x, y) =∑

r,sα_r,sx^ry^s velja f(S_x, S_y)(M(G;x, y)) =∑

r,s

α_r,sS_x^rS_y^s(M(G;x, y)) =∑

r,s

α_r,s∑

i≤j

m_ij(G)i^−rj^−sxⁱy^j

=∑

i≤j

m_ij(G)∑

r,s

α_r,si^−rj^−sxⁱy^j.

Evaluiramo vx=y= 1 in dobimo željeni rezultat f(S_x, S_y)(M(G;x, y))⏐

⏐x=y=1 =∑

i≤j

m_ij(G)∑

r,s

α_r,si^−rj^−s=∑

i≤j

m_ij(G)f(i, j).

Podobno izračunamo tudi S_x^rD^s_y(M(G;x, y)) =S_x^rD_y^s

(

∑

i≤j

m_i,j(G)xⁱy^j )

=S_x^r (

∑

i≤j

m_i,j(G)j^sxⁱy^j )

=∑

i≤j

m_ij(G)i^−rj^sxⁱy^j.

Za funkcijof(x, y) = ∑

i,j∈Z

α_ijxⁱy^j dobimo

f(S_x, D_y)(M(G;x, y)) =∑

r,s

α_r,sS_x^rD^s_y(M(G;x, y)) =∑

r,s

α_r,s∑

i≤j

m_ij(G)i^−rj^sxⁱy^j

=∑

i≤j

m_ij(G)∑

r,s

α_r,si^−rj^sxⁱy^j.

f(S_x, D_y)(M(G;x, y))⏐

⏐x=y=1 =∑

i≤j

m_ij(G)∑

r,s

α_r,si^−rj^s =∑

i≤j

m_ij(G)f(i, j). (2.16)

Simetričen rezultat velja za D_x^rS_y^s(M(G;x, y)).

Za izračun nekaterih drugih oblik funkcijef(x, y)uvedemo dodatna operatorja:

J(f(x, y)) = f(x, x), Qα(f(x, y)) =x^αf(x, y), α̸= 0.

Trditev 2.21. Naj bo G = (V, E) graf in I(G) = ∑

uv∈E

f(d_u, d_v), kjer je f funkcija oblike f(x, y) = _(x+y+α)^xrys k in so r, s≥0, k ≥1 ter α∈Z. Potem je

I(G) =S_x^kQ_αJ D^r_xD_y^s(M(G;x, y))⏐

⏐x=1.

Dokaz.

S_x^kQ_αJ D_x^rD^s_y(M(G;x, y)) = S_x^kQ_αJ (

∑

i≤j

m_ij(G)i^rj^sxⁱy^j )

=S_x^kQ_α (

∑

i≤j

m_ij(G)i^rj^sx^i+j )

=S_x^k (

∑

i≤j

m_ij(G)i^rj^sx^i+j+α )

=∑

i≤j

m_ij(G)i^rj^sx^i+j+α(i+j+α)^−k.

Evalviramo v x= 1, velja

S_x^kQ_αJ D_x^rD^s_y(M(G;x, y))⏐

⏐_x=1 =∑

i≤j

m_ij(G)i^rj^s(i+j+α)^−k.

Kar je enako kot

I(G) =∑

i≤j

m_ij(G)f(i, j) =∑

i≤j

m_ij(G) i^rj^s (i+j+α)^k.

Iz rezultatov, navedenih v tem poglavju, dobimo tabelo izrazov za izračun BID indeksa iz M-polinoma. Pri tem upoštevamo, da so koeficienti α, a, b ∈ N. Tabela je povzeta po [7] in [3].

Tabela 1: Tabela izpeljav za izračun BID indeksov

oznaka topološki indeks f(x, y) izpeljava

M1(G) prvi zagrebški x+y (Dx+Dy)(M(G;x, y))⏐

⏐_x=y=1

M₂(G) drugi zagrebški xy (D_xD_y)(M(G;x, y))⏐

⏐x=y=1

mM2(G) modificiran drugi zagrebški _xy¹ (SxSy)(M(G;x, y))⏐

⏐_x=y=1

R_α(G) splošen Randićev (xy)^α (D_x^α+D^α_y)(M(G;x, y))⏐

⏐x=y=1

R^′_α(G) splošen Randićev _(xy)¹α (S_x^αS_y^α)(M(G;x, y))⏐

⏐_x=y=1

S_D(G) simetrični delitveni ^x2_xy^+y2 (D_xS_y+D_yS_x)(M(G;x, y))⏐

⏐x=y=1

H(G) harmonični _x+y² (2S_xJ(M(G;x, y))⏐

⏐_x=y=1

In(G) indeks obratne vsote _x+y^xy SxJ DxDy(M(G;x, y))⏐

⏐_x=y=1

AZI(G) povečani zagrebški (

xy x+y−2

)3

S_x³Q₋₂J D_x³D_y³(M(G;x, y))⏐

⏐x=y=1

SCIα(G) splošni indeks povezanosti vsote (x+y)^α D^α_x(J(M(G;x, y)))⏐

⏐_x=1

M₁^α(G) prvi splošni zagrebški x^α−1+y^α−1 (D_x^α−1+D^α−1_y )(M(G;x, y))⏐

⏐x=y=1

M_(a,b)(G) splošni zagrebški x^ay^b+x^by^a (D^a_xD^b_y+D_x^bD_y^a)(M(G;x, y))⏐

⏐_x=y=1

S pomočjo preprostih operacij, kot sta odvajanje in integriranje, lahko iz M-polinoma izračunamo veliko različnih topoloških indeksov stopenj vozlišč.

2.4 Izračun M-polinoma za nekaj molekulskih struktur

2.4.1 Zvezdasta drevesa

Primer je povzet po [6]. Oglejmo si izračun M-polinoma na primeru zvezdastih dreves. Zvezdasto drevo je drevo z natanko enim vozliščem stopnje večje od dva. To vozlišče imenujemo center. Če stopnjo centra označimo zn, potem zS(k₁, k₂, ..., k_n) označimo zvezdasto drevo, kjer jek_j število povezavj-tega žarka, ki izhaja iz centra.

Za tak žarek bomo rekli, da ima dolžinokj. Primer zvezdastega drevesa je na sliki 3.

Trditev 2.22. Naj boK =∑n

j=1k_j in naja označuje število žarkov z natanko eno povezavo. Potem je M-polinom zvezdastega drevesa S(k₁, k₂, ..., k_n) enak

M(S(k₁, ..., k_n);x, y) = (n−a)xy²+axyⁿ+ (K+a−2n)x²y²+ (n−a)x²yⁿ. Dokaz. Možne stopnje vozlišč v zvezdastem drevesu S(k₁, k₂, ..., k_n) so 1,2 in n.

Vrednost m₁₁ = 0 in m₁₂ = n −a, saj so to ravno vse krajiščne povezave žarkov dolžine vsaj dva. Tudim_2n=n−a; tukaj preštejemo vse centralne povezave žarkov dolžine vsaj dva. Velja m_1n = a, ker v to skupino sodijo natanko vsi žarki dolžine

Slika 3: Primer zvezdastega drevesa S(1,2,3,4,3,3,2,1). Centralno vozlišče je stopnje osem, iz njega pa izhajajo žarki dolžin med ena in štiri.

ena in mnn = 0.Izračunamo šem22=K−(n−a)−a−(n−a) =K+a−2n. Od tod dobimo M-polinom

M(S(k₁, ..., k_n);x, y) = (n−a)xy² +axyⁿ+ (K +a−2n)x²y²+ (n−a)x²yⁿ. Iz polinoma izračunajmo harmonični indeks in indeks obratne vsote.

Trditev 2.23. Naj bo K = ∑n

j=1k_j in naj a označuje število žarkov z natanko eno povezavo. Vrednost harmoničnega indeksa zvezdastega drevesa S(k₁, k₂, ..., k_n) je enaka

H(S(k₁, k₂, ..., k_n)) = (1 2 + 2

n+ 3)(n−a) + ( 2

n+ 2 + 1)a+ 2

5(K−2n), indeks obratne vsote pa

I_n(S(k₁, ..., k_n);x, y) = (1

2+ 2n

n+ 3)(n−a) + ( n n+ 2 + 4

5)a+ 4

5(K−2n).

Dokaz.

D_y(M(S(k₁, ..., k_n))) = 2(n−a)xy²+naxyⁿ+ 2(K+a−2n)x²y² +n(n−a)x²yⁿ

D_xD_y(M(S(k₁, ..., k_n))) = 2(n−a)xy²+naxyⁿ+ 4(K+a−2n)x²y² + 2n(n−a)x²yⁿ

J D_xD_y(M(S(k₁, ..., k_n))) = 2(n−a)x³+naxⁿ⁺¹+ 4(K+a−2n)x⁴ + 2n(n−a)xⁿ⁺²

S_xJ D_xD_y(M(S(k₁, ..., k_n))) = 1

2(n−a)x³+ n

n+ 2axⁿ⁺¹ + 4

5(K+a−2n)x⁴+ 2n

n+ 3(n−a)xⁿ⁺²

I_n(S(k₁, ..., k_n);x, y) =S_xJ D_xD_y(M(S(k₁, ..., k_n)))⏐

⏐x=1

= 1

2(n−a) + n

n+ 2a+ 4

5(K+a−2n) + 2n

n+ 3(n−a)

= (1

2+ 2n

n+ 3)(n−a) + ( n n+ 2 +4

5)a +4

5(K −2n)

J(M(S(k₁, ..., k_n))) = (n−a)x³ +axⁿ⁺¹+ (K+a−2n)x⁴ + (n−a)x²⁺ⁿ

2SxJ(M(S(k1, ..., kn))) = 1

2(n−a)x³+ 2

n+ 2axⁿ⁺¹ +2

5(K +a−2n)x⁴+ 2

n+ 3(n−a)xⁿ⁺² H(S(k₁, k₂, ..., k_n)) = 2S_xJ(M(S(k₁, ..., k_n)))⏐

⏐x=y=1

= 1

2(n−a) + 2

n+ 2a+ 2

5(K+a−2n)

+ 2

n+ 3(n−a) = (1 2 + 2

n+ 3)(n−a) + ( 2

n+ 2 + 1)a+2

5(K−2n).

2.4.2 Verige kaktusov

Kaktusni graf je povezan graf, v katerem imata poljubna enostavna cikla največ eno skupno vozlišče. Vsak cikel kaktusnega grafa je brez tetiv in vsak blok grafa je cikel ali povezava. Če so vsi bloki kaktusnega grafa cikli dolžine tri, se graf imenujetrikotni kaktusni graf. Podobno se tak graf s cikli dolžine 4 imenujekvadratni kaktusni graf.

Kadar imajo vsi 4-cikli kvadratnega kaktusnega grafa največ dve prerezni vozlišči in vsako prerezno vozlišče pripada natanko dvema 4-cikloma, graf imenujemo verižni kvadratni kaktus. V orto-verižnh kvadratnih kaktusih so prerezna vozlišča sosednja, pri para-verižnih kvadratnih kaktusih pa prerezna vozlišča niso sosednja.

V tem razdelku bomo izračunali M-polinom in nekatere BID indekse za različne kaktusne grafe. Rezultati za le-te so bili objavljeni v [3], vendar se naši izračuni vseh treh M-polinomov razlikujejo od navedenih v viru.

ZCOⁿ_m označimo graf orto-verižnega kaktusa, kjer je m dolžina vsakega cikla in ndolžina verige (število ciklov). Na sliki 4 je poseben primer orto-verižnega kaktusa;

trikotni kaktusni graf.

Trditev 2.24. Naj bo COⁿ_m orto-verižni kaktus in m ≥ 3, n ≥ 2. Potem je M- polinom grafa enak

M(COⁿ_m;x, y) = (mn−3n+ 2)x²y²+ 2nx²y⁴+ (n−2)x⁴y⁴.

Dokaz. GrafCOⁿ_m imamn−(n−1) = mn−n+ 1 vozlišč inmnpovezav. Določimo koeficientem_i,j: m_2,2 =mn−3n+ 2, saj so v vsakem notranjem ciklu 3 povezave z

Slika 4: Poseben primer ortoverižnega kaktusa je trikotni kaktusni graf. Sestavljen je iz ciklov dolžine tri, njegova prerezna vozlišča pa so sosednja.

vsaj enim krajiščem stopnje različne od 2, cikla na začetku in koncu verige pa imata taki le dve povezavi, m_2,4 = 2n, ker ima vsak cikel natanko dve taki povezavi in m_4,4 = n−2, ker ima vsak notranji cikel eno tako povezavo, krajna cikla pa take povezave nimata.

Graf ima vsa vozlišča stopnje 2 ali 4, zato so to edini neničelni koeficienti. M-polinom je torej oblike

M(CO_mⁿ;x, y) = (mn−3n+ 2)x²y²+ 2nx²y⁴+ (n−2)x⁴y⁴. Z danim rezultatom izračunamo prvi zagrebški indeks.

Trditev 2.25. Naj bo COⁿ_m orto-verižni kaktus in m ≥ 3, n ≥ 2. Prvi zagrebški indeks M1 je enak

M₁(COⁿ_m) = 4mn+ 8n−8.

Dokaz.

(D_x+D_y)(M(CO_mⁿ)) = (mn−3n+ 2)(2x²y²+x²2y²) + 2n(2x²y⁴+ 4x²y⁴) + (n−2)(4x⁴y⁴+ 4x⁴y⁴) = 4(mn−3n+ 2)x²y² + 12nx²y⁴+ 8(n−2)x⁴y⁴.

(D_x+D_y)(M(CO_mⁿ))⏐

⏐x=y=1 = 4(mn−3n+ 2) + 12n+ 8(n−2)

= 4mn+ 8n−8.

Trditev 2.26. Naj bo T_n trikotni verižni kaktus in n ≥2. Potem je M(Tn;x, y) = 2x²y²+ 2nx²y⁴+ (n−2)x⁴y⁴. Dokaz. V rezultat trditve (2.24) vstavimo m = 3.

Trditev 2.27. Prvi zagrebški indeks trikotnega verižnega kaktusa T_n, n ≥2 je enak M₁(T_n) = 20n−8.

Dokaz. V rezultat trditve (2.25) vstavimo m=3.

Oglejmo si sedaj še graf orto-verige Q(m, n), sestavljen iz polnega grafa K_m in m kopij grafa K_n, ki imajo po eno skupno vozlišče z grafom K_m. Prikazan je na sliki 5.

Slika 5: Orto veriga Q(m, n), sestavljena iz grafa K_m inm grafov K_n.

Trditev 2.28. Naj bo Q(m, n) orto-veriga za m, n≥2. Potem je M(Q(m, n);x, y) = m(n−1)(n−2)

2 xⁿ⁻¹yⁿ⁻¹+ (n−1)mxⁿ⁻¹y^m+n−2 +m(m−1)

2 x^m+n−2y^m+n−2.

Dokaz. Število vseh vozlišč grafa je m+ (n −1)m = mn, število vseh povezav pa (n −1)nm/2 + (m − 1)m/2. Vsa vozlišča grafa so bodisi stopnje n −1, bodisi stopnje m+n−2, zato je potrebno določiti le koeficiente mn−1,n−1, mn−1,m+n−2 in mm+n−2,m+n−2.. Dobimo

mn−1,n−1 = m(n−1)(n−2)

2 ,

saj te povezave ustrezajo povezavam podgrafov Kn−1 v Kn. Vrednost mn−1,m+n−2 = (n−1)m,

to je število povezav v grafih K_n, ki jih še nismo prešteli. Na koncu določimo še mm+n−2,m+n−2 = m(m−1)

2 ,

kar je število povezav grafaK_m. M-polinom danega grafa je torej oblike M(Q(m, n);x, y) =m(n−1)(n−2)

2 xⁿ⁻¹yⁿ⁻¹+ (n−1)mxⁿ⁻¹y^m+n−2 +m(m−1)

2 x^m+n−2y^m+n−2. 2.4.3 Rombični in cikcak benzenoidni sistemi Primer sledi viru [1].

2.4.3.1 Cikcak benzenoidni sistemi

Benzenoidni sistem lahko predstavimo kot molekulski graf, ki ga dobimo tako, da kongruentne pravilne šestkotnike razporedimo v ravnino. Pri tem upoštevamo, da se poljubna dva šestkotnika ali stikata v skupnem robu, ali pa se sploh ne stikata.

Risba razdeli ravnino v eno neskončno zunanje območje in v nekaj končnih notranjih območji. Vsa notranja območja morajo biti pravilni šestkotniki.

Cikcak benzenoidni sitem Z_n ima n vrst, v vsaki vrsti po dva šestkotnika, kot je prikazano na sliki 6.

Slika 6: Cikcak benzenoidni sistemZ_n vsebuje po dva šestkotnika v vsaki vrsti.

Trditev 2.29. Naj bo Z_n cikcak benzenoidni sistem. Potem je njegov M-polinom oblike

M(Z_n;x, y) = 2(n+ 2)x²y²+ 4nx²y³+ (4n−3)x³y³.

Dokaz. Določimo najprej število povezav in vozlišč grafaZ_n. Ker prva vrsta vsebuje dva šestkotnika, ki imata skupaj 12 povezav in je ena povezava skupna, ima prva vrsta skupaj 11 povezav. Prva in druga vrsta skupaj imata 24 povezav, od tega so tri skupne, tako da dobimo 21 različnih povezav. Nadaljujemo s štetjem in v grafu Zn preštejemo10n+ 1 povezav ter8n+ 2 vozlišč. Vsa vozlišča grafa so stopnje 2 ali 3, zato moramo določiti naslednje tri neprazne množice

m22= 2n+ 4, m₂₃= 4n,

m₃₃= 10n+ 1−(2n+ 4)−4n = 4n−3.

Po definiciji M-polinoma je M(Z_n;x, y) = ∑

i≤j

m_ijxⁱy^j = 2(n+ 2)x²y²+ 4nx²y³+ (4n−3)x³y³.

Z danim M-polinomom lahko izračunamo različne topološke indekse.

Trditev 2.30. Za cikcak benzenoidni sitemZ_nimajo topološki indeksi stopenj vozlišč naslednje vrednosti

mM₂(Z_n) = 29 18n+2

3

R_α(Z_n) = 4n9^α+ 2n4^α+ 4n6^α−3×9^α+ 4×4^α R^′_α(Z_n) = 2n+ 4

4^α +4n

6^α + 4n−3 9^α S_D(Z_n) = 62

3 n+ 2 H(Z_n) = 31

3 n+ 1 I_n(Z_n) = 64

5 n− 1 2 AZI(Z_n) = 1457

16 n−459 64.

Dokaz. Naj bo M(Z_n;x, y) = f(x, y) = 2(n+ 2)x²y²+ 4nx²y³+ (4n−3)x³y³. Potem velja

Dxf(x, y) = 4(n+ 2)x²y²+ 8nx²y³+ 3(4n−3)x³y³ D_yf(x, y) = 4(n+ 2)x²y²+ 12nx²y³+ 3(4n−3)x³y³ D_xD_yf(x, y) = 8(n+ 2)x²y²+ 24nx²y³+ 9(4n−3)x³y³

S_y(f(x, y)) = (n+ 2)x²y²+4

3nx²y³+ 1

3(4n−3)x³y³ S_xS_y(f(x, y)) = 1

2(n+ 2)x²y²+2

3nx²y³+1

9(4n−3)x³y³ D^α_y(f(x, y)) = 2^α+1(n+ 2)x²y² + 3^α4nx²y³ + 3^α(4n−3)x³y³ D^α_xD^α_y(f(x, y)) = 2^2α+1(n+ 2)x²y²+ 2^α+23^αnx²y³+ 3^2α(4n−3)x³y³

S_y^α(f(x, y)) = 1

2^α−1(n+ 2)x²y²+ 4

3^αnx²y³+ 1

3^α(4n−3)x³y³ S_x^αS_y^α(f(x, y)) = 1

2^2α−1(n+ 2)x²y²+ 1

3^α2^α−2nx²y³+ 1

3^2α(4n−3)x³y³ S_xD_y(f(x, y)) = 2(n+ 2)x²y²+ 6nx²y³+ (4n−3)x³y³

S_yD_x(f(x, y)) = 2(n+ 2)x²y²+ 8

3nx²y³+ (4n−3)x³y³ J f(x, y) = 2(n+ 2)x⁴+ 4nx⁵+ (4n−3)x⁶

S_xJ f(x, y) = 1

2(n+ 2)x⁴+4

5nx⁵+ 1

6(4n−3)x⁶ J D_xD_yf(x, y) = 8(n+ 2)x⁴+ 24nx⁵+ 9(4n−3)x⁶ SxJ DxDyf(x, y) = 2(n+ 2)x⁴+ 24

5 nx⁵+ 3

2(4n−3)x⁶

D_y³f(x, y) = 16(n+ 2)x²y²+ 108nx²y³+ 27(4n−3)x³y³ D³_xD_y³f(x, y) = 108(n+ 2)x²y²+ 864nx²y³+ 729(4n−3)x³y³ J D³_xD_y³f(x, y) = 108(n+ 2)x⁴+ 864nx⁵+ 729(4n−3)x⁶