UNIVERZITET U KRAGUJEVCU PRIRODNO-MATEMATI^KI FAKULTET Tomica Divni} NEKI REZULTATI O EKSTREMNIM VREDNOSTIMA RANDI]EVOG INDEKSA NA GRAFOVIMA Doktorska disertacija Kragujevac, 2013. IDENTIFIKACIONA STRANICA DOKTORSKE DISERTACIJE Autor Ime i prezime: Tomica Divni} Datum i mesto ro|ewa: 01. 01. 1969. Obre` Sada{we zaposlewe: Profesor u Sredwoj {koli u Varvarinu Doktorska disertacija Naslov: Neki rezultati o ekstremnim vrednostima Randi}evog indeksa na grafovima Broj stranica: 104 Broj slika: 36 Broj bibliografskih podataka: 37 Ustanova i mesto gde je rad izra|en: Prirodno-matemati~ki fakultet, Univerzitet u Kragujevcu Nau~na oblast (UDK): Matematika - kombinatorna optimizacija (51) Mentor: Dr Qiqana Pavlovi} Ocena i odbrana Datum prijave teme: 27.07.2011. Broj odluke i datum prihvatawa doktorske disertacije: 890/ II-1, 16.11.2011. Komisija za ocenu podobnosti teme i kandidata: Dr Qiqana Pavlovi} - vanredni profesor Prirodno-matemati~kog fakulteta u Kragujevcu Dr Vera Kova~evi}-Vuj~i} - redovni profesor Fakulteta organizacionih nauka u Beogradu Dr Miroslav Petrovi} - redovni profesor Prirodno-matemati~kog fakulteta u Kragujevcu Komisija za ocenu i odbranu doktorske disertacije: Dr Qiqana Pavlovi} - vanredni profesor Prirodno-matemati~kog fakulteta u Kragujevcu Dr Vera Kova~evi}-Vuj~i} - redovni profesor Fakulteta organizacionih nauka u Beogradu Dr Miroslav Petrovi} - redovni profesor Dr`avnog univerziteta u Novom Pazaru Datum odbrane disertacije: 1 Predgovor Ova doktorska disertacija je proistekla kao rezultat vi{egodi{we saradwe i rada pod mentorstvom dr Qiqane Pavlovi}, vanrednog profesora na Prirodno- matemati~kom fakultetu Univerziteta u Kragujevcu. Tema koja se obra|uje u doktorskoj disertaciji, odre|ivawe ekstremnih vredno- sti Randi}evog indeksa na prostim grafovima, je posebno interesantna i zna~ajna jer proisti~e iz prakti~ne potrebe izu~avawa strukture molekula. Kasnije i samo weno izu~avawe povezuje je sa drugim matemati~kim pojmovima na grafo- vima - matricama. Ono na {ta ~italac treba posebno da obrati pa`wu je to da se kako do istih tako i do novih rezultata dolazi na razli~ite na~ine, razli~itim metodama, {to omogu}ava boqu povezanost matemati~kih pojmova i omogu}ava dobijawe jo{ novih rezultata. Uvek blagovremeno i kooperativno mi{qewe od strane mentora dalo mi je poseban podstrek, `equ i ambiciju da istrajem u istra`iva~kom radu. Zato, ovom prilikom, najve}u zahvalnost izkazujem profesorki dr Qiqani Pavlovi}. Ta- ko|e, veliku zahvalnost iskazujem i mnogim ~lanovima Instituta za matematiku i informatiku Prirodno-matemati~kog fakulteta u Kragujevcu na podr{ci i pomo}i. Zahvaqujem se i akademiku Ivanu Gutmanu koji je prvi dr`ao predavawa na PMF-u u Kragujevcu na temu o Randi}evom indeksu, te je tako motivisao druge kolege i mene da se bavimo ovom problematikom. Posebnu podr{ku i nesumwivo poverewe sam dobijao od svoje porodice, svojih prijateqa i kolega. Tim povodom im najsrda~nije zahvaqujem. Kragujevac, januar 2013. Tomica Divni} 2 Ovu doktorsku disertaciju posve}ujem |acima moje {kole, Sredwe {kole u Var- varinu, sa `eqom da im bude inspiracija i te`wa ka sli~nim ciqevima. Poruka: Matematiku ~ini skup pojmova (definicija, ~iwenica) i skup tvr- |ewa (veza me|u pojmovima). ^esto se pitamo: kako se re{ava zadatak iz mate- matike? Prvo treba da znamo: ako je zadatak (problem) postavqen, to postoji na~in da se on re{i! Ali kako? Zadatak ~itamo pa`qivo (polako) tako da svaku re~ (svako slovo) shvatimo u potpunom zna~ewu. Razlikujemo date podatke od zadatog ciqa. Analiziramo date podatke i sve {to o wima znamo i sa wima mo`emo da radimo. Kada dobro shvatimo {ta se u zadatku daje i {ta sve to {ire zna~i, usredsredimo se na ciq zadatka - krajwi rezultat. ^esto i krajwi rezultat treba analizirati i posma- trati ga u nekom lak{em prepoznatqivijem obliku. Zadatak re{avamo tako {to pomo}u datih podataka i nekih drugih op{tih tvr|ewa (kojih se u datom momentu treba setiti) pi{emo logi~ki o~igledan sled ekvivalentnih zakqu~aka. Na kraju jo{ jednom (ili vi{e puta) proverimo ispravnost re{ewa. Tomica Divni} Sadr`aj Predgovor 1 1 Uvod 6 2 Op{ti deo - osnovni pojmovi, definicije i pregled rezultata 10 2.1 Grafovi - osnovni pojmovi i definicije . . . . . . . . . . . . . . . 10 2.2 Definicija Randi}evog indeksa i pregled rezultata . . . . . . . . . 12 2.3 Osnovni pojmovi konveksne analize i matemati~kog programirawa . . . . . . . . . . . . . . . . . . . . . . 14 3 Matemati~ki modeli i metode 18 3.1 Matemati~ki modeli . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2 Matemati~ke metode . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2.1 Odre|ivawe minimalne vrednosti Randi}evog indeksa primenom metode linearnog programirawa . . . . . . . . . . 23 3.2.2 Odre|ivawe minimalne vrednosti Randi}evog indeksa primenom kvadratnog programirawa . . . . . . . . . . . . . 25 4 Maksimalna vrednost Randi}evog indeksa 34 5 Minimalna vrednost Randi}evog indeksa za k ≥ T 2 37 5.1 Hipoteze i opis problema . . . . . . . . . . . . . . . . . . . . . . . . 37 5.2 Prvi slu~aj: n ≡ 0(mod 4), ili n ≡ 2(mod 4) i k neparno . . . . . . 41 5.3 Drugi slu~aj: n je neparan broj . . . . . . . . . . . . . . . . . . . . . 45 5.4 Tre}i slu~aj: n ≡ 2(mod 4) i k paran broj . . . . . . . . . . . . . . . 50 6 Minimalna vrednost Randi}evog indeksa za k ≤ T 2 56 7 Uop{tewa nekih rezultata o ekstremnim vrednostima Randi}evog indeksa na grafovima 67 7.1 Uop{tewa rezultata u slu~aju kada je k ≥ T 2 . . . . . . . . . . . . . . 68 7.2 Slu~aj kada su kNm i n neparni brojevi . . . . . . . . . . . . . . . . 73 7.2.1 Maksimalna vrednost funkcije γ) kada je np = 1 . . . . . . . 78 7.2.2 Maksimalna vrednost funkcije γ2 . . . . . . . . . . . . . . . 85 7.2.3 Gorwa granica funkcije γ) kada je np ≥ 2 . . . . . . . . . . . 87 7.2.4 Dokazi teorema . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4 SADR@AJ 7.3 Uop{tewa rezultata u slu~aju kada je k ≤ T 2 . . . . . . . . . . . . . . 96 Dodatak 98 Literatura 100 Biografija 103 5 Glava 1 Uvod Nala`ewe najboqeg, optimalnog re{ewa u bilo kojoj situaciji je svakodnevni ciq svake osobe bez obzira ~ime se bavi. Oblast matematike koja se bavi proble- mima optimizacije, pod odre|enim uslovima, naziva se matemati~ko programi- rawe. Problem matemati~kog programirawa je, u najkra}im crtama, odre|ivawe ta~ke u nekom vektorskom prostoru koja zadovoqava neka ograni~ewa, a u kojoj data funkcija posti`e ekstremnu vrednost. Jedna od podoblasti matemati~kog programirawa je diskretno programirawe odnosno kombinatorna optimizacija. U kombinatornoj optimizaciji tra`i se ekstremna vrednost neke funkcije de- finisane na kona~nom ili prebrojivo beskona~nom skupu. Kao posebno va`ni delovi kombinatorne optimizacije su celobrojno programirawe i optimizacija na grafovima. Tema ove disertacije je upravo jedan problem optimizacije na gra- fovima, to jest odre|ivawe ekstremnih vrednosti Randi}evog indeksa na prostim grafovima. Prosti grafovi su grafovi bez dvostrukih grana, bez petqi i bez usmerenih grana. Graf, kao model rasporeda elemenata nekog skupa i postoje}ih veza izme|u wih, je nezaobilazan pojam u svim oblastima qudskog istra`ivawa. O tome go- vore mnogi nau~ni radovi, monografije, kwige i drugo. Bilo koji molekul se mo`e predstaviti pomo}u grafa. Upravo, izu~avaju}i molekule alkana, Milan Randic´ shvata vezu izme|u nekih fizi~ko-hemijskih osobina i same strukture mo- lekula, odnosno veza u wima. Posmatrano {ire, struktura grafova je opisivana na vi{e na~ina (npr. pojmom prose~na daqina, hromatskim brojem i drugo), a posebnu karakteristiku strukture daje takozvani Randi}ev indeks (indeks pove- zanosti, indeks granawa). Postoji korespodencija izme|u Randi}evog indeksa i nekih fizi~kohemijskih osobina alkana, kao {to su npr. ta~ka kqu~awa, ta~ka mr`wewa i drugo. Randi}evindeks nekog grafapredstavqa zbir te`ina svih grana grafa. Te`ina proizvoqne grane grafa mo`e se definisati na vi{e na~ina, a ovde }e to biti recipro~na vrednost kvadratnog korena iz proizvoda stepena ~vorova koje spaja ta grana. Predmet ove disertacije je da se na skupu prostih grafova sa n ~vorova G(kN n) i minimalnim stepenom ~vorova jednakim k, odredi minimalna (i maksi- malna) vrednost tog indeksa kao i grafovi na kojima se ona posti`e. Mada je Milan Randic´ definisao ovaj indeks 1975. godine [35], najve}i broj 6 1. UVOD rezultata je iz posledwih dvadesetak godina. Ovim istra`ivawima su se bavili, pored ameri~kih (hemi~ar M. Randi} je radio na Tufts univerzitetu u Medford- u, dr`ava Massachusetts), mnogi evropski i kineski istra`iva~i. Posebno se isti~e kanadski nau~nik Pierre Hansen [1N 2N 3N 6N 7N 17N 18N 19]. Naime, pored toga {to se me|u prvima bavi ovom problematikom, on je sa G.Caporossi -jem 2000. godine napravio sistem AutoGraphix [7], koji je od velike pomo}i za stvarawe hipoteza o ekstremnim vrednostima. Na kraju pomenu}emo na{eg akademika pro- fesora Ivana Gutmana koji je objavio veliki broj radova (npr. [16N 5N 6N 23N 28]) i monografija [15N 23] o Randi}evom indeksu. Tako|e, nekoliko kwiga je posve}eno ovom topolo{kom indeksu [20N 21N 22], kao i veliki broj doktorskih teza. Napo- menimo jo{ da postoji veza izme|u Randi}evog indeksa i sopstvenih vrednosti Ltpltvx-ove matrice pridru`ene grafu. Sve hipoteze koje se odnose na ekstremne vrednosti Randi}evog indeksa na prostim grafovima su u potpunosti re{ene. U radu }e biti predstavqeni svi va`niji dokazi, a sama disertacija sadr`i sedam glava i dodatak. Prva glava, kao {to se vidi, je uvodnog karaktera. U woj se utvr|uju mesto i zna~aj nau~nih istra`ivawa u vezi sa temom doktorske disertacije. Tako|e, daju se i uvodna obja{wewa narednih glava. Posebno, na kraju ove glave, se isti~e doprinos autora doktorske disetracije nau~nim istra`ivawima. U drugoj glavi se na po~etku daje pregled osnovnih pojmova iz teorije grafova koji su neophodni za daqi rad. Ovde se iznosi i sama definicija Randi}evog in- deksa na prostim grafovima proizvoqnog reda n. U najkra}em je iznesen pregled rezultata i na~in dokazivawa. U posledwem delu ove glave dati su najosnovniji pojmovi iz konveksne analize, koja je teorijska osnova za veliki deo oblasti ma- temati~kog programirawa. Tako|e su iznesene i najva`nije definicije i ideje matemati~kog programirawa na koje se zasnivaju mnogi dokazi u narednim gla- vama. Tre}a glava na prvom mestu govori o matemati~kim modelima, odnosno opi- sima samih grafova koje }emo kasnije da koristimo. Navedeni su razli~iti mo- deli istog skupa grafova. Razlog tome je upravo to, {to se do raznih dokaza dolazi na osnovu razli~itih modela. Za dokazivawe razli~itih tvr|ewa kori{}eno je i vi{e metoda: grafovska metoda, metode linearnog i kvadratnog programirawa i druge. U ovoj glavi je, pored izno{ewa ovih metoda, dat i prikaz nekih rezultata. Do prvih rezultata, odre|ivawe maksimalne vrednosti Randi}evog indeksa na prostim grafovima [14] , odre|ivawe minimuma Randi}evog indeksa za grafove minimalnog stepena ~vorova jedan, dva, pa onda i tri dolazi se, prvo, grafovskom tehnikom [4N 10], a zatim i linearnim programirawem [28N 30N 25]. Upravo jedan od tih po~etnih rezultata, odre|ivawe minimuma Randi}evog indeksa na prostim grafovima bez izolovanih ~vorova je, uz izvesne promene, i predstavqen u ovoj glavi. Ovaj dokaz je sproveden metodom linearnog programirawa. Od posebne va`nosti je i rezultat koji se nalazi u radu [33] i koji se tako|e iznosi u ovoj glavi. U wemu se prvi put za ovaj problem koristi ideja kvadratnog programira- wa. ^etvrta glava govori o maksimalnoj vrednosti Randi}evog indeksa i zasniva se na radovima [14] i [28]. Maksimalna vrednost na skupu prostih grafova reda n 7 1. UVOD je T 2 i dobija se na bilo kom regularnom grafu, koji nije nultog stepena regular- nosti, iz tog skupa. U petoj glavi su posebno va`ni rezultati jer su obra|eni grafovi sa n ~vorova minimalnog stepena ~vorova k pri ~emu je k ≥ T 2 . Rezultati u ovoj glavi se za- snivaju na radu [27]. Minimalna vrednost Randi}evog indeksa zavisi, pored toga {to je k ≥ T 2 , i od odnosa brojeva k i n. Do rezultata se dolazi u vi{e slu~aja: 1) n ≡ 0(mod 4), ili je n ≡ 2(mod 4) i k je neparan broj; 2) n je neparan broj; 3) n ≡ 2(mod 4) i k je paran broj. B.Liu i J. Liu su re{ili slu~ajeve 1) i 2) (sli~no kao u radovima [31N 33]), a autor disertacije, zajedno sa svojim mentorom Lj. Pa- vlovic´ i M. Stojanovic´, su{tinski pojednostavquju pomenute rezultate slu~ajeva 1) i 2) i re{avaju najte`i slu~aj 3). Upravo ti pojednostavqeni dokazi }e biti izneseni u ovoj glavi. Odre|ivawe minimalne vrednosti Randi}evog indeksa na prostim grafovima reda n minimalnog stepena ~vorova k, gde je k ≤ T 2 , predstavqeno je u {estoj glavi i zasniva se na radu [11]. Dobijenim rezultatom je kona~no dokazana hipoteza koja je postavqena prvi put u radu [10], a zatim preciznije u [1] i na kraju u [27]. Do tog rezultata je bilo o~igledno te{ko do}i s obzirom da je posledwi dokazan. Time se, zajedno sa petom glavom, daje u potpunosti re{ewe problema nala`ewa minimalne vrednosti Randi}evog indeksa na posmatranom skupu grafova. Svi prethodno dobijeni rezultati o minimalnoj vrednosti Randi}evog indeksa mogu da se dobiju kao posebni slu~ajevi rezultata iznesenih u ove dve glave, a koji se zasnivaju na radovima [27] i [11]. Sedma glava sadr`i uop{tewa ve}ine rezultata prethodne dve glave. Ovi re- zultati se zasnivaju na radovima [27N 11N 12]. Ispostavqa se da je mo`da i najte`i dokaz, u ~itavom nala`ewu ekstremnih vrednosti i ekstremalnih grafova (gra- fova na kojima se te vrednosti posti`u), upravo dokaz jednog uop{tewa [12]. Naime, treba odrediti minimalnu vrednost Randi}evog indeksa i grafove na kojima se ta vrednost ostvaruje, na skupu grafova kada je: ukupan broj ~vorova n neparan broj, kada je minimalni stepen ~vorova k ≥ T 2 neparan broj i kada je maksimalni stepen ~vorova m < n tako|e neparan broj. Kako bi se na{la od- govaraju}a ekstremna vrednost koja je ostvariva na nekom grafu ovaj dokaz se u mnogome razlikuje od dokaza u petoj glavi. Kao {to je iz teorije grafova poznato, ukupan broj ~vorova neparnog stepena u grafu je paran. Ovo tvr|ewe u mnogome komplikuje dokaz pod odre|enim uslovima. U dodatku, na kraju doktorske disertacije, su na engleskom jeziku ukratko su- mirani svi prethodno prikazani rezultati. Mada je ve} pomenuto, najva`niji doprinos autora u ovoj disertaciji ogleda se u slede}im rezultatima: • odre|ivawe minimalne vrednosti Randi}evog indeksa na skupu prostih gra- fova reda n bez izolovanih ~vorova [11N 12N 27]; • sprovo|ewe kvadratnog programirawa u slu~aju k ≤ T 2 i nk ≥ n− k kao {to je u radu [33]; • stvarawe raznih modela grafova kako bi se problem sagledao sa vi{e strana 8 1. UVOD [11N 12]; • kreativnost u pojednostavqewu postoje}ih rezultata i stvarawu novih i povezivawu vi{e rezultata u jedan [27]; • pronala`ewe nove tehnike dokaza za slu~aj k ≤ T 2 na osnovu rada [11]; • uop{tewe prethodnih rezultata sagledavawemposebnih situacija prilikom nekih uop{tewa [11N 12N 27]. 9 Glava 2 Op{ti deo - osnovni pojmovi, definicije i pregled rezultata U prvom delu ovog poglavqa navedeni su osnovni pojmovi i definicije iz teorije grafova koji se koriste u daqem radu [9]. Zatim je definisan sam pojam Randi}evog indeksa na grafovima i izvr{en pregled rezultata. Na kraju su nave- deni osnovni pojmovi i teoreme konveksne analize i matemati~kog programirawa [36]. 2.1 Grafovi - osnovni pojmovi i definicije Do pre nekoliko decenija pojam grafa je naj~e{}e tuma~en kao slika odre|enog problema. Danas, graf predstavqa jedan od osnovnih matemati~kih pojmova. Veliki broj kwiga obja{wava pojmove iz teorije grafova, a ovde }e biti navedeni samo neophodni pojmovi za daqi rad. Definicija 2.1. Graf G je ure|en par (iNX) gde je i kona~an neprazan skup eleme- nata koji se nazivaju ~vorovi grafa, a X skup dvo~lanih podskupova skupa i koji se nazivaju grane grafa G. Ovako definisan graf je kona~an, neorijentisan, bez petqi i vi{estrukih grana i nazivamo ga prostim grafom. Broj ~vorova grafa G zove se red grafa i ozna~ava sa n. Broj grana grafa G ozna~ava se sa m. ^vorove grafa naj~e{}e ozna~avamo sa u i v, a granu koja spaja ~vorove u i v sa uv. U tom slu~aju za ~vorove u i v ka`emo da su susedni. Tako|e ka`emo da je grana uv incidentna ~vorovima u i v. Skup svih ~vorova grafa G koji su susedni ~voru u ozna~ava se sa a(u) i zove se susedstvo ~vora u. Za sve grane grafa G koje su incidentne istom ~voru ka`emo da su susedne grane. Definicija 2.2. Ukupan broj grana koje su sa ~vorom u incidentne nazivamo stepen ~vora u i ozna~avamo sa d(u). Ako je i = {u)N u2N . . . N uT} skup ~vorova grafa G = (iNX), tada }emo sa d)N d2N . . . N dT redom ozna~iti stepene ~vorova. Minimalan i maksimalan stepen 10 2.1. GRAFOVI - OSNOVNI POJMOVI I DEFINICIJE grafa G, koje ozna~avamo redom sa δ(G) i ∆(G), defini{u se na slede}i na~in: δ(G) = min{d)N d2N . . . N dT} i ∆(G) = mtx{d)N d2N . . . N dT}. Ako saberemo sve stepene ~vorova grafa dobijamo dvostruki broj grana, jer svaka grana doprinosi sumi stepena ~vorova dva puta: po jedanput za svaki ~vor grane. Dakle, va`i jednakost: (∗) d) + d2 + · · ·+ dT = 2m Elementarno znawe nam kazuje, da samo kada se sabere paran broj neparnih brojeva dobija se paran broj, a parni sabirci ne mewaju parnost. Istaknimo tvr|ewe koje sledi iz prethodne jednakosti: Teorema 2.1. Broj ~vorova neparnog stepena u svakom grafu je paran. Definicija 2.3. Za graf H = (i)N X)) za koji va`i i) ⊆ i i X) ⊆ X ka`emo da je podgraf grafa G = (iNX). Graf H je indukovani podgraf grafa G ako skup X) sadr`i sve grane iz X koje povezuju ~vorove iz skupa i). SaG−u }emo ozna~iti graf koji se dobija iz grafa G uklawawem ~vora u ∈ i (G) i svih grana incidentnih sa u. Sli~no sa G − uv ozna~avamo graf koji se dobija od grafa G brisawem grane uv. Definicija 2.4. Graf G je povezan ako za bilo koja dva ~vora u i v postoji niz ~vorova u = u)N u2N . . . N uk = v (2 ≤ k ≤ n), pri ~emu su bilo koja dva uzastopna ~lana niza susedni ~vorovi. U suprotnom ka`emo da je graf nepovezan. Nepovezan graf se sastoji od dva ili vi{e povezanih podgrafova koje nazivamo komponente grafa. Definicija 2.5. Ako su svi ~vorovi grafaG stepena r, tada se grafG zove regularan graf stepena r. Iz jednakosti (∗) vidimo da za regularne grafove stepena r va`i n · r = 2m t.j. m = T·X 2 te bar jedan od brojeva n - red grafa ili r - stepen regularnosti moraju biti parni. Definicija 2.6. Graf ~ija su svaka dva ~vora susedna zove se kompletan graf. Kompletan graf san ~vorova, koga ozna~avamo saKT, je regularan graf stepena r = n− 1 i on imam = T·(T−)) 2 = ( T 2 ) grana. Definicija 2.7. Bipartitan graf je graf ~iji se skup ~vorova mo`e razbiti na dva disjunktna skupa pri ~emu svaka grana spaja ~vor prvog skupa sa ~vorom drugog skupa. Kompletan bipartitan graf je bipartitan graf kod koga je svaki ~vor prvog skupa susedan sa svakim ~vorom drugog skupa. Ako je u prvom skupu r, a u drugom s ~vorova sa KX,s }emo ozna~iti kompletan bipartitan graf. Kada je r = 1 to kom- pletan bipartitan grafK),T−) nazivamo zvezda i obele`avamo sa fT. SaK∗X,s }emo ozna~iti graf koji nastaje od kompletno bipartitnog grafa KX,s povezivawem svih ~vorova u delu koji ima r ~vorova. 11 2.2. DEFINICIJA RANDI]EVOG INDEKSA I PREGLED REZULTATA Definicija 2.8. Komplement grafa G je graf G¯ koji ima iste ~vorove kao graf G, pri ~emu su dva ~vora susedna u G¯ ako i samo ako ti ~vorovi nisu susedni u G. Graf se boji na taj na~in {to se svakom ~voru pridru`i neka boja, tj. svaki ~vor se boji jednom bojom. Graf je pravilno obojen ako su svaka dva susedna ~vora obojena razli~itim bojama. Ako graf mo`e da se pravilno oboji a da se pritom upotrebi k ili mawe od k boja, graf je k-obojiv. Definicija 2.9. Hromatski broj γ(G) grafa G je jednak k, ako je graf k-obojiv a nije (k − 1)-obojiv. Ako je γ(G) = k, ka`e se da je graf G k-hromatski. Za k = 2 graf se naziva bihromatski i on je tada bipartitni. Te`inski graf je graf u kojem je svakoj grani dodeqen neki broj. Drugim re~ima, grafu G = (iNX) pridru`eno je preslikavawe ω : X 7→ R koje svakoj grani uv ∈ X dodequje broj ω (uv) kao te`inu. Funkciju ω nazivamo te`inska funkcija grafa. Definicija 2.10. Graf G = (iNX) na kome je definisana te`inska funkcija ω : X 7→ R se naziva mre`a. 2.2 Definicija Randi}evog indeksa i pregled rezultata Izu~avaju}i fizi~ko-hemijske osobine alkana, Milan Randic´ je 1975. godine [35] definisao indeks (kasnije poznat pod wegovim imenom Randi}ev indeks) na prostim grafovima, odnosno grafovima bez dvostrukih grana i petqi. Taj indeks je jednak zbiru te`ina svih grana. Te`ina neke grane jednaka je recipro~noj vrednosti kvadratnog korena proizvoda stepena krajwih ~vorova te grane. Definicija 2.11. Neka je G prost graf i X skup grana grafa G. Randi}ev indeks e(G) grafaG je: e(G) = ∑ uv∈E(G) )√ d(u)d(v) , pri ~emu suma ide preko svih grana uv grafa G. 6 5 2 3 54 3 32 1Kao primer izra~unavawa vrednosti Randi}evog indeksa uze}emo graf G) sa slike 2.1. Primetimo da: po jedna grana povezuje ~vorove stepena 1 i 4, 2 i 3, 2 i 4, 3 i 4, 4 i 5, 5 i 5; po dve grane povezuju ~vorove stepena 2 i 6, 3 i 6, 5 i 6 i pet grana je incidentno ~vorovima stepena 3 i 5. Konkretno, vrednost Randi}evog indeksa grafa G) bi}e: e(G)) = )√ )·4 + )√ 2·+ + )√ 2·4 + )√ +·4 + )√ 4·5 + )√ 5·5 + 2√ 2·6 + 2√ +·6 + 2√ 5·6 + 5√ +·5 = 4N 6789. Slika 2.1. Graf G) 12 2.2. DEFINICIJA RANDI]EVOG INDEKSA I PREGLED REZULTATA Prvo su se Randi}evim indeksom bavili hemi~ari. Tri kwige su posve}ene ovom indeksu [20N 21N 22]. Kasnije je privukao pa`wu matemati~ara. Danas, pored pomenute tri kwige, postoji i vi{e monografija o Randi}evom indeksu [15N 23]. Preko 2000 radova je, tako|e, posve}eno ovom indeksu. Veliki broj nau~nika se bavi pitawima ekstremnih vrednosti Randi}evog indeksa [4N 5N 7N 8N 14N 16], a tako- |e je va`no odrediti i grafove na kojima se te ekstremne vrednosti posti`u. Do maksimalne vrednosti Randi}evog indeksa se relativno lako dolazi [14N 28]; to su odgovaraju}i regularni grafovi. B.Bollobas i P.Erdos [4] su postavili pitawe nala`ewa minimalnih vrednosti Randi}evog indeksa na prostim grafovima sa n ~vorova, pri ~emu je dat minimalan stepen ~vorova k. Isto pitawe nagla{ava i S. Fajtlowitcz [14]. B. Bollobos i P. Erdos re{avaju problem kada je k = 1 [4]; odgovaraju}i graf je zvezda fT. Za k = 2 re{ewe je dato u [10] i odgovaraju}i graf je K ∗ 2,T−2. Oba ova slu~aja su re{ena analizom same strukture grafa, tzv. grafovskom tehnikom ili grafteoretskim pristupom. Za k = 1 i k = 2 , primenom linearnog programi- rawa, problem re{avaju Lj. Pavlovic´ i I. Gutman [28N 30], a zatim, za k = 3, X. Li i Y. Shi [25]. U radu [31] Lj. Pavlovic´ dolazi do rezultata za k = ⌊T 2 ⌋, odnosno u radu [33] Lj. Pavlovic´ i T. Divnic´ za k ≤ T 2 i nk ≥ n − k, gde je nk broj ~vorova stepena k. Za dobijawe ovih rezultata prvi put se koristi metoda kvadratnog programirawa. Posledwi slu~aj, k ≤ T 2 i nk ≥ n − k, Lj. Pavlovic´ re{ava i primenom linearnog programirawa [32]. Na slici 2.2. predstavqeni su grafovi reda n = 9 na kojima se posti`e minimalna vrednost Randi}evog indeksa, ako je minimalni stepen ~vorova k = 1 (zvezda graf), k = 2 (grafK∗2,7) i k = 3 (grafK ∗ +,6). Slika 2.2. Grafovi: f1, K ∗ 2,7 i K ∗ +,6. X.Li, B. Liu i J. Liu, smatraju}i da su re{ili problem, objavquju 2010. godine dobijene rezultate u European Journal of Operational Research [24]. Lj. Pavlovic´ uo~ava nedostatke dokaza i {aqe komentar u isti ~asopis [34]. Problem i daqe ostaje otvoren. Nakon vi{e od deset godina problem je na kraju u potpunosti re{en. U radu [11] T. Divnic´ i Lj. Pavlovic´ re{avaju slu~aj za k ≤ T 2 , a u radu [27] B. Liu, Lj. 13 2.3. OSNOVNI POJMOVI KONVEKSNE ANALIZE I MATEMATI^KOG PROGRAMIRAWA Pavlovic´, T. Divnic´, J. Liu i M. Stojanovic´ za slu~aj k ≥ T 2 . Tako|e su izvr{ena i uop{tewa rezultata kada se stepen bilo kog ~vora grafa nalazi na intervalu [kNm] gde jem najve}i stepen ~vorova u grafu [27N 11N 12]. Na kraju treba naglasiti i to da su izvr{ena i uop{tewa definicije Randi}e- vog indeksa, kao i da nastaju nove klase indeksa nalik ovom indeksu. Navedimo konkretno da su, inspirisani Randi}evim indeksom, B. Furtula i D. Vukicˇevic´ uveli novu klasu topolo{kih indeksa koju su nazvali klasom geometrijsko aritmeti~kog indeksa [37]. Autor ove disertacije, Lj. Pavlovic´ i M. Milivojevic´ su, primenom linearnog programirawa, do{li do odre|enih rezultata odre|iva- wa ekstremnih vrednosti i ekstremalnih grafova i na ovoj klasi indeksa [13]. 2.3 Osnovni pojmovi konveksne analize i matemati~kog programirawa Definicija 2.12. Skup V ⊆ RT je konveksan skup ako i samo ako za svaki xN y ∈ V i λ ∈ [0N 1] va`i λx+ (1− λ)y ∈ V. Definicija 2.13. Neka je V ⊆ RT konveksan skup. Funkcija y : V 7→R je kon- veksna funckija na V ako i samo ako za svaki xN y ∈ V i svaki λ ∈ [0N 1] va`i y(λx+ (1− λ)y) ≤ λy(x) + (1− λ)y(y). Funkcija g : V 7→R je konkavna na V ako i samo ako je funkcija −g konveksna na V. Linearna funkcija y = tx+ u je i konveksna i konkavna. Kvadratna funkcija y = x2+ ux+v, slo`ena funkcija prethodnih i mnoge druge funkcije su konveksne ili konkavne. Oblast matemati~ko programirawe se bavi odre|ivawem ta~ke nekog skupa koja zadovoqava odre|ene uslove (ograni~ewa), a u kojoj data funkcija posti`e ekstremnu vrednost. Konkretno, razmatramo problem (c ) minimizacije funkcije φ : RT 7→R na skupu k = {x ∈ RT| yi(x) ≤ 0N i = 1N 2N . . . Nm}. Skup k naziva se skup dopustivih ta~aka ili dopustivi skup; funkcije yi(x)N i = 1N 2N . . . Nm zovu se funkcije ograni~ewa, dok se funkcija φ(x) naziva funkcija ciqa. Vidimo da su sva ograni~ewa dopustivog skupa nejednakosti. To je mogu}e uvek posti}i prevo|ewem bilo koje jednakosti u dve suprotne nejednakosti. Definicija 2.14. Ta~ka x∗ ∈ k je optimalna (minimalna) ta~ka problema (c ) ako i samo ako je φ(x∗) ≤ φ(x) za svako x ∈ k . Optimalna ta~ka se jo{ naziva i globalni optimum. Problem maksimizacije funkcije φ : RT 7→R na skupu k svodi se na problem minimizacije uvo|ewem funkcije ψ(x) = −φ(x) na istom skupu. Ako su funkcije φ(x) i yi(x), za i = 1N 2N . . . Nm, konveksne funkcije tada problem: min x∈X φ(x)N 14 2.3. OSNOVNI POJMOVI KONVEKSNE ANALIZE I MATEMATI^KOG PROGRAMIRAWA k = {x ∈ RT | yi(x) ≤ 0N 1 ≤ i ≤ m}N nazivamo problem konveksnog programirawa. Kada su funkcije φ(x) i yi(x)N za i = 1N 2N . . . Nm, linearne (kvadratne) govorimo o linearnom (kvadratnom) pro- gramirawu. Ukoliko je nametnut uslov celobrojnosti govorimo o celobrojnom programirawu. Problem linearnog programirawa mo`emo zapisati u obliku (tiN v ∈ RT i ui ∈ R)1: min x∈X vTxN k = {x ∈ eT | tTi x− ui ≤ 0N 1 ≤ i ≤ m}. ^esto se u praksi sre}emo sa problemom u kome su samo ograni~ewa linearna, a koga mo`emo zapisati u obliku (tiN vj ∈ RT i uiN dj ∈ R): min x∈X φ(x)N k = {x ∈ RT | tTi x− ui ≤ 0N vTj x− dj = 0N 1 ≤ i ≤ mN 1 ≤ j ≤ k}N ili u jednostavnijem zapisu (ti ∈ RT i ui ∈ R): min x∈X φ(x)N k = {x ∈ RT | tTi x− ui ≤ 0N 1 ≤ i ≤ m }. Postoji veliki broj teorema (najpoznatije su Kuhn–Tucker -ove teoreme) koje daju potrebne i dovoqne uslove za nala`ewe optimalnih ta~aka pomenutih pro- blema. Navedimo neke od wih. Teorema 2.2. (Teorema 2.4.3 u [36].) Neka je u problemu max x∈X φ(x)N k = {x ∈ RT | tTi x− ui ≥ 0N 1 ≤ i ≤ m }N funkcijaφ(x) konkavna i diferencijabilna. Dopustiva ta~ka x( ∈ k je optimalna (maksimalna) ta~ka problema ako i samo ako postoje nenegativni brojevi λi, za 1 ≤ i ≤ m, takvi da je2: ∇φ(x() + m∑ i5) λiti = 0N λi(t T i x( − ui) = 0N 1 ≤ i ≤ m. 1 Vektor x ∈ Rn, tj. x = (x1; : : : ; xn), se ~esto u matemati~kom programirawu predstavqa u matri~nom obliku x =  x1.. . xn , odnosno xT = [ x1 : : : xn ] : 2 Za datu funkciju f 2 Rn 7→ R gradijent funkcije f(x) je∇f(x) = ( @f @x1 ; @f@x2 ; : : : ; @f @xn ) . 15 2.3. OSNOVNI POJMOVI KONVEKSNE ANALIZE I MATEMATI^KOG PROGRAMIRAWA Primetimo da je u prethodnoj teoremi naveden problem maksimizacije ({to }e i na daqe biti) i da je funkcija ciqa konkavna. Razlog tome je {to u disertaciji upravo razmatramo ovakve probleme. Navedimo daqe, odgovaraju}u teoremu kada su neka ograni~ewa jednakosti. Teorema 2.3. Neka je u problemu max x∈X φ(x)N k = {x ∈ RT | tTi x− ui ≥ 0N vTj x− dj = 0N 1 ≤ i ≤ mN 1 ≤ j ≤ k}N funkcijaφ(x) konkavna i diferencijabilna. Dopustiva ta~ka x( ∈ k je optimalna (maksimalna) ta~ka problema ako i samo ako postoje nenegativni brojevi λi, za 1 ≤ i ≤ m, i realni brojevi µj , za 1 ≤ j ≤ k, takvi da je: ∇φ(x() + m∑ i5) λiti + k∑ j5) µjvj = 0N λi(t T i x( − ui) = 0N 1 ≤ i ≤ m. Navedimo sada i dve va`ne definicije matemati~kog programirawa. Definicija 2.15. Neka je dat problem max x∈X φ(x)N k = {x ∈ RT | tTi x− ui ≥ 0N vTj x− dj = 0N 1 ≤ i ≤ mN 1 ≤ j ≤ k}. Za nenegativne brojeve λi, 1 ≤ i ≤ m, i realne brojeve µj , 1 ≤ j ≤ k, funkcija ψ(x) = φ(x) + m∑ i5) λi(t T i x− ui) + k∑ j5) µj(v T j x− dj) se naziva Lagrange -ova funkcija datog problema. Definicija 2.16. Dopustivu ta~ku x∗ problema max x∈X φ(x)N k = {x ∈ RT | tTi x− ui ≥ 0N 1 ≤ i ≤ m }N nazivamo stacionarnomta~kom ako i samo ako zadovoqava takozvane Kuhn{Tucker -ove uslove, tj. postoje nenegativni brojevi λi, za 1 ≤ i ≤ m, takvi da je: ∇φ(x() + m∑ i5) λiti = 0N λi(t T i x( − ui) = 0N 1 ≤ i ≤ m. 16 2.3. OSNOVNI POJMOVI KONVEKSNE ANALIZE I MATEMATI^KOG PROGRAMIRAWA Pored navedenih teorema koje se koriste u konveksnom (konkavnom) slu~aju nave{}emo i slede}u teoremu koja se zasniva na tzv. uslovima regularnosti. Teorema 2.4. (Teorema 37.1 u [26]) Neka je dat problem max x∈X φ(x)N k = {x ∈ RT | tTi x− ui ≥ 0N vTj x− dj = 0N 1 ≤ i ≤ mN 1 ≤ j ≤ k}N gde je φ(x) diferencijabilna funkcija. Potreban uslov da dopustiva regularna ta~ka x( ∈ k bude optimalna (maksimalna) ta~ka datog problema je da postoje nenegativni brojevi λi, za 1 ≤ i ≤ m, i realni brojevi µj , za 1 ≤ j ≤ k, takvi da je: ∇ψ(x) = ∇φ(x() + m∑ i5) λiti + k∑ j5) µjvj = 0N λi(t T i x( − ui) = 0N 1 ≤ i ≤ m. O uslovima regularnosti govore mnoga tvr|ewa, a po{to su u prethodnoj teoremi ograni~ewa linearna, nave{}emo odgovaraju}e. Lema 2.1. (Videti 38.4 u [26]) Neka je definisan skup k = {x ∈ RT | tTi x− ui ≥ 0N vTj x− dj = 0N 1 ≤ i ≤ mN 1 ≤ j ≤ k}. Ako postoji ta~ka x¯ ∈ k takva da je tTi x¯ − ui > 0 i vTj x¯ − dj = 0N za 1 ≤ i ≤ m i 1 ≤ j ≤ k, tada je svaka ta~ka x ∈ k regularna. 17 Glava 3 Matemati~ki modeli i metode U ovom delu problemu nala`ewa ekstremnih vrednosti Randi}evog indeksa na grafovima dajemo matemati~ke opise, odnosno modele koje }emo kasnije kori- stiti. Prvenstveno }emo se baviti problemom odre|ivawa minimalne vrednosti Randi}evog indeksa, s obzirom da je (pokaza}e se) odre|ivawe maksimalne vred- nosti dosta lak{e. Sam problem koji su B.Bollobas i P.Erdos postavili je veoma te`ak, te se u po~etku pojavquju samo delimi~ni rezultati. Tako|e, primewuje se i vi{e metoda. Radi ilustracije razli~itih metoda ovde }e biti dati i neki od po~etnih rezultata. 3.1 Matemati~ki modeli Ponovimo zadatak (problem) koji su postavili B.Bollobas i P.Erdos [4]: odre- diti minimalnu vrednost Randi}evog indeksa na skupu prostih grafova sa n ~vo- rova, pri ~emu je minimalni stepen ~vorova k. Ozna~imo sa G(kN n) skup prostih grafova sa n ~vorova ~iji je minimalni stepen ~vorova k. Bilo koji ~vor prostog grafa sa n ~vorova mo`e biti povezan sa najvi{e n − 1 ~vorova. Zna~i, stepen bilo kog ~vora grafa G ∈ G(kN n) je ceo broj iz intervala [kN n − 1]. Neka je xi,j broj grana koje povezuju ~vorove stepena i i j (k ≤ i ≤ j ≤ n − 1). O~igledno je xj,i = xi,j . Sada, Randi}ev indeks grafa G ∈ G(kN n) mo`emo predstaviti u slede}em obliku: e(G) = ∑ uv∈E(G) 1√ d(u)d(v) = ∑ k≤i≤j≤T−) xi,j√ ij . Neka sa nkN nk+)N . . . N nT−) ozna~imo broj ~vorova stepena kN k + 1N . . . N n − 1, respektivno. Va`i jednakost: nk + nk+) + nk+2 + · · ·+ nT−) = n. Iz svakog ~vora stepena i izlazi i grana. Prema tome, ukupan broj grana koje povezuju ~vorove ste- pena i sa ~vorovima bilo kog drugog stepena j (k ≤ j ≤ n− 1) jednak je ini. Me|u tim granama, grane koje povezuju ~vorove istog stepena i se ra~unaju duplo, pa va`i: xk,i+xk+),i+· · ·+2xi,i+· · ·+xi,T−) = ini. Konkretno, za grane koje povezuju ~vorove stepena k va`i: 2xk,k + xk,k+) + xk,k+2 + · · ·+ xk,T−) = knk. Sli~no, za grane koje 18 3.1. MATEMATI^KIMODELI povezuju ~vorove stepena k + 1 va`i: xk,k+)+2xk+),k+)+xk+),k+2+ · · ·+xk+),T−) = (k+1)nk+). Nastavimo li tako daqe, za grane koje povezuju ~vorove stepena n− 1 va`i}e: xk,T−) + xk+),T−) + xk+2,T−) + · · · + 2xT−),T−) = (n − 1)nT−). Pored ovih jednakosti ispuwene su i neke nejednakosti za proizvoqan grafG ∈ G(kN n). Broj grana xi,j , koje povezuju ~vorove stepena i i j, nije ve}i od proizvoda broja ~vo- rova ni stepena i i broja ~vorova nj stepena j: xi,j ≤ ninj , za k ≤ i ≤ n − 1 i i < j ≤ n− 1. Broj grana xi,i, koje povezuju ~vorove istog stepena, nije ve}i od Ti(Ti−)) 2 , tj. xi,i ≤ ( Ti 2 ) , za k ≤ i ≤ n− 1. Na osnovu svega prethodno re~enog, problem (c ) odre|ivawa minimuma min{e(G) : G ∈ G(kN n)} mo`emo matemati~ki predstaviti u slede}em obliku: min ∑ k≤i≤j≤T−) xi,j√ ij pri ~emu va`i: (1) 2xk,k + xk,k+) + xk,k+2 + · · ·+ xk,T−) = knkN xk,k+) + 2xk+),k+) + xk+),k+2 + · · ·+ xk+),T−) = (k + 1)nk+)N xk,k+2 + xk+),k+2 + 2xk+2,k+2 + · · ·+ xk+2,T−) = (k + 2)nk+2N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xk,T−) + xk+),T−) + xk+2,T−) + · · ·+ 2xT−),T−) = (n− 1)nT−)N (2) nk + nk+) + . . . N nT−) = nN (3) xi,j ≤ ninjN za k ≤ i < j ≤ n− 1N (4) xi,i ≤ ( ni 2 ) N za k ≤ i ≤ n− 1N (5) xi,jN ni su nenegativni celi brojevi za k ≤ i ≤ n− 1. Nejednakosti (3) i (4) su kvadratne, te je problem (c ) problem kvadratnog programirawa. Na osnovu jednakosti (1) i (2), Randi}ev indekse(G) = ∑ k≤i≤j≤T−) xi;j√ ij mo`emo predstaviti i u slede}em obliku: (6) e(G) = n 2 − 1 2 ∑ k≤i≤j≤T−) ( 1√ i − 1√ j )2 xi,j. Naime, kada se prva jednakost u (1) podeli sa k, druga sa k + 1, tre}a sa k + 2 i tako daqe, posledwa sa n− 1, dobija se: 2 k xk,k + ) k xk,k+) + ) k xk,k+2 + . . .+ ) k xk,T−) = nkN ) k+) xk,k+) + 2 k+) xk+),k+) + ) k+) xk+),k+2 + . . .+ ) k+) xk+),T−) = nk+)N ) k+2 xk,k+2 + ) k+2 xk+),k+2 + 2 k+2 xk+2,k+2 + . . .+ ) k+2 xk+2,T−) = nk+2N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ) T−)xk,T−) + ) T−)xk+),T−) + ) T−)xk+2,T−) + . . .+ 2 T−)xT−),T−) = nT−). 19 3.1. MATEMATI^KIMODELI Nakon pa`qivog sabirawa ovih jednakosti (sabirke sa leve strane sa istim in- deksima uzimati zajedno) rezultat mo`emo videti u kra}em obliku:∑ k≤i≤j≤T−) ( 1 i + 1 j ) xi,j = nk + nk+) + nk+2 + · · ·+ nT−) = nN na osnovu (2). Sada, pomo}u ovog rezultata, lako dolazimo do navedenog oblika: e(G) = ∑ k≤i≤j≤T−) xi,j√ ij = 1 2 ∑ k≤i≤j≤T−) ( 1 i + 1 j − ( 1√ i − 1√ j )2) xi,j = 1 2 ∑ k≤i≤j≤T−) ( 1 i + 1 j ) xi,j − 1 2 ∑ k≤i≤j≤T−) ( 1√ i − 1√ j )2 xi,j = n 2 − 1 2 ∑ k≤i≤j≤T−) ( 1√ i − 1√ j )2 xi,j. Defini{imo sada novu funkciju: (7) γ = ∑ k≤i 0, za 1 ≤ i ≤ j ≤ n − 1N vrednost sabirka u zbiru za Randi}ev indeks biti pozitivna, tj. [ )√ ij − √ T−) T ( ) i + ) j )] xi,j > 0. Ovim je o~igledno da se minimalna vrednost Randi}evog indeksa posti`e samo u slu~aju kada je i = 1 i j = n− 1, a to je upravo√ n− 1. Videli smo da se ta vrednost posti`e na zvezda grafu, ~ime je teorema dokazana. 2 3.2.2 Odre|ivawe minimalne vrednosti Randi}evog indeksa primenom kvadratnog programirawa Kao {to je pomenuto, prvi rezultati o ekstremnim vrednostima Randi}evog indeksa na grafovima dobijeni su grafovskom tehnikom i linearnim progra- mirawem. Nakon vi{egodi{weg zastoja dolazi se do jednog od va`nijih dokaza metodom kvadratnog programirawa. Naime, re{ava se slu~aj odre|ivawa mini- malne vrednosti Randi}evog indeksa kada je k ≤ T 2 i nk ≥ n − k [33]. Neka je nk = n−k+ t, gde se t o~igledno nalazi na intervalu 0 ≤ t ≤ k. Problem mo`emo opisati na slede}i na~in: min ∑ k≤i≤j≤T−) xi,j√ ij pri ~emu, uz nk = n− k + t, va`i: (1) 2xk,k + xk,k+) + xk,k+2 + · · ·+ xk,T−) = knkN xk,k+) + 2xk+),k+) + xk+),k+2 + · · ·+ xk+),T−) = (k + 1)nk+)N xk,k+2 + xk+),k+2 + 2xk+2,k+2 + · · ·+ xk+2,T−) = (k + 2)nk+2N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xk,T−) + xk+),T−) + xk+2,T−) + · · ·+ 2xT−),T−) = (n− 1)nT−)N (2) nk + nk+) + . . . N nT−) = nN (3) xi,j ≤ ninjN za k ≤ i < j ≤ n− 1N 25 3.2. MATEMATI^KE METODE (4) xi,i ≤ ( ni 2 ) N za k ≤ i ≤ n− 1. Re{i}emoproblem za proizvoqnu, fiksiranu vrednost t. Samimtim}e ink imati fiksiranu vrednost. Kasnije }emo odrediti ekstremnu vrednost Randi}evog in- deksa za bilo koje t za koje va`i 0 ≤ t ≤ k. Va`i teorema: Teorema 3.2. [33] Neka je G(kN n) skup prostih grafova sa n ~vorova i neka je minimalni stepen ~vorova k. Ako je broj ~vorova stepena k jednak nk = n − k + t, k ≤ T 2 , 0 ≤ t ≤ k, i t i n − k nisu istovremeno neparan i paran broj, tada je minimalna vrednost Randi}evog indeksa na skupu G(kN n): e∗T−k+t = (n− k + t)t 2k + (k − t)(n− k + t)√ k(n− 1) + (k − t)(k − t− 1) 2(n− 1) Ova vrednost se posti`e na grafovima za koje je: n∗T−) = k−t, n∗k+) = n∗k+2 = · · · = n∗T−2 = 0,x ∗ k,k = (n−k+t)tP2,x∗k,T−) = (k−t)(n−k+t), x∗T−),T−) = (k−t)(k−t−1)P2 i svi ostali x∗i,j i x ∗ i,i su jednaki 0. Napomena: Ako je t neparan i n−k paran broj, to x∗k,k nisu celi brojevi pa re{ewe ne bi bilo grafovsko. U tom slu~aju bi e∗T−k+t predstavqalo dowu granicu minimalnih vrednosti Randi}evog indeksa. Primetimo tako|e, da je za t = k broj ~vorova nk stepena k jednak n. U tom slu~aju je broj grana grafa Tk 2 , te je vrednost Randi}evog indeksa, posle deqewa sa √ kk, jednaka T 2 . Ovaj rezultat se poklapa sa vredno{}u funkcije e∗T−k+t kada je t = k. Na daqe mo`emo smatrati da je t < k. Kako bismo do{li do dokaza, problem }emo posmatrati u ranije izvedenom obliku (c2) sa malom promenom. Novi problem (c ′ 2) mo`emo zapisati u obliku: max γ = max ∑ k≤i 0. Na osnovu (17) i prethodnog rezultata zakqu~ujemo da je: 0 = µi,jyi,j = (µi + µj + ( 1√ i − 1√ j )2 )yi,j ≥ 0N te su yi,j = 0, za k ≤ i ≤ n− 2N i < j ≤ n− 2. 2 Lema 3.3. Za svaku stacionarnu ta~ku problema (c ′2) va`i: (21) γ = 1 2 λ((k − t) + 1 2 T−)∑ j5k+) ( 1√ k − 1√ j )2 nknj. 28 3.2. MATEMATI^KE METODE Dokaz. Posmatrajmo funkciju γ = ∑ k≤i γ∗, tada bi ξ bila stacionarna ta~ka problema (c ′2) te bi va`elo γ ∗ ≥ γ(ξ). 2 Dokaz teoreme 3.2. Sam dokaz teoreme sledi na osnovu prethodne leme 3.6. Videli smo da za ta~ku ξ∗, u kojoj se posti`e maksimalna vrednost funkcije γ i ujedno minimalna vrednost Randi}evog indeksa, va`i: n∗i = 0N i = k+1N . . . N n−2N n∗T−) = k − tN y∗k,k = (T−k+t)(T−k−))2 i svi ostali y∗i,j i y∗i,i jednaki 0. Sada primenimo jednakosti: (8) xi,j = ninj − yi,j za k ≤ i < n− 1N i < j ≤ n− 1N xi,i = ( Ti 2 )− yi,i za k ≤ i ≤ n− 1. Dobijamo da je: x∗k,k = ( T∗k 2 ) − y∗k,k = (T−k+t)(T−k+t−))2 − (T−k+t)(T−k−))2 = (T−k+t)t2 , x∗k,T−) = n ∗ kn ∗ T−) − y∗k,T−) = (n− k + t)(k − t)− 0 = (k − t)(n− k + t) i x∗T−),T−) =( T∗n−1 2 ) − y∗T−),T−) = (k−t)(k−t−))2 − 0 = (k−t)(k−t−))2 i svi ostali x∗i,j i x∗i,i jednaki 0. Sada mo`emo, na osnovu definicije Randi}evog indeksa e(G) = ∑ k≤i≤j≤T−) xi;j√ ij , dobiti minimalnu vrednoste∗T−k+t = (T−k+t)t 2k + (k−t)(T−k+t)√ k(T−)) + (k−t)(k−t−)) 2(T−)) , a mo`emo i na osnovu veze Randi}evog indeksa sa funkcijom γ, e(G) = T 2 − ) 2 γ (iz (6) i (8)). Nesumwivo, a i lako se pokazuje, da su rezultati isti. 2 Na slici 3.1 predstavqeni su grafovi reda n = 12 na kojima Randi}ev indeks posti`e minimalnu vrednost, kada je minimalni stepen ~vorova k = 5 i kada parametar t uzima vrednosti od 0 do 5. Teorema 3.3. [33] Neka je G(kN n) skup prostih grafova sa n ~vorova i neka je minimalni stepen ~vorova k. Ako je nk ≥ n − k, (k ≤ nP2) tada je minimalna vrednost Randi}evog indeksa na skupu G(kN n): e∗ = k(n− k)√ k(n− 1) + k(k − 1) 2(n− 1) Ova vrednost se posti`e na grafu K∗k,T−k, gde je n ∗ k = n − k, n∗T−) = k, n∗k+) = n∗k+2 = · · · = n∗T−2 = 0, x∗k,T−) = k(n − k), x∗T−),T−) = k(k−))2 i svi ostali x∗i,j su jednaki 0. 32 3.2. MATEMATI^KE METODE Slika 3.1. Ekstremni grafovi za: n = 12N k = 5 i t = 0N 1N 2N 3N 4N 5 . Dokaz. Na|imo parcijalni izvod funkcije e∗T−k+t = (T−k+t)t 2k + (k−t)(T−k+t)√ k(T−)) + (k−t)(k−t−)) 2(T−)) po t, za 0 ≤ t ≤ k. Se∗T−k+t St = n− k + 2t 2k + −n+ 2k − 2t√ k(n− 1) + −2k + 2t+ 1 2(n− 1) = n− 2k + 2t 2k + 1 2 − n− 2k + 2t√ k(n− 1) + n− 2k + 2t 2(n− 1) − 1 2 = n− 2k + 2t 2 ( 1√ k − 1√ n− 1 )2 ≥ 0. Funkcija e∗T−k+t je rastu}a na intervalu [0N k] i posti`e minimalnu vrednost e∗ = k(T−k)√ k(T−)) + k(k−)) 2(T−)) za t = 0. 2 33 Glava 4 Maksimalna vrednost Randi}evog indeksa Problem odre|ivawa maksimalne vrednosti Randi}evog indeksa na prostim grafovima re{ava prvo S. Fajtlowicz grafovskom metodom u radu [14]. Zatim i LJ. Pavlovic´ i I. Gutman dolaze do istog rezultatametodom linearnog programirawa [28]. U ne{to izmewenom obliku bi}e prezentovan drugi rezultat. Razmatramo proste grafove G sa n ≥ 2 ~vorova (graf sa jednim ~vorom nema grane i vrednost Randi}evog indeksa je nula). Na osnovu definicije Randi}evog indeksa e(G) = ∑ k≤i≤j≤T−) xi;j√ ij va`i: Lema 4.1. Ako je graf G sastavqen od komponenti G)N G2N . . . N Gp, tada je e(G) = e(G)) +e(G2) + · · ·+e(Gp). Dokaz. Ukoliko je graf sastavqen od komponenti, sabirawe te`ina grana u svakoj komponenti daje vrednosti Randi}evog indeksa po komponentama. Ukupan zbir vrednosti Randi}evih indeksa svih komponenti je ujedno i zbir te`ina svih grana grafa, t.j. vrednost Randi}evog indeksa grafa. 2 Lema 4.2. Ako je graf G reda n regularan graf stepena r > 0, tada je e(G) = T 2 . Dokaz. Znamo da regularan graf G stepena r ima m = T·X 2 grana. Svaka grana ima istu te`inu )√ XX = ) X . Po definiciji vidimo da je vrednost Randi}evog indeksa e(G) = n·r 2 X = T 2 . 2 Vidimo da na vrednost Randi}evog indeksa regularnog grafa ne uti~e stepen regularnosti r. Na istu vrednost ne}e uticati ni ako je graf G sastavqen od regularnih komponenti. Stepeni regularnosti ovih komponenti mogu biti i razli~iti, ali pozitivni brojevi. Lema 4.3. Ako je graf G reda n sastavqen od regularnih komponenti nenultog stepena, tada je e(G) = T 2 . Dokaz. Neka su komponente grafa G: G)N G2N . . . N Gp reda n)N n2N . . . N np, respek- tivno, pri ~emu je n) + n2 + · · · + np = n. Vrednosti Randi}evog indeksa kom- ponenti G)N G2N . . . N Gp , na osnovu prethodne leme 4.2. su: T1 2 , T2 2 ,. . . , Tp 2 , respek- tivno. Na osnovu leme 4.1., vrednost Randi}evog indeksa grafa G je: e(G) = 34 4. MAKSIMALNA VREDNOST RANDI]EVOG INDEKSA e(G)) + e(G2) + · · · + e(Gp) = T12 + T22 + · · · + Tp2 = T1+T2+···+Tp2 = T2 , {to je i trebalo dokazati. 2 Doka`imo sada slede}e tvr|ewe: Teorema 4.1. [28] Za bilo koji grafG reda n je vrednost Randi}evog indeksae(G) ≤ T 2 . Maksimalna vrednost T 2 se posti`e na grafovima u kojima su sve komponente nenultog stepena regularnosti. Dokaz. Graf sa dva ~vora mo`e biti bez grane ili sa jednom granom. U prvom slu~aju je vrednost Randi}evog indeksa 0, a u drugom )√ )·) = 1. U drugom slu~aju je to regularan graf stepena 1 i vrednost je tako|e 2 2 = 1. Teorema je ispuwena. Neka je n ≥ 3. U po~etku razmatrajmo grafove sa n ~vorova bez izolovanih ~vorova. Zna~i, najni`i stepen ~vorova je k = 1. Ranije izvedenu vrednost Randi}evog indeksa, (6) e(G) = n 2 − 1 2 ∑ k≤i≤j≤T−) ( 1√ i − 1√ j )2 xi,jN s obzirom da je k = 1, mo`emo zapisati u obliku: (6∗) e(G) = n 2 − 1 2 ∑ )≤i≤j≤T−) ( 1√ i − 1√ j )2 xi,j. pri ~emu su ispuweni uslovi: (1∗) 2x),) + x),2 + x),+ + · · ·+ x),T−) = n)N x),2 + 2x2,2 + x2,+ + · · ·+ x2,T−) = 2n2N x),+ + x2,+ + 2x+,+ + · · ·+ x+,T−) = 3n+N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x),T−) + x2,T−) + x+,T−) + · · ·+ 2xT−),T−) = (n− 1)nT−)N (2∗) n) + n2 + n+ + · · ·+ nT−) = n. O~igledno, maksimalna vrednost Randi}evog indeksa grafa G je T 2 ako i samo ako je xi,j = 0 za 1 ≤ i < j ≤ n − 1. Vidimo da prethodni rezultat mo`emo iskazati i slede}im re~ima: Randi}ev indeks grafa G bez izolovanih ~vo- rova ima maksimalnu vrednost ako i samo ako graf G nema grane koje pove- zuju ~vorove razli~itog stepena. Uo~imo, tako|e, da vrednosti promenqivih x),)N x2,2N . . . N xT−),T−) nisu u potpunosti odre|ene. Prethodni rezultat mo`emo i ovako formulisati: Randi}ev indeks grafa G bez izolovanih ~vorova ima mak- simalnu vrednost ako i samo ako graf G sadr`i samo grane koje povezuju ~vorove istog stepena. Ovo tvr|ewe nam i ukazuje na to da se maksimalna vrednost posti`e upravo na grafovima u kojima su sve komponente nenultog stepena regularnosti. Kao {to je pomenuto na po~etku, razmatrali smo grafove sa n ~vorova bez izolovanih ~vorova i dobili da se maksimalna vrednost Randi}evog indeksa T 2 35 4. MAKSIMALNA VREDNOST RANDI]EVOG INDEKSA dosti`e na grafovima u kojima su sve komponente nenultog stepena regularno- sti. Neka je, sada, G) graf sa p izolovanih ~vorova, gde je p > 0. Neka je G2 graf sa n − p ~vorova koji nastaje od grafa G) brisawem svih izolovanih ~vo- rova. Tada je graf G2 bez izolovanih ~vorova pa, na osnovu ranije pokazanog, ima vrednost Randi}evog indeksa e(G2) = T−p 2 < T 2 . Na osnovu leme 4.1., grafovi G) i G2 imaju jednake vrednosti Randi}evog indeksa. Zakqu~ujemo da vrednost Randi}evog indeksa bilo kog grafa G reda n ne mo`e biti ve}a od T 2 . Time je teorema u potpunosti dokazana. 2 Na slikama 4.1. i 4.2. vidimo primere grafova reda n = 6 na kojima se posti`e maksimalna vrednost Randi}evog indeksa. Slika 4.1. Regularan graf stepena 3. Slika 4.2. Graf G = K2 ⋃ K4. 36 Glava 5 Minimalna vrednost Randi}evog indeksa za k ≥ n2 Problem koji su postavili B. Bollobas i P. Erdos [4], odrediti minimalnu vrednost Randi}evog indeksa na skupu prostih grafova sa n ~vorova pri ~emu je minimalni stepen ~vorova kN podeli}emo u dva dela. U ovoj glavi re{i}emo dati problem u slu~aju kada je k ≥ T 2 , a re{ewe u slu~aju kada je k ≤ T 2 bi}e dato u narednoj glavi. 5.1 Hipoteze i opis problema Kao{to smo ranije imali,G(kN n) ozna~ava skup prostih grafova sa n ~vorova ~iji je minimalni stepen ~vorova k. Za k = 1 problem su re{ili B. Bollobas i P. Erdos [4]. Re{avaju}i problem za k = 2, C. Delorme, O. Favaron i D. Rautenbach [10] postavqaju i prvu pretpostavku op{teg re{ewa. Hipoteza 5.1. [10] Ako je graf G reda n i δ(G) ≥ k, tada je: e(G) ≥ k(n− k)√ k(n− 1) + k(k − 1) 2(n− 1) N pri ~emu je jednakost ispuwena ako i samo ako je G = K∗k,T−k. Ranije smo videli da je ova pretpostavka potvr|ena u slu~aju kada je k ≤ T 2 i nk ≥ n − k [33]. Me|utim, ispostavilo se da u op{tem slu~aju ona ne va`i. Nakon {to su G. Caporossi i P. Hansen napravili sistem AutoGraphix dolazi se do mnogo ta~nijih pretpostavki u vezi grafova. M. Aouchiche i P. Hansen 2007. godine u radu [1] iznose spisak hipoteza o Randi}evom indeksu. Upravo tu se nalazi i ispravqena hipoteza u vezi problema koji su postavili B.Bollobas i P.Erdos. 37 5.1. HIPOTEZE I OPIS PROBLEMA Neka je kT =  T+2 2 za n ≡ 0(mod 4)N T++ 2 za n ≡ 1(mod 4)N T+4 2 za n ≡ 2(mod 4)N T++ 2 za n ≡ 3(mod 4)N p =  T−2 2 za n ≡ 2(mod 4) i k paranN ⌈T 2 ⌉ za n ≡ 3(mod 4)N ⌊T 2 ⌋ u ostalim slu~ajevimaN i neka sa GT,p,k ozna~imo familiju komplemenata grafova koji se sastoji od (n− k − 1)-regularnog grafa od p ~vorova i n− p izolovanih ~vorova (slika 5.1.). GT,p,k GT,p,k Slika 5.1. Graf iz GT,p,k i wegov komplement, za n = 7N k = 5N i p = 4. Familiju GT,p,k mo`emo tako|e opisati kao familiju grafova sa n ~vorova koja nastaje iz kompletnog grafaKT brisawem grana (n−k−1)-regularnog grafa od p ~vorova. Hipoteza 5.2. [1] Ako je graf G reda n i δ(G) ≥ k, tada je: e(G) ≥  k(k−)) 2(T−)) + k(T−k)√ k(T−)) za k < kTN (T−p)(T−p−)) 2(T−)) + p(p+k−T) 2k + p(T−p)√ k(T−)) za kT ≤ k ≤ n− 2N gde su kT i p prethodno definisani, pri ~emu je ispuwena jednakost ako i samo ako je G = K∗k,T−k za k < kT, i ako i samo ako je G ∈ GT,p,k (opisano iznad) za k ≥ kT. Vidimo da se za 1 ≤ k ≤ T 2 obe hipoteze poklapaju, dok su za k > T 2 razli~ite. Oba izraza dowe granice za vrednost Randi}evog indeksamo`emo transformisati u nove oblike. Za prvi izraz va`i: k(k−)) 2(T−)) + k(T−k)√ k(T−)) = T 2 − T 2 + k(k−T+T−)) 2(T−)) + k(T−k)√ k(T−)) = T 2 − T 2 + k 2 − k(T−k) 2(T−)) + k(T−k)√ k(T−)) = T 2 − T−k 2 + k(T−k)√ k(T−)) − k(T−k) 2(T−)) = T 2 − ) 2 ( ) k − 2√ k(T−)) + ) T−) ) k(n − k) = T 2 − ) 2 ( )√ k − )√ T−)) 2k(n − k). Za drugi izraz va`i: (T−p)(T−p−)) 2(T−)) + p(p+k−T) 2k + p(T−p)√ k(T−)) = T−p 2 − (T−p)p 2(T−)) + p 2 − p(T−p) 2k + p(T−p)√ k(T−)) = T−p+p 2 − ) 2 ( ) k − 2√ k(T−)) + ) T−) ) p(n−p) = T 2 − ) 2 ( )√ k − )√ T−)) 2p(n−p).Sada mo`emo prethodnu hipotezu (datu u [1]) iskazati u novom obliku. 38 5.1. HIPOTEZE I OPIS PROBLEMA Hipoteza 5.3. [27] Ako je graf G reda n i δ(G) ≥ k, tada je: e(G) ≥ { T 2 − ) 2 ( )√ k − )√ T−)) 2k(n− k) za k ≤ T 2 N T 2 − ) 2 ( )√ k − )√ T−)) 2p(n− p) za T 2 ≤ k ≤ n− 2N gde je p =  T 2 za n ≡ 0(mod 4); n ≡ 2(mod 4) i k neparanN ⌊T 2 ⌋ ili ⌈T 2 ⌉ za n ≡ 1(mod 4) i k paran; n ≡ 3(mod 4) i k paranN ⌊T 2 ⌋ za n ≡ 1(mod 4) i k neparanN T−2 2 ili T+2 2 za n ≡ 2(mod 4) i k paranN ⌈T 2 ⌉ za n ≡ 3(mod 4) i k neparan. Jednakost va`i ako i samo ako jeG = K∗k,T−k, za k ≤ T2 , i ako i samo ako jeG ∈ GT,p,k (opisano ranije), za k > T 2 . Ovde }e biti predstavqen dokaz upravo izmewene hipoteze Aouchiche i Hansen za T 2 ≤ k ≤ n − 2. U dosta pojednostavqenom obliku metode kvadratnog progra- mirawa koju smo ranije videli (u tre}oj glavi), do}i }emo do optimalnog re{ewa u vi{e slu~ajeva. Konkretno, problem }emo podeliti u slede}a tri slu~aja: 1) n ≡ 0(mod 4), ili je n ≡ 2(mod 4) i k je neparan broj; 2) n je neparan broj; 3) n ≡ 2(mod 4) i k je paran broj. B. Liu i J. Liu dokazuju prvi i drugi slu~aj sli~no kao u radovima [31N 33], odnosno kao u tre}oj glavi. Zajedno, LJ. Pavlovic´, M. Stojanovic´ i autor ove disertacije, dolaze do optimalnog re{ewa u tre}em (vide}e se) najte`em slu~aju. U ponovnom sagledavawu rezultata autor ove disertacije i LJ. Pavlovic´ pojedno- stavquju sve prethodne dokaze i umesto dokaza koji je sadr`ao 21 lemu daju dokaz koji se bazira na samo pet lema. Ponovimo matemati~ki opis navedenog problema, koji smo definisali u tre}oj glavi. Problem c odre|ivawa minimumamin{e(G) : G ∈ G(kN n)}mo`emo predstaviti u slede}em obliku: min ∑ k≤i≤j≤T−) xi,j√ ij pri ~emu, uz T 2 ≤ k ≤ n− 2, va`i: (1) 2xk,k + xk,k+) + xk,k+2 + · · ·+ xk,T−) = knkN xk,k+) + 2xk+),k+) + xk+),k+2 + · · ·+ xk+),T−) = (k + 1)nk+)N xk,k+2 + xk+),k+2 + 2xk+2,k+2 + · · ·+ xk+2,T−) = (k + 2)nk+2N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xk,T−) + xk+),T−) + xk+2,T−) + · · ·+ 2xT−),T−) = (n− 1)nT−)N (2) nk + nk+) + . . . N nT−) = n 39 5.1. HIPOTEZE I OPIS PROBLEMA (3) xi,j ≤ ninjN za k ≤ i < j ≤ n− 1N (4) xi,i ≤ ( ni 2 ) N za k ≤ i ≤ n− 1 (5) xi,jN ni nenegativni celi brojevi za k ≤ i ≤ j ≤ n− 1. Nejednakosti (3) i (4) su kvadratne, te je problem c problem kvadratnog pro- gramirawa. Kao {to je ranije navedeno, na osnovu jednakosti (1) i (2), Randi}ev indeks e(G) = ∑ k≤i≤j≤T−) xi;j√ ij mo`emo predstaviti i u slede}em obliku: (6) e(G) = n 2 − 1 2 ∑ k≤i≤j≤T−) ( 1√ i − 1√ j )2 xi,j. Sada defini{imo novu funkciju: (7) γ = ∑ k≤i γ m ) , u ovom slu~aju mo`emo zakqu~iti da je γ ∗ ) maksimalna vrednost koja se posti`e u ta~ki a∗) = ( T 2 N 0N 0N . . . N 0N T 2 ) na skupu svih dopustivih ta~aka. 2 Pokazali smo da funkcija γ) posti`e maksimalnu vrednost u ta~ki a ∗ ) . Da- qim razmatrawem vidimo da γ2 posti`e maksimalnu vrednost, koja je jednaka 0, u ta~ki l ∗) koja je definisana sa yk,k = (T−k−))T 4 i svi ostali yi,j = 0. Sve vredno- sti promenqivih, nkN nk+)N . . . N nT−)N yk,kN yk,k+)N . . . N yT−2,T−2, su celi nenegativni brojevi (s obzirom da posmatramo slu~aj:n ≡ 0(mod 4), ili n ≡ 2(mod 4) i k neparno). Pomo}u veza (8) xi,j = ninj − yi,j za k ≤ i < n− 1N i < j ≤ n− 1N xi,i = ( Ti 2 )− yi,i za k ≤ i ≤ n− 1N 43 5.3. DRUGI SLU^AJ: T JE NEPARAN BROJ sada mo`emo dobiti i vrednosti po~etnih promenqivih. Uz nk = nT−) = T2 i ostali ni = 0 za k + 1 ≤ i ≤ n − 2, bi}e (s obzirom da je yk,k = (T−k−))T4 i svi ostali yi,j = 0): xk,k = ( Tk 2 ) − yk,k = Tk(Tk−))2 − (T−k−))T4 = T(T−2)0 − (T−k−))T4 = T(2k−T) 0 N xk,T−) = T2 T 2 − 0 = T2 4 N xT−),T−) = ( Tn−1 2 ) − yT−),T−) = Tn−1(Tn−1−))2 − 0 = T(T−2) 0 , i svi ostali xi,jN xi,i jednaki nuli. Sve ove vrednosti su celi nenega- tivni brojevi te mo`emo zakqu~iti da se za wih ostvaruje minimalna vrednost Randi}evog indeksa na posmatranom skupu grafova G(kN n) u slu~aju: k ≥ T 2 i n ≡ 0(mod 4), ili n ≡ 2(mod 4) i k neparan broj. U tom slu~aju je p = T 2 te je minimalna vrednost Randi}evog indeksa e(G) = T 2 − ) 2 ( )√ k − )√ T−) )2 T2 4 = T 2 − ) 2 ( )√ k − )√ T−)) 2p(n − p) koja se posti`e na bilo kom grafu G ∈ GT,p,k, odno- sno G ∈ GT,T/2,k. Na kraju, prethodna razmatrawa mo`emo formulisati u obliku teoreme. Teorema 5.1. Ako je n ≡ 0(mod 4), ili ako je n ≡ 2(mod 4) i k neparan broj, i ako G ∈ G(kN n), tada je e(G) ≥ n 2 − n 2 8 ( 1√ k − 1√ n− 1 )2 . Ova vrednost se posti`e na bilo kom grafu G ∈ GT,T/2,k za koji je nk = nT−) = nP2N xk,k = n(2k − n)P8N xk,T−) = n2P4N xT−),T−) = n(n− 2)P8, i svi ostali xi,jN xi,i i ni su jednaki 0. Na slici 5.2. vidimo ekstremni graf G ∈ G)2,6,6, to jest graf K∗6,6, gde je n6 = n)) = 6N x6,6 = 0N x6,)) = 36 i x)),)) = 15. Slika 5.2. Graf K∗6,6. Slika 5.3. Graf K ∗ 5,5. Na slici 5.3. vidimo ekstremni graf G ∈ G)(,5,5, to jest graf K∗5,5, gde je n5 = n1 = 5N x5,5 = 0N x5,1 = 25 i x1,1 = 10. 44 5.3. DRUGI SLU^AJ: T JE NEPARAN BROJ 5.3 Drugi slu~aj: n je neparan broj Na osnovu jednakosti (12) defini{imo novu funkciju γ¯) sa γ¯)(nkN ...N nT−2) = − (∑T−2 i5k ( )√ i − )√ T−))ni )2 + n ∑T−2 i5k ( )√ i − )√ T−) )2 ni . Neka je, daqe, skup k = {(nkN ...N nT−)) | nk + ... + nT−) = n}. Tada je γ)(nkN ...N nT−)) = γ¯)(nkN ...N nT−2) za (nkN ...N nT−)) ∈ k . Funkcija γ¯) je konkavna na RT−k−) po{to je prvi iz- raz kompozicija kvadratne i linearne funkcije (sa negativnim predznakom), a drugi izraz linearna funkcija. Razmatra}emo funkciju γ¯) umesto funkcije γ). Pri tome, ta~ki (nkN ...N nT−2) ∈ RT−k−), na osnovu jednakosti (2), odgovara ta~ka (nkN ...N nT−2N n− ∑T−2 j5k nj) ∈ RT−k skupa k . Razlikujemo dva podslu~aja: prvi podslu~aj (2t) kada je najvi{i stepen ~vo- rova u grafu ∆(G) = n − 1, i drugi podslu~aj (2u) kada je ∆(G) < n − 1. Da- qe, podeli}emo prvi podslu~aj (2t) u dva nova podslu~aja: prvi (2t)) kada je nk ≤ (n− 1)P2, i drugi (2t2) kada je nk ≥ (n+ 1)P2. Podslu~aj 2t). U ovom podslu~aju je n neparan broj i nk ≤ T−)2 . Razmatramo problem c 2G1 : max − ( T−2∑ i5k ( 1√ i − 1√ n− 1 ) ni )2 + n T−2∑ i5k ( 1√ i − 1√ n− 1 )2 niN pri ~emu va`i (13) −nk + n− 1 2 ≥ 0N (14) ni ≥ 0N za k ≤ i ≤ n− 2. Ozna~imo sa a dopustivu ta~ku (nkN . . . N nT−2) problema c 2G1 (o~igledno takvih ta~aka ima; npr. za nk = 0). Po{to je funkcija γ¯) konkavna (a nesporno i dife- rencijabilna), mo`emo primeniti Kuhn–Tucker -ovu teoremu 2.2. na problemc 2G1 . Po toj teoremi, dopustiva ta~ka a je ta~ka maksimuma problema c 2G1 ako postoje nenegativni brojevi µ(, λi za k ≤ i ≤ n− 2, takvi da za funkcijuΨ definisanu sa Ψ = γ¯) + µ( ( −nk + n− 1 2 ) + T−2∑ i5k λini = − ( T−2∑ i5k ( 1√ i − 1√ n− 1 ) ni )2 + n T−2∑ i5k ( 1√ i − 1√ n− 1 )2 ni + µ( ( −nk + n− 1 2 ) + T−2∑ i5k λini va`i SΨPSni = 0 za k ≤ i ≤ n− 2, odnosno: (15) −2 ( 1√ k − 1√ n− 1 ) T−2∑ j5k ( 1√ j − 1√ n− 1 ) nj +n ( 1√ k − 1√ n− 1 )2 −µ(+λk = 0N 45 5.3. DRUGI SLU^AJ: T JE NEPARAN BROJ (16) −2 ( 1√ i − 1√ n− 1 ) T−2∑ j5k ( 1√ j − 1√ n− 1 ) nj+n ( 1√ i − 1√ n− 1 )2 +λi = 0N za k + 1 ≤ i ≤ n− 2N i (17) µ( ( −nk + n− 1 2 ) = 0N (18) λini = 0 za k ≤ i ≤ n− 2. Doka`imo prvo nekoliko pomo}nih tvr|ewa. Lema 5.2. Ta~ka a ∗ 2G1 odre|ena sa (T−) 2 N 0N . . . N 0) je ta~ka maksimuma problema c 2G1 . Dokaz. Za ovu ta~ku su ispuweni uslovi (13) i (14) te je ona dopustiva ta~ka. Iz (18), po{to je nk = T−) 2 ̸= 0, vidimo da je λ∗k = 0 i samim tim se iz (15) dobija: µ∗( = −2 ( 1√ k − 1√ n− 1 ) n− 1 2 ( 1√ k − 1√ n− 1 ) + n ( 1√ k − 1√ n− 1 )2 = ( 1√ k − 1√ n− 1 )2 . Tako|e iz (16), za k + 1 ≤ i ≤ n− 2, va`i: λ∗i = ( 1√ i − 1√ n− 1 )( 2 ( 1√ k − 1√ n− 1 ) n− 1 2 − n ( 1√ i − 1√ n− 1 )) = ( 1√ i − 1√ n− 1 )( n− 1√ k − n√ i + 1√ n− 1 ) . Funkcija )√ i je opadaju}a, a lako se pokazuje da je i funkcija ( )√ j − )√ j+) ) tako|e opadaju}a, te va`i: n− 1√ k − n√ i + 1√ n− 1 ≥ n− 1√ k − n√ k + 1 + 1√ n− 1 = (n− 1) ( 1√ k − 1√ k + 1 ) − ( 1√ k + 1 − 1√ n− 1 ) = (n− 1) ( 1√ k − 1√ k + 1 ) − T−2∑ j5k+) ( 1√ j − 1√ j + 1 ) ≥ (n− 1) ( 1√ k − 1√ k + 1 ) − (n− k − 2) ( 1√ k − 1√ k + 1 ) = (k + 1) ( 1√ k − 1√ k + 1 ) ≥ 0N 46 5.3. DRUGI SLU^AJ: T JE NEPARAN BROJ Vidimo da su µ∗( ≥ 0 i λ∗i ≥ 0, za k + 1 ≤ i ≤ n− 2. Sobzirom da dopustiva ta~ka a ∗ 2G1 ispuwava Kuhn–Tucker -ove uslove ona je i ta~ka maksimuma problema c 2G1 , {to je i trebalo dokazati. 2 Maksimalna vrednost funkcije γ¯), a samim tim i funkcije γ), na k (u oznaci γ¯∗)) }e biti: γ¯∗) = − (( 1√ k − 1√ n− 1 ) nk )2 + n ( 1√ k − 1√ n− 1 )2 nk = ( 1√ k − 1√ n− 1 )2( − ( n− 1 2 )2 + n n− 1 2 ) = ( 1√ k − 1√ n− 1 )2 n2 − 1 4 N i ona se posti`e u ta~ki a∗2G1 ∈ k odre|enoj sa (T−)2 N 0N ...N 0N T+)2 ). Podslu~aj 2t2. U ovom podslu~aju je n neparan broj i nk ≥ (n+ 1)P2. Razmatramo problem c 2G2 : max − ( T−2∑ i5k ( 1√ i − 1√ n− 1 ) ni )2 + n T−2∑ i5k ( 1√ i − 1√ n− 1 )2 niN pri ~emu va`i (19) nk − n+ 1 2 ≥ 0N (14) ni ≥ 0N za k + 1 ≤ i ≤ n− 2. Ako je nk ≥ T+)2 i ni ≥ 0, za k+1 ≤ i ≤ n−2, tada je x = ∑T−2 i5k ( )√ i − )√ T−))ni ≥ ( )√ k − )√ T−)) T+) 2 > ( )√ k − )√ T−)) T 2 . U prvom slu~aju upore|ivali smo funkciju γ) = γ¯) sa funkcijom g(x) = −x2 + nx ( )√ k − )√ T−) ) . I sada }emo sli~no do}i do maksimalne vrednosti. Funkcija g(x), koja je jednaka g(x) = T 2 4 ( )√ k − )√ T−) )2 −( x− T 2 ( )√ k − )√ T−) ))2 , pod uslovom da je x ≥ ( )√ k − )√ T−)) T+) 2 , posti`emaksimalnu vrednost u ta~ki x∗ = ( )√ k − )√ T−)) T+) 2 . Ova ta~ka x∗ se dobija za nk = T+)2 N ni = 0 za k + 1 ≤ i ≤ n − 2. Po{to je γ) = γ¯) ≤ g na k , i γ¯)(x∗) = g(x∗), vidimo da i funkcija γ) posti`e maksimalnu vrednost γ¯ ∗ ) u ta~ki a ∗ 2G2 koja je odre|ena sa nk = T+) 2 N ni = 0 za k + 1 ≤ i ≤ n− 2 i nT−) = T−)2 . Time smo dokazali tvr|ewe: Lema 5.3. Funkcija γ), za koju va`e uslovi (2),(9)i (19), posti`e maksimalnu vrednost ( 1√ k − 1√ n− 1 )2 n2 − 1 4 N u ta~ki a∗2G2 ∈ k odre|enoj sa (T+)2 N 0N ...N 0N T−)2 ). 47 5.3. DRUGI SLU^AJ: T JE NEPARAN BROJ Zasad smo obradili slu~aj kada je najve}i stepen ~vorova ∆(G) = n − 1, i dobili jedinstvenu maksimalnu vrednost funkcije γ). Podslu~aj 2u. Neka je najve}i stepen ~vorova m = ∆(G) < n − 1. U tom slu~aju }e dokaz biti sli~an dokazu prvog podslu~aja (2t), pa ga mo`emo izostaviti. Maksimalna vrednost funkcije γ) je γ¯m) = ( 1√ k − 1√ m )2 n2 − 1 4 . Po{to je γ¯∗) > γ¯ m ) zakqu~ujemo da je γ¯ ∗ ) maksimalna vrednost, koja se posti`e u ta~ki a∗2G1 ili u ta~ki a ∗ 2G2 . Pokazali smo da funkcija γ) posti`e maksimalnu vrednost u ta~kama a ∗ 2G1 odnosno a∗2G2 . Daqim razmatrawem vidimo da funkcija γ2 posti`e maksimalnu vrednost, koja je jednaka 0, u ta~kil ∗2G1 ilil ∗ 2G2 koja je odre|ena sa yk,k = (T−k−))(T−)) 4 ili yk,k = (T−k−))(T+)) 4 dok su svi ostali yi,j = 0 (setimo se sa po~etka razmatrawa problema da je y∗i,j = 0 za i ̸= j i y∗i,i = (T−i−))T ∗ i 2 ). Primenimo sada jednakosti (8) kako bismo dobili xi,j . U prvom slu~aju je nk = T−) 2 i nT−) = T+)2 a yk,k = (T−k−))(T−)) 4 (svi ostali su jed- naki 0), te su: xk,k = ( Tk 2 )−yk,k = Tk(Tk−))2 − (T−k−))(T−))4 = (T−))(T−+)0 − (T−k−))(T−))4 = (T−))(2k−T−)) 0 ; xk,T−) = nknT−) − yk,T−) = (T−))2 (T+))2 − 0 = T 2−) 4 ; xT−),T−) =( Tn−1 2 ) − yT−),T−) = Tn−1(Tn−1−))2 − 0 = (T+))(T−))0 = (T2−))0 , i svi ostali xi,jN xi,i jednaki nuli. U drugom slu~aju je nk = T+) 2 i nT−) = T−)2 a yk,k = (T−k−))(T+)) 4 (svi ostali su jednaki 0), te su: xk,k = Tk(Tk−)) 2 − (T−k−))(T+)) 4 = (T+))(T−)) 0 − (T−k−))(T+)) 4 = (T+))(2k−T+)) 0 ; xk,T−) = nknT−) − yk,T−) = (T+))2 (T−))2 − 0 = T 2−) 4 ; xT−),T−) =( Tn−1 2 )− yT−),T−) = Tn−1(Tn−1−))2 − 0 = (T−))(T−+)0 , i svi ostali xi,jN xi,i jednaki nuli. Vode}i ra~una o celobrojnosti promenqivih, dolazimo do slede}eg tvr|ewa: Teorema 5.2. Ako je ukupan broj ~vorova n neparan broj, i ako je graf G ∈ G(kN n) tada je e(G) ≥ n 2 − ( 1√ k − 1√ n− 1 )2 n2 − 1 8 . Jednakost va`i, za n ≡ 1(mod 4), ili za n ≡ 3(mod 4) i k paran broj, na bilo kom grafu G ∈ GT,(T−))/2,k za koji je nk = T−)2 N nT−) = T+)2 N xk,k = (T−))(2k−T−))0 N xk,T−) = T2−) 4 , xT−),T−) = T 2−) 0 i svi ostali xi,jN xi,i i ni su jednaki nuli. Ako je n ≡ 3(mod 4), ili ako je n ≡ 1(mod 4) i k paran broj, tada va`i jednakost na bilo kom grafu G ∈ GT,(T+))/2,k za koji je nk = T+)2 N nT−) = T−)2 N xk,k = (T+))(2k−T+))0 N xk,T−) = T 2−) 4 , xT−),T−) = (T−))(T−+) 0 i svi ostali xi,jN xi,i i ni su jednaki nuli. Na slici 5.4. vidimo ekstremni graf G ∈ G)+,6,0 gde je, s obzirom da je 13 ≡ 1(mod 4), n0 = 6N n)2 = 7N x0,0 = 3N x0,)2 = 42 i x)2,)2 = 21. Na slici 5.5. vidimo ekstremni graf G ∈ G)+,7,0 gde je, s obzirom da je 13 ≡ 1(mod 4) i k = 8 paran broj, n0 = 7N n)2 = 6N x0,0 = 7N x0,)2 = 42 i x)2,)2 = 15. 48 5.3. DRUGI SLU^AJ: T JE NEPARAN BROJ Slika 5.4. Graf G ∈ G)+,6,0. Slika 5.5. Graf G ∈ G)+,7,0. Na slici 5.6. vidimo ekstremni graf G ∈ G)),5,6 gde je, s obzirom da je 11 ≡ 3(mod 4) i k = 6 paran broj, n6 = 5N n)( = 6N x6,6 = 0N x6,)( = 30 i x)(,)( = 15. Na slici 5.7. vidimo ekstremni graf G ∈ G)),6,6 gde je, s obzirom da je 11 ≡ 3(mod 4), n6 = 6N n)( = 5N x6,6 = 3N x6,)( = 30 i x)(,)( = 10. Slika 5.6. Graf G ∈ G)),5,6. Slika 5.7. Graf G ∈ G)),6,6. Na slici 5.8. vidimo ekstremni graf G ∈ G)+,6,7 gde je, s obzirom da je 13 ≡ 1(mod 4), n7 = 6N n)2 = 7N x7,7 = 0N x7,)2 = 42 i x)2,)2 = 21. Na slici 5.9. vidimo ekstremni graf G ∈ G)),6,7 gde je, s obzirom da je 11 ≡ 3(mod 4), n7 = 6N n)( = 5N x7,7 = 6N x7,)( = 30 i x)(,)( = 10. Primetimo da, ako je n ≡ 1(mod 4), ili ako je n ≡ 3(mod 4) i k paran broj, to je p = T−) 2 = ⌊T 2 ⌋. Tako|e, ako je n ≡ 3(mod 4), ili ako je n ≡ 1(mod 4) i k paran broj, to je p = T+) 2 = ⌈T 2 ⌉. Ovim smo, u slu~aju kada je n neparan broj, potvrdili hipotezu. 49 5.4. TRE]I SLU^AJ: T ≡ 2(mod 4) I k PARAN BROJ Slika 5.8. Graf G ∈ G)+,6,7. Slika 5.9. Graf G ∈ G)),6,7. 5.4 Tre}i slu~aj: n ≡ 2(mod 4) i k paran broj Za n ≡ 2(mod 4) je T 2 neparan broj te je, s obzirom na parnost broja k, u ovom slu~aju k ≥ T 2 +1. Kao i ranije, razmatra}emo dva podslu~aja: prvi podslu~aj (3t) kada je∆(G) = n−1, i drugi podslu~aj (3u) kada je∆(G) < n−1. Daqe, podeli}emo prvi podslu~aj (3t) u tri nova podslu~aja: prvi(3t)) kada je nk ≤ nP2 − 1, drugi (3t2) kada je nk = nP2 i tre}i (3t+) kada je nk ≥ nP2 + 1. Podslu~aj 3t): U ovom podslu~aju je, uz n ≡ 2(mod 4) i k paran broj, jo{ i nk ≤ nP2− 1. Razmatramo problem c +G1 : max − ( T−2∑ i5k ( 1√ i − 1√ n− 1 ) ni )2 + n T−2∑ i5k ( 1√ i − 1√ n− 1 )2 niN pri ~emu va`i (13′) −nk + n 2 − 1 ≥ 0N (14) ni ≥ 0N za k ≤ i ≤ n− 2. Ovaj problem c +G1 se sli~no re{ava kao problem c 2 G1 . Dopustiva ta~ka a je ta~ka maksimuma problema c +G1 ako postoje nenegativni brojevi µ(, λi za k ≤ i ≤ n− 2, takvi da za funkciju Ψ definisanu sa Ψ = γ¯) + µ( ( −nk + n 2 − 1 ) + T−2∑ i5k λini = − ( T−2∑ i5k ( 1√ i − 1√ n− 1 ) ni )2 + n T−2∑ i5k ( 1√ i − 1√ n− 1 )2 ni + µ( ( −nk + n 2 − 1 ) + T−2∑ i5k λini 50 5.4. TRE]I SLU^AJ: T ≡ 2(mod 4) I k PARAN BROJ va`i SΨPSni = 0 za k ≤ i ≤ n− 2, odnosno: (15) −2 ( 1√ k − 1√ n− 1 ) T−2∑ j5k ( 1√ j − 1√ n− 1 ) nj +n ( 1√ k − 1√ n− 1 )2 −µ(+λk = 0N (16) − 2 ( 1√ i − 1√ n− 1 ) T−2∑ j5k ( 1√ j − 1√ n− 1 ) nj +n ( 1√ i − 1√ n− 1 )2 +λi = 0N za k + 1 ≤ i ≤ n− 2N i (17′) µ( ( −nk + n 2 − 1 ) = 0N (18) λini = 0 za k ≤ i ≤ n− 2. Va`i slede}e tvr|ewe: Lema 5.4. Ta~kaa ∗ +G1 odre|ena sa (T 2 − 1N 0N . . . N 0) je ta~ka maksimuma problema c +G1 . Dokaz. Za ovu ta~ku su ispuweni uslovi (13') i (14) te je ona dopustiva ta~ka. Iz (18), po{to je nk = T 2 − 1 ̸= 0, vidimo da je λ∗k = 0 i samim tim se iz (15) dobija: µ∗( = −2 ( 1√ k − 1√ n− 1 )(n 2 − 1 )( 1√ k − 1√ n− 1 ) + n ( 1√ k − 1√ n− 1 )2 = 2 ( 1√ k − 1√ n− 1 )2 . Tako|e iz (16), za k + 1 ≤ i ≤ n− 2, va`i: λ∗i = ( 1√ i − 1√ n− 1 )( 2 ( 1√ k − 1√ n− 1 )(n 2 − 1 ) − n ( 1√ i − 1√ n− 1 )) = ( 1√ i − 1√ n− 1 )( n− 2√ k − n√ i + 2√ n− 1 ) . Funkcije )√ i i ( )√ j − )√ j+) ) su opadaju}e te va`i: n− 2√ k − n√ i + 2√ n− 1 ≥ n− 2√ k − n√ k + 1 + 2√ n− 1 = (n− 2) ( 1√ k − 1√ k + 1 ) − 2 ( 1√ k + 1 − 1√ n− 1 ) = (n− 2) ( 1√ k − 1√ k + 1 ) − 2 T−2∑ j5k+) ( 1√ j − 1√ j + 1 ) ≥ (n− 2) ( 1√ k − 1√ k + 1 ) − 2(n− k − 2) ( 1√ k − 1√ k + 1 ) = (−n+ 2k + 2) ( 1√ k − 1√ k + 1 ) ≥ 0N 51 5.4. TRE]I SLU^AJ: T ≡ 2(mod 4) I k PARAN BROJ s obzirom da je k ≥ T 2 − 1. Vidimo da su µ∗( ≥ 0 i λ∗i ≥ 0, za k + 1 ≤ i ≤ n − 2. S obzirom da dopustiva ta~ka a ∗ +G1 ispuwava Kuhn–Tucker -ove uslove ona je i ta~ka maksimuma problema c +G1 , {to je i trebalo dokazati. 2 Maksimalna vrednost funkcije γ¯), odnosno funkcije γ), je γˆ∗) = ( 1√ k − 1√ n− 1 )2( n2 4 − 1 ) N i ona se posti`e u ta~ki a∗+G1 ∈ k odre|enoj sa (T2 − 1N 0N ...N 0N T2 + 1). Podslu~aj 3t2: U ovompodslu~aju je, uzn ≡ 2(mod 4) i k paran broj, jo{ink = nP2. Funkcija γ), za koju va`e uslovi (2) i (9), posti`e maksimalnu vrednost kada je nk = T 2 N nT−) = T2 i svi ostali ni = 0. Me|utim, u tom slu~aju (s obzirom da je yk,k = (T−k−))Tk 2 ) je xk,k = Tk(Tk−)) 2 − yk,k = T(T−2)0 − (T−k−))T4 = T4 (k − T2 ), {to nije ceo broj. Da bi smo do{li do grafovskog re{ewa mora da postoji bar jedno ni koje }e biti pozitivno za k + 1 ≤ i ≤ n− 2. Razmatramo problem c +G2 : max − ( T−2∑ i5k ( 1√ i − 1√ n− 1 ) ni )2 + n T−2∑ i5k ( 1√ i − 1√ n− 1 )2 niN pri ~emu va`i (20) nk = n 2 N (21) ni ≥ 1N za najmawe jedno i ∈ {k + 1N ...N n− 2}N (22) ni ≥ 0N za k + 1 ≤ i ≤ n− 2. Za nk = T 2 dobijamo, za k + 1 ≤ i ≤ n− 2: Sγ¯) Sni = −2 ( 1√ i − 1√ n− 1 ) T−2∑ j5k ( 1√ j − 1√ n− 1 ) nj + n ( 1√ i − 1√ n− 1 )2 = ( − ( 1√ k − 1√ n− 1 ) n− 2 T−2∑ j5k+) ( 1√ j − 1√ n− 1 ) nj + n ( 1√ i − 1√ n− 1 )) · ( 1√ i − 1√ n− 1 ) Za nk = T 2 , ni ≥ 0 i bar jedno ni ≥ 1, lako je videti da je Sγ¯)PSni < 0, za k + 1 ≤ i ≤ n − 2. Tada, funkcija γ¯) posti`e maksimalnu vrednost kada se uzme upravo jedno nj = 1 i svi ostali ni = 0 za k + 1 ≤ i ≤ n − 2N i ̸= j. Ozna~imo sa γ¯j) maksimalnu vrednost funkcije γ¯), odnosno funkcije γ) na k , kada je nj = 1 i svi ostali ni = 0. Po{to je tada nT−) = T2 − 1, imamo da je γ¯j) = ( 1√ k − 1√ n− 1 )2 n 2 (n 2 − 1 ) + ( 1√ j − 1√ n− 1 )2 (n 2 − 1 ) + ( 1√ k − 1√ j )2 n 2 . 52 5.4. TRE]I SLU^AJ: T ≡ 2(mod 4) I k PARAN BROJ Uporedimo funkcije γˆ∗) i γ¯ j ) za k + 1 ≤ j ≤ n− 2. γˆ∗) − γ¯j) = ( 1√ k − 1√ n− 1 )2( n2 4 − 1 ) − ( 1√ k − 1√ n− 1 )2 n 2 (n 2 − 1 ) − ( 1√ j − 1√ n− 1 )2 (n 2 − 1 ) − ( 1√ k − 1√ j )2 n 2 = [( 1√ k − 1√ n− 1 )2 − ( 1√ j − 1√ n− 1 )2](n 2 − 1 ) − ( 1√ k − 1√ j )2 n 2 = ( 1√ k − 1√ j )( − 1√ k + n− 1√ j − n− 2√ n− 1 ) . Po{to je )√ j opadaju}a funkcija i k ≥ T 2 − 1, imamo da je − )√ k + T−)√ j − T−2√ T−) ≥ − )√ k + T−)√ T−2 − T−2√T−) ≥ − )√n 2 −) + T−)√ T−2 − T−2√T−) = T−)− √ 2√ T−2 − T−2√T−) . Posledwi izraz }e biti pozitivan kada je (n− 1−√2)2(n− 1) > (n− 2)+ ⇐⇒ (n2 + 1 + 2 − 2n − 2√2n + 2√2)(n− 1) > n+ − 6n2 + 12n − 8 ⇐⇒ (−1− 2− 2√2 + 6)n2 + (2 + 2 √ 2 + 3 + 2 √ 2− 12)n+8−3−2√2 > 0⇐⇒ (3− 2√2)n2+(4√2− 7)n+5− 2 √ 2 > 0. Proverom za n = 5 i n = 6 pokazuje se da je posledwi kvadratni izraz u nejednakosti prvo negativan pa pozitivan, te mo`emo zakqu~iti da je nejednakost ispuwena za n ≥ 6 (za n ≤ 5 ne postoji n ≡ 2(mod 4) i k paran broj ). Zakqu~ujemo da je maksimalna vrednost u slu~aju (t2) mawa od γˆ ∗ ) = ( )√ k − )√ T−)) 2(T 2−4 4 ). Podslu~aj 3t+: U ovom podslu~aju je, uz n ≡ 2(mod 4) i k paran broj, jo{ i nk ≥ T2 + 1. Razmatramo problem c +G3 : max − ( T−2∑ i5k ( 1√ i − 1√ n− 1 ) ni )2 + n T−2∑ i5k ( 1√ i − 1√ n− 1 )2 niN pri ~emu va`i (23) nk − n 2 − 1 ≥ 0N (14) ni ≥ 0N za k ≤ i ≤ n− 2. Ovaj problem je sli~an problemu c 2G2 . Ako je nk ≥ T2 +1 i ni ≥ 0, za k+1 ≤ i ≤ n−2, tada jex =∑T−2i5k ( )√i− )√T−))ni ≥ ( )√k− )√T−))(T2+1) > ( )√k− )√T−))T2 . Funkcija g(x) = −x2 + nx ( )√ k − )√ T−) ) = T 2 4 ( )√ k − )√ T−) )2 − ( x− T 2 ( )√ k − )√ T−) ))2 , pod uslovom da je x ≥ ( )√ k − )√ T−))( T 2 + 1), posti`e maksimalnu vrednost u ta~ki x∗ = ( )√ k − )√ T−))( T 2 + 1). Ova ta~ka x∗ se dobija za nk = T2 + 1N ni = 0 za k + 1 ≤ i ≤ n − 2. Po{to je γ) = γ¯) ≤ g na k , i γ¯)(x∗) = g(x∗), vidimo da i funkcija γ) posti`e maksimalnu vrednost γ¯ ∗ ) u ta~ki a ∗ +G3 koja je odrte|ena sa nk = T 2 +1N ni = 0 za k+1 ≤ i ≤ n−2 i nT−) = T2 −1. Time smo dokazali tvr|ewe: 53 5.4. TRE]I SLU^AJ: T ≡ 2(mod 4) I k PARAN BROJ Lema 5.5. Funkcija γ), za koju su ispuweni uslovi (2),(9) i (23) posti`e maksimalnu vrednost γˆ∗) = ( 1√ k − 1√ n− 1 )2( n2 4 − 1 ) . u ta~ki a∗+G3 . Podslu~aj 3u. Neka je najvi{i stepen ~vorova m = ∆(G) < n − 1. U tom slu~aju je dokaz sli~an dokazu podslu~aju 3t te ga izostavqamo. Maksimalna vrednost funkcije γ) je γˆm) = ( 1√ k − 1√ m )2( n2 4 − 1 ) . Po{to je γˆ∗) > γˆ m ) zakqu~ujemo da je γˆ ∗ ) maksimalna vrednost, koja se posti`e u ta~ki a∗+G1 ili u ta~ki a ∗ +G3 . Dokazali smo da funkcija γ) posti`e maksimalnu vrednost u bilo kojoj ta~ki a∗+G1 ili a ∗ +G3 . Daqim razmatrawem vidimo da funkcija γ2 posti`e maksimalnu vrednost, koja je jednaka 0, u ta~kil ∗+G1 ilil ∗ +G3 koja je odre|ena sa yk,k = (T−k−))(T−2) 4 ili yk,k = (T−k−))(T+2) 4 dok su svi ostali yi,j = 0 (setimo se sa po~etka razmatrawa problema da je y∗i,j = 0 za i ̸= j i y∗i,i = (T−i−))T ∗ i 2 ). Primenimo sada jednakosti (8) kako bismo dobili xi,j . U prvom slu~aju je nk = T 2 − 1 i nT−) = T2 + 1 a yk,k = (T−k−))(T−2)4 (svi ostali su jednaki 0), te su: xk,k = ( Tk 2 ) − yk,k = Tk(Tk−))2 − (T−k−))(T−2)4 = (T−2)(T−4)0 − (T−k−))(T−2) 4 = (T−2)(2k−T−2) 0 ; xk,T−) = nknT−) − yk,T−) = (T2 − 1)(T2 + 1)− 0 = T 2−4 4 ; xT−),T−) = ( Tn−1 2 )− yT−),T−) = Tn−1(Tn−1−))2 − 0 = T(T+2)0 , i svi ostali xi,jN xi,i jed- naki su nuli. U drugom slu~aju je nk = T 2 +1 i nT−) = T2−1 a yk,k = (T−k−))(T+2)4 (svi ostali su jednaki 0), te su: xk,k = Tk(Tk−)) 2 − (T−k−))(T+2) 4 = (T+2)T 0 − (T−k−))(T+2) 4 = (T+2)(2k−T+2) 0 ; xk,T−) = nknT−) − yk,T−) = (T2 + 1)(T2 − 1) − 0 = T 2−4 4 ; xT−),T−) =( Tn−1 2 )−yT−),T−) = Tn−1(Tn−1−))2 −0 = (T−2)(T−4)0 , i svi ostali xi,jN xi,i jednaki su nuli. Vode}i ra~una o celobrojnosti promenqivih, dolazimo do slede}eg tvr|ewa: Teorema 5.3. Ako je n ≡ 2(mod 4), k paran, (k ≥ T 2 + 1), i ako G ∈ G(kN n), tada e(G) ≥ n 2 − 1 2 ( 1√ k − 1√ n− 1 )2 (n2 − 4) 4 . Jednakost se posti`e na grafovimaG ∈ GT,n+2 2 ,k za koje je nk = T 2 +1, nT−) = T2−1, xk,k = ) 2 (T 2 + 1)(k− T 2 + 1), xk,T−) = T 2−4 4 , xT−),T−) = (T2 − 1)(T2 − 2)P2 i svi ostali xi,j , xi,i i ni su jednaki 0 ili na grafovimaG ∈ GT,n−2 2 ,k za koje je nk = T 2 − 1, nT−) = T 2 + 1N xk,k = (T−2)(2k−T−2) 0 N xk,T−) = T 2−4 4 N xT−),T−) = T(T+2) 0 i svi ostali xi,j , xi,i i ni su jednaki 0. U prvom slu~aju je p = T+2 2 , a u drugom p = T−2 2 , {to se poklapa sa hipotezom. 54 5.4. TRE]I SLU^AJ: T ≡ 2(mod 4) I k PARAN BROJ Na slici 5.10. vidimo ekstremni graf G ∈ G)(,6,6, gde je n6 = 6N n1 = 4N x6,6 = 6N x6,1 = 24 i x1,1 = 6. Na slici 5.11. vidimo ekstremni graf G ∈ G)(,4,6, gde je n6 = 4N n1 = 6N x6,6 = 0N x6,1 = 24 i x1,1 = 15. Slika 5.10. Graf G ∈ G)(,6,6. Slika 5.11. Graf G ∈ G)(,4,6. 55 Glava 6 Minimalna vrednost Randi}evog indeksa za k ≤ n2 Kao {to je pomenuto u prethodnoj glavi, u ovoj glavi }emo dokazati hipotezu 5.2, koju su postavili M. Aouchiche i P. Hansen 2007. godine u radu [1]. Podse}amo ~itaoce da su sve hipoteze 5.1., 5.2. i 5.3. iste u slu~aju kada je k ≤ T 2 . Time }e u potpunosti biti re{en problem nala`ewa minimalne vrednost Randi}evog indeksa na skupu prostih grafova sa n ~vorova pri ~emu je minimalni stepen ~vorova k. Dokaza}emo slede}e tvr|ewe. Teorema 6.1. Ako je k ≤ T 2 , i graf G pripada skupu G(kN n), tada je e(G) ≥ n 2 − 1 2 ( 1√ k − 1√ n− 1 )2 (n− k)k. Jednakost va`i ako i samo ako je G = K∗k,T−k pri ~emu je: nk = n − kN nT−) = kN xk,T−) = (n−k)kN xT−),T−) = k(k−1)P2, i svi ostali xi,jN xi,i i ni su jednaki nuli. Pre nego {to pre|emo na dokaz navedene teoreme definisa}emo problem i do- kazati jednu lemu. Problem c odre|ivawa minimuma min{e(G) : G ∈ G(kN n)} mo`emo predstaviti u slede}em obliku: min ∑ k≤i≤j≤T−) xi,j√ ij pri ~emu, uz k ≤ T 2 , va`i: (1) 2xk,k + xk,k+) + xk,k+2 + · · ·+ xk,T−) = knkN xk,k+) + 2xk+),k+) + xk+),k+2 + · · ·+ xk+),T−) = (k + 1)nk+)N xk,k+2 + xk+),k+2 + 2xk+2,k+2 + · · ·+ xk+2,T−) = (k + 2)nk+2N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xk,T−) + xk+),T−) + xk+2,T−) + · · ·+ 2xT−),T−) = (n− 1)nT−)N 56 6. MINIMALNA VREDNOST RANDI]EVOG INDEKSA ZA k ≤ n 2 (2) nk + nk+) + . . . N nT−) = nN (3) xi,j ≤ ninjN za k ≤ i < j ≤ n− 1N (4) xi,i ≤ ( ni 2 ) N za k ≤ i ≤ n− 1N (5) xi,jN ni nenegativni celi brojevi za k ≤ i ≤ j ≤ n− 1. Kao {to je ranije navedeno, na osnovu jednakosti (1) i (2), Randi}ev indeks e(G) = ∑ k≤i≤j≤T−) xi;j√ ij mo`emo predstaviti i u slede}em obliku: (6) e(G) = n 2 − 1 2 ∑ k≤i≤j≤T−) ( 1√ i − 1√ j )2 xi,j. I na kraju, kada defini{emo novu funkciju: (7) γ = ∑ k≤i k + 2 i n ≡ 3(mod 4), i ako G ∈ G(kNmN n), tada je e(G) ≥ n 2 − ( 1√ k − 1√ m )2 (n+ 1)(n− 3) 8 − ( 1√ k − 1√ m− 1 )2 (n+ 1) 4 − ( 1√ m− 1 − 1√ m )2 (−n+ 2m− 3) 4 . Ova vrednost se posti`e na grafovima familije G(n+1 2 ,(,...,(,),n−3 2 ), za koje je nk = T+) 2 N ni = 0, zak+1 ≤ i ≤ m−2,nm−) = 1N nm = T−+2 , xk,k = (T+))(−T+2k+))0 N xk,m−) = T+) 2 , xk,m = (T+))(T−+) 4 N xm−),m = −T+2m−+2 N xm,m = (T−+)(−T+2m−+) 0 + T−m 2 i svi ostali xi,j su jednaki nuli. 77 7.2. SLU^AJ KADA SU k,m I T NEPARNI BROJEVI Na slici 7.16. predstavqen je graf G ∈ G(9N 13N 15), odnosno graf G ∈ G(0,(,(,),6), na kome se posti`e minimalna vrednost Randi}evog indeksa, pod uslovi- ma teoreme 7.6. Naglasimo da je x1,1 = 8N x1,)2 = 8, x1,)+ = 48, x)2,)+ = 4 i x)+,,)+ = 13. Slika 7.16. Graf G ∈ G(0,(,(,),6). Razmatra}emo dva glavna slu~aja: 1. np = 1 i 2. np ≥ 2, za neko p, k + 1 ≤ p ≤ m− 1. Odredi}emo maksimalnu vrednost ili gorwu granicu funkcija γ) i γ2 primenom relevantnih ograni~ewa u oba slu~aja. U prvom pododeqku na}i }emo maksimalnu vrednost funkcije γ) u prvom slu~aju 1. Zatim }emo odrediti mak- simalnu vrednost funkcije γ2 u oba slu~aja. U narednom pododeqku, odredi}emo gorwu granicu funkcije γ) u drugom slu~aju 2. Na kraju }emo prvo dokazati teoremu 7.4., pa zajedno druge dve teoreme. Ideja dokaza je da poka`emo da grafovi na kojima se posti`e ekstremna vred- nost ne mogu imati dva ~vora stepena p, za k + 1 ≤ p ≤ m − 1, i ne mogu imati jedan ~vor stepena p za k + 2 ≤ p ≤ m− 2. Samim tim, dolazimo do grafova koji imaju jedan ~vor stepena p za koji funkcija γ)+ γ2 posti`e maksimalnu vrednost. U celokupnom radu na daqe va`i: T+) 2 ≤ k < p < m ≤ n− 2. 7.2.1 Maksimalna vrednost funkcije γ) kada je np = 1 Uovomslu~aju odredi}emomaksimumfunkcije γ) pri~emu va`e uslovi (2)N (10)N (5′) i np = 1 za neko p, k+1 ≤ p ≤ m−1. Ozna~imo sa (t) uslov )√k+ )√m− 2√p ≥ 0 i sa (u) uslov )√ k + )√ m − 2√ p ≤ 0. Samim tim, razlikujemo dva podslu~aja: podslu~aj (t) ako je ispuwen uslov (t), i podslu~aj (u) kada je ispuwen uslov (u). Daqe, podelimo podslu~aj (t) u nova dva podslu~aja: podslu~aj (t)), kada je nk ≤ T−)2 , i podslu~aj (t2), kada je nk ≥ T+)2 . Tako|e, i podslu~aj (u) podelimo u nova dva 78 7.2. SLU^AJ KADA SU k,m I T NEPARNI BROJEVI podslu~aja: podslu~aj (u)), kada je nk ≤ T−+2 , i podslu~aj (u2), kada je nk ≥ T−)2 . Odredimo maksimalnu vrednost funkcije γ) u svakom podslu~aju i, nakon toga, maksimum funkcije γ) u celokupnom slu~aju. Podslu~aj t). U ovom podslu~aju odredi}emo maksimalnu vrednost funkcije γ) kada su ispuweni uslovi )√ k + )√ m − 2√ p ≥ 0 i nk ≤ T−)2 . Razmatramo problem c G1 : max− ( m−)∑ j5k ( 1√ j − 1√ m ) nj )2 + n m−)∑ j5k ( 1√ j − 1√ m )2 nj pri ~emu va`i np = 1N −nk + n− 1 2 ≥ 0N ni ≥ 0N za k ≤ i ≤ m− 1N i ̸= p. Ozna~imo saa dopustivu ta~ku (nkN . . . N nm−)) problema c G1 . Primenimo Kuhn– Tucker -ovu teoremu 2.2. na problem c G1 . Po toj teoremi, dopustiva ta~ka a je ta~ka maksimuma ovog problema ako postoje nenegativni brojevi µk, λi, za k ≤ i ≤ m− 1N i ̸= p, takvi da va`e Kuhn–Tucker -ovi uslovi: (13) −2 ( m−)∑ j5k ( 1√ j − 1√ m ) nj )( 1√ k − 1√ m ) +n ( 1√ k − 1√ m )2 −µk+λk = 0N (14) − 2 ( m−)∑ j5k ( 1√ j − 1√ m ) nj )( 1√ i − 1√ m ) + n ( 1√ i − 1√ m )2 + λi = 0N za k + 1 ≤ i ≤ m− 1N i ̸= pN i (15) µk ( −nk + n− 1 2 ) = 0N (16) λini = 0N za k ≤ i ≤ m− 1N i ̸= p. Lema 7.1. Ta~kaa ∗ G1 , odre|ena sa nk = T−) 2 , np = 1 i ni = 0, za k+1 ≤ i ≤ m−1N i ̸= p, je ta~ka maksimuma problema c G1 . Dokaz. Lako se vidi da je navedena ta~ka dopustiva. U ovoj ta~ki je λ∗k = 0, po{to je δ(G) = k i iz (16), pa na osnovu (13) bi}e: µ∗k = ( 1√ k − 1√ m )( −2 ( 1√ k − 1√ m ) n− 1 2 − 2 ( 1√ p − 1√ m ) + n ( 1√ k − 1√ m )) = ( 1√ k − 1√ m )( 1√ k − 2√ p + 1√ m ) . 79 7.2. SLU^AJ KADA SU k,m I T NEPARNI BROJEVI Na osnovu uslova podslu~aja (a) )√ k + )√ m − 2√ p ≥ 0, je µ∗k ≥ 0. Iz jednakosti (14), k + 1 ≤ i ≤ m− 1N i ̸= p, va`i: λ∗i = ( 1√ i − 1√ m )( 2 ( 1√ k − 1√ m ) n− 1 2 + 2 ( 1√ p − 1√ m ) − n ( 1√ i − 1√ m )) = ( 1√ i − 1√ m )( n− 1√ k + 2√ p − n√ i − 1√ m ) . Po{to su )√ i i )√ j − )√ j+) opadaju}e funkcije, imamo da je T−)√ k + 2√ p − T√ i − )√ m ≥ T−)√ k + 2√ p − T√ k+) − )√ m ≥ (n−1)( )√ k − )√ k+) )−( )√ k+) − )√ p ) = (n−1)( )√ k − )√ k+) )−∑p−)j5k+)( )√j− )√ j+) ) ≥ (n− 1)( )√ k − )√ k+) )− (p− k− 1)( )√ k − )√ k+) ) = (n− p+ k)( )√ k − )√ k+) ) ≥ 0, i otud λ∗i ≥ 0. Na osnovu svega, ta~ka a∗G1 ispuwava Kuhn–Tucker -ove uslove te je i ta~ka maksimuma. 2 Zakqu~ak mo`emo predstaviti slede}im tvr|ewem. Lema 7.2. Maksimalna vrednost funkcije γ¯) i samim tim funkcije γ) je γ)(G1) = ( 1√ k − 1√ m )2 (n− 1)2 4 + ( 1√ k − 1√ p )2 n− 1 2 + ( 1√ p − 1√ m )2 n− 1 2 N i ona se posti`e u ta~ki a∗G1 ∈ k odre|enoj sa (T−)2 N 0N . . . N 0N 1N 0N . . . N 0N T−)2 ). Podslu~aj t2. U ovom podslu~aju odredi}emo maksimalnu vrednost funkcije γ) kada su ispuweni uslovi )√ k + )√ m − 2√ p ≥ 0 i nk ≥ T+)2 . Razmatramo problem c G2 : max− ( m−)∑ j5k ( 1√ j − 1√ m ) nj )2 + n m−)∑ j5k ( 1√ j − 1√ m )2 nj pri ~emu va`i np = 1N nk − n+ 1 2 ≥ 0N ni ≥ 0N za k + 1 ≤ i ≤ m− 1N i ̸= p. Za k ≤ i ≤ m− 1, dobijamo : Sγ¯)PSni = −2 ( m−)∑ j5k ( 1√ j − 1√ m ) nj )( 1√ i − 1√ m ) + n ( 1√ i − 1√ m )2 =( −2 ( 1√ k − 1√ m ) nk − 2 m−)∑ j5k+) ( 1√ j − 1√ m ) nj + n ( 1√ i − 1√ m ))( 1√ i − 1√ m ) < ( − ( 1√ k − 1√ m ) (n+ 1) + n ( 1√ i − 1√ m ))( 1√ i − 1√ m ) < 0N po{to je nk ≥ T+)2 i ni ≥ 0. Kako je Sγ¯)PSni ≤ 0, za k ≤ i ≤ m − 1, funkcija γ¯) posti`e maksimalnu vrednost za nk = T+) 2 N np = 1 i ni = 0, za k + 1 ≤ i ≤ m − 1N i ̸= p. Mo`emo primetiti da se u ovom podslu~aju ne koristi uslov (t). Zakqu~ak mo`emo uobli~iti slede}im tvr|ewem. 80 7.2. SLU^AJ KADA SU k,m I T NEPARNI BROJEVI Lema 7.3. Maksimalna vrednost funkcije γ¯) i samim tim funkcije γ) u podslu~aju (t2) je γ)(G2) = ( 1√ k − 1√ m )2 (n+ 1)(n− 3) 4 + ( 1√ k − 1√ p )2 n+ 1 2 + ( 1√ p − 1√ m )2 n− 3 2 N i ona se posti`e u ta~kia∗G2 ∈ k odre|enoj sa (T+)2 N 0N . . . N 0N 1N 0N . . . N 0N T−+2 ). Podslu~aj u). U ovom podslu~aju odredi}emo maksimalnu vrednost funkcije γ) kada su ispuweni uslovi )√ k + )√ m − 2√ p ≤ 0 and nk ≤ T−+2 . Razmatramo problem c b1 : max− ( m−)∑ j5k ( 1√ j − 1√ m ) nj )2 + n m−)∑ j5k ( 1√ j − 1√ m )2 nj pri ~emu va`i np = 1N −nk + n− 3 2 ≥ 0N ni ≥ 0N za k ≤ i ≤ m− 1N i ̸= p. Po teoremi 2.2., dopustiva ta~ka (nkN . . . N nm−)) je ta~ka maksimuma navedenog problema ako postoje nenegativni brojevi µk, λi, za k ≤ i ≤ m− 1N i ̸= p, takvi da va`e Kuhn–Tucker -ovi uslovi: (13) −2 ( m−)∑ j5k ( 1√ j − 1√ m ) nj )( 1√ k − 1√ m ) +n ( 1√ k − 1√ m )2 −µk+λk = 0N (14) − 2 ( m−)∑ j5k ( 1√ j − 1√ m ) nj )( 1√ i − 1√ m ) + n ( 1√ i − 1√ m )2 + λi = 0N za k + 1 ≤ i ≤ m− 1N i ̸= pN i (17) µk ( −nk + n− 3 2 ) = 0N (16) λini = 0N za k ≤ i ≤ m− 1N i ̸= p. Lema 7.4. Ta~ka a ∗ b1 odre|ena sa nk = T−+ 2 , np = 1 and ni = 0, za k + 1 ≤ i ≤ m− 1N i ̸= p, je ta~ka maksimuma problema c b1 . Dokaz. Lako se vidi da je navedena ta~ka dopustiva. U ovoj ta~ki je λ∗k = 0, na osnovu (16) i po{to je δ(G) = k, pa na osnovu (13) bi}e: 81 7.2. SLU^AJ KADA SU k,m I T NEPARNI BROJEVI µ∗k = ( 1√ k − 1√ m )( −2 ( 1√ k − 1√ m ) n− 3 2 − 2 ( 1√ p − 1√ m ) + n ( 1√ k − 1√ m )) = ( 1√ k − 1√ m )( 3√ k − 2√ p − 1√ m ) . Kako je +√ k ≥ 2√ p + )√ m , vidimo da je µ∗k ≥ 0. Na osnovu (14) , za k + 1 ≤ i ≤ m− 1N i ̸= pN je: λ∗i = ( 1√ i − 1√ m )( 2 ( 1√ k − 1√ m ) n− 3 2 + 2 ( 1√ p − 1√ m ) − n ( 1√ i − 1√ m )) = ( 1√ i − 1√ m )( n− 3√ k + 2√ p − n√ i + 1√ m ) . Po{to je 2√ p ≥ )√ k + )√ m i po{to su funkcije )√ i i )√ j − )√ j+) opadaju}e, dobijamo da je T−+√ k + 2√ p − T√ i + )√ m ≥ T−+√ k + )√ k + )√ m − T√ k+) + )√ m = (n− 2)( )√ k − )√ k+) )− 2( )√ k+) − )√ m ) = (n− 2)( )√ k − )√ k+) )− 2∑m−)j5k+)( )√j − )√j+)) ≥ (n− 2)( )√k − )√k+))− 2(m − k − 1)( )√ k − )√ k+) ) ≥ (n − 2 − 2m + 2k + 2)( )√ k − )√ k+) ) ≥ 0N po{to je n − 2m + 2k ≥ n − 2(n − 2) + 2T+) 2 > 0. Vidimo da je i λ∗i ≥ 0. Zna~i, ta~ka a∗b1 zadovoqava Kuhn–Tucker -ove uslove i to je ta~ka maksimuma. 2 Va`i slede}e tvr|ewe. Lema 7.5. Maksimalna vrednost funkcije γ¯) i samim tim funkcije γ) je γ)(b1) = ( 1√ k − 1√ m )2 (n− 3)(n+ 1) 4 + ( 1√ k − 1√ p )2 n− 3 2 + ( 1√ p − 1√ m )2 n+ 1 2 N i ona se posti`e u ta~ki a∗b1 ∈ k odre|enoj sa (T−+2 N 0N . . . N 0N 1N 0N . . . N 0N T+)2 ). Podslu~aj u2. U ovom podslu~aju odredi}emo maksimalnu vrednost funkcije γ) kada su ispuweni uslovi )√ k + )√ m − 2√ p ≤ 0 and nk ≥ T−)2 . Razmatramo problem c b2 : max− ( m−)∑ j5k ( 1√ j − 1√ m ) nj )2 + n m−)∑ j5k ( 1√ j − 1√ m )2 nj pri ~emu va`i np = 1N nk − n− 1 2 ≥ 0N ni ≥ 0N za k + 1 ≤ i ≤ m− 1N i ̸= p. Po teoremi 2.2., dopustiva ta~ka (nkN . . . N nm−)) je ta~ka maksimuma navedenog problema ako postoje nenegativni brojevi µk, λi, za k+1 ≤ i ≤ m−1N i ̸= p, takvi da va`e Kuhn–Tucker -ovi uslovi: (13′) −2 ( m−)∑ j5k ( 1√ j − 1√ m ) nj )( 1√ k − 1√ m ) + n ( 1√ k − 1√ m )2 + µk = 0N 82 7.2. SLU^AJ KADA SU k,m I T NEPARNI BROJEVI (14) − 2 ( m−)∑ j5k ( 1√ j − 1√ m ) nj )( 1√ i − 1√ m ) + n ( 1√ i − 1√ m )2 + λi = 0N za k + 1 ≤ i ≤ m− 1N i ̸= pN i (18) µk ( nk − n− 1 2 ) = 0N (16′) λini = 0N za k + 1 ≤ i ≤ m− 1N i ̸= p. Lema 7.6. Ta~kaa ∗ b2 odre|ena sank = T−) 2 ,np = 1 ini = 0, za k+1 ≤ i ≤ m−1N i ̸= p, je ta~ka maksimuma problema c b2 . Dokaz. Lako se vidi da je navedena ta~ka dopustiva. U ovoj ta~ki iz (13′) bi}e: µ∗k = ( 1√ k − 1√ m )( 2 ( 1√ k − 1√ m ) n− 1 2 + 2 ( 1√ p − 1√ m ) − n ( 1√ k − 1√ m )) = ( 1√ k − 1√ m )( − 1√ k + 2√ p − 1√ m ) . Na osnovu uslova (u) )√ k + )√ m − 2√ p ≤ 0 vidimo da je µ∗k ≥ 0. Iz (14), za k + 1 ≤ i ≤ m− 1N i ̸= p, u ovoj ta~ki bi}e: λ∗i = ( 1√ i − 1√ m )( 2 ( 1√ k − 1√ m ) n− 1 2 + 2 ( 1√ p − 1√ m ) − n ( 1√ i − 1√ m )) = ( 1√ i − 1√ m )( n− 1√ k + 2√ p − n√ i − 1√ m ) . Kako je 2√ p ≥ )√ k + )√ m , dobijamoda je: T−)√ k + 2√ p − T√ i − )√ m ≥ T−)√ k + )√ k + )√ m − T√ i − )√ m = T√ k − T√ i ≥ 0. Vidimo da je i λ∗i ≥ 0. Zna~i, ta~ka a∗b2 zadovoqava Kuhn–Tucker -ove uslove te je ta~ka maksimuma. 2 Kona~no i u ovom slu~aju dolazimo do slede}eg tvr|ewa. Lema 7.7. Maksimalna vrednost funkcije γ¯) i samim tim i funkcije γ) je γ)(b2) = ( 1√ k − 1√ m )2 (n− 1)2 4 + ( 1√ k − 1√ p )2 n− 1 2 + ( 1√ p − 1√ m )2 n− 1 2 N i ona se posti`e u ta~ki a∗b2 ∈ k odre|enoj sa (T−)2 N 0N . . . N 0N 1N 0N . . . N 0N T−)2 ). Sada }emo utvrditi vrednost za p kada funkcije γ)(G1)N γ)(G2)N γ)(b1) i γ)(b2) posti`u maksimalne vrednosti. Ponovimo vrednosti ovih funkcija. γ)(G1) = ( 1√ k − 1√ m )2 (n− 1)2 4 + ( 1√ k − 1√ p )2 n− 1 2 + ( 1√ p − 1√ m )2 n− 1 2 N 83 7.2. SLU^AJ KADA SU k,m I T NEPARNI BROJEVI γ)(G2) = ( 1√ k − 1√ m )2 (n+ 1)(n− 3) 4 + ( 1√ k − 1√ p )2 n+ 1 2 + ( 1√ p − 1√ m )2 n− 3 2 N γ)(b1) = ( 1√ k − 1√ m )2 (n− 3)(n+ 1) 4 + ( 1√ k − 1√ p )2 n− 3 2 + ( 1√ p − 1√ m )2 n+ 1 2 N γ)(b2) = ( 1√ k − 1√ m )2 (n− 1)2 4 + ( 1√ k − 1√ p )2 n− 1 2 + ( 1√ p − 1√ m )2 n− 1 2 . Po{to je Sγ)(G1)PSp = T−) 2 √ p3 ( )√ k + )√ m − 2√ p ) ≥ 0, s obziromna uslov (t), zakqu~ujemo da funkcija γ)(G1) posti`e maksimalnu vrednost γ ∗ )(G1) za p = m − 1. Po{to je Sγ)(G2)PSp = ) 2 √ p3 (T+)√ k + T−+√ m − 2(T−))√ p ) = ) 2 √ p3 (T−)√ k + T−)√ m − 2(T−))√ p + 2√ k − 2√ m ) > 0, zakqu~ujemo da funkcija γ)(G2) posti`e maksimalnu vrednost γ ∗ )(G2) za p = m − 1. Daqe, Sγ)(b2)PSp = T−) 2 √ p3 ( )√ k + )√ m − 2√ p ) ≤ 0, na osnovu uslova (u) i mo`emo zakqu~iti da funkcija γ)(b2) posti`e maksimalnu vrednost γ ∗ )(b2) za p = k + 1. Na kraju, po{to je Sγ)(b1)PSp = ) 2 √ p3 (T−+√ k + T+)√ m − 2(T−))√ p ) < 0, na osnovu uslova (u), i funkcija γ)(b1) posti`e maksimalnu vrednost γ ∗ )(b1) za p = k + 1. Navedimo sve ~etiri ekstremne vrednosti. γ∗)(G1) = ( 1√ k − 1√ m )2 (n− 1)2 4 + ( 1√ k − 1√ m− 1 )2 n− 1 2 + ( 1√ m− 1 − 1√ m )2 n− 1 2 N γ∗)(G2) = ( 1√ k − 1√ m )2 (n+ 1)(n− 3) 4 + ( 1√ k − 1√ m− 1 )2 n+ 1 2 + ( 1√ m− 1 − 1√ m )2 n− 3 2 N γ∗)(b1) = ( 1√ k − 1√ m )2 (n− 3)(n+ 1) 4 + ( 1√ k − 1√ k + 1 )2 n− 3 2 + ( 1√ k + 1 − 1√ m )2 n+ 1 2 N γ∗)(b2) = ( 1√ k − 1√ m )2 (n− 1)2 4 + ( 1√ k − 1√ k + 1 )2 n− 1 2 + ( 1√ k + 1 − 1√ m )2 n− 1 2 . Uporedimo sada γ∗)(G1) i γ ∗ )(G2) . γ∗)(G1) − γ∗)(G2) = ( 1√ k − 1√ m )2 − ( 1√ k − 1√ m− 1 )2 + ( 1√ m− 1 − 1√ m )2 = 2 ( 1√ m− 1 − 1√ m )( 1√ k − 1√ m ) > 0. 84 7.2. SLU^AJ KADA SU k,m I T NEPARNI BROJEVI Vidimo da je ve}a vrednost γ∗)(G1). Uporedimo sada γ ∗ )(b2) i γ∗)(b1). γ∗)(b2) − γ∗)(b1) = ( 1√ k − 1√ m )2 + ( 1√ k − 1√ k + 1 )2 − ( 1√ k + 1 − 1√ m )2 = 2 ( 1√ k − 1√ k + 1 )( 1√ k − 1√ m ) > 0. U ovom slu~aju je ve}a vrednost γ∗)(b2). Sada, uporedimo i vrednosti γ ∗ )(G1) i γ∗)(b2). γ∗)(G1) − γ∗)(b2) = ( 1√ k − 1√ m− 1 )2 n− 1 2 + ( 1√ m− 1 − 1√ m )2 n− 1 2 − ( 1√ k − 1√ k + 1 )2 n− 1 2 − ( 1√ k + 1 − 1√ m )2 n− 1 2 = (n− 1) ( 1√ k + 1 − 1√ m− 1 )( 1√ k − 1√ k + 1 − 1√ m− 1 + 1√ m ) . Po{to je )√ k − )√ k+) > )√ m−) − )√m , sledi da je γ∗)(G1) > γ∗)(b2), ako je k + 1 ̸= m− 1. Ovim smo upravo dokazali slede}e tvr|ewe: Lema 7.8. Ako je np = 1 za neko p, k+1 ≤ p ≤ m−1, tada funkcija γ), koja ispuwava uslove (2)N (5′)N (10), posti`e maksimalnu vrednost γ∗)(G1) = ( 1√ k − 1√ m )2 (n− 1)2 4 + ( 1√ k − 1√ m− 1 )2 n− 1 2 + ( 1√ m− 1 − 1√ m )2 n− 1 2 N u ta~ki odre|enoj sa (T−) 2 N 0N . . . N 0N 1N T−) 2 ). 7.2.2 Maksimalna vrednost funkcije γ2 Razmatra}emo dva podslu~aja: prvi podslu~aj (1) kada je np = 1 za neko p, gde je k < p < m, i drugi podslu~aj (2) kada je np ≥ 2 za neko p, gde je k < p < m. Podslu~aj 1. Za np = 1 dobijamo da je xp,p = 0, odnosno yp,p = 0. Tako|e, va`i sistem jednakosti (1′), a specijalno yk,p+yk+),p+...+2yp,p+...+yp,m = (n−p−1)np = n − p − 1. Funkcija γ2 = − ∑ k≤i γˆ2. Daqe, kako za izvod funkcije γ¯2 va`i: Sγ¯2PSp = ( )√ p − )√ p+) )( )√ p3 − )√ (p+))3 )(n − p − 1) + ( )√ p − )√ p+) )2 > 0, zakqu~ujemo da funkcija γ¯2 posti`e maksimalnu vrednost γ¯ ∗ 2 za p = m − 1. Ova vrednost je γ¯∗2 = − ( 1√ m− 1 − 1√ m )2 (n−m)N i posti`e se kada je ym−),m = n − mN ym,m = (T−m−))Tm−(T−m)2 N yi,i = (T−i−))Ti2 , za i ̸= m − 1N i ̸= m i svi ostali yi,j = 0. Pored toga, yi,i i ni moraju biti celi brojevi. Kako je nm−) = 1, to ostale vrednosti za ni moraju biti celi brojevi za koje va`i nk + ...+ nm−2+ nm = n− 1 (a tih mogu}nosti ima dosta). Zakqu~ujemo da postoji vi{e ekstremnih ta~aka funkcije γ2. Dokazali smo slede}e tvr|ewe: Lema 7.9. Ako je np = 1 za neko p, gde je k + 1 ≤ p ≤ m − 1, tada je maksimalna vrednost funkcije γ2, za koju va`e uslovi (1 ′)N (2)N (5′)N (10− 12), vrednost γ¯∗2 . Kako bismo na{li optimalnu vrednost funkcije γ , mo`emo za ni uzeti vrednosti iz ta~ke (T−) 2 N 0N . . . N 0N 1N T−) 2 ) za koju γ) posti`e maksimalnu vrednost γ∗)(G1). To su: nk = T−) 2 N ni = 0, za k + 1 ≤ i ≤ m − 2, nm−) = 1N nm = T−)2 , yk,k = (T−k−))(T−)) 4 N ym−),m = n − mN ym,m = (T−m−))(T−))−2(T−m)4 , i svi ostali yi,j = 0. Neka je γ∗ = γ∗)(G1) + γ¯ ∗ 2 . Sada se mo`e videti da su yi,i, za k ≤ i ≤ m, celobrojni ako je n ≡ 1(mod 4). Grafove na kojima funkcija γ dobija vrednost γ∗, kada je n ≡ 1(mod 4), smo zapisali u obliku G(n−1 2 ,(,...,(,),n−1 2 ). U slu~aju kada je n ≡ 3(mod 4) uslov celobrojnosti nije ispuwen za navedene vrednosti promenqivih. Analizirajmo vrednosti iz ta~ke (T+) 2 N 0N . . . N 0N 1N T−+ 2 ) za koju funkcija γ) posti`e vrednost γ ∗ )(G2) . Tada su: nk = T+) 2 N ni = 0, za k + 1 ≤ i ≤ m − 2, nm−) = 1N nm = T−+2 , yk,k = (T−k−))(T+))4 N ym−),m = n − mN ym,m = (T−m−))(T−+)−2(T−m) 4 , i svi ostali yi,j = 0. Vidimo da su sve promenqive celobrojne. Grafove za koje funkcija γ posti`e vrednost γ∗)(G2)+ γ¯ ∗ 2 , a koja mo`e da se realizuje u slu~aju n ≡ 3(mod 4), smo zapisali u obliku G(n+1 2 ,(,...,(,),n−3 2 ). Ispostavi}e se, da se na pomenutim grafovima i posti`e ekstremna vrednost funkcije γ, odnosno da je, u slu~aju kada je n ≡ 1(mod 4), ekstremna vrednost ba{ γ∗ = γ∗)(G1) + γ¯ ∗ 2 , a u slu~aju kada je n ≡ 3(mod 4) i k + 1 < m − 1, ekstremna vrednost upravo γ∗)(G2) + γ¯ ∗ 2 . Kada je k + 1 = m− 1 ekstremna vrednost funkcije γ se posti`e na grafovima oblika G(n−1 2 ,),n−1 2 ). O tome }e biti vi{e re~i kasnije. Podslu~aj 2. Ako je np ≥ 2 za neko p, gde je k < p < m, mo`emo za funkciju γ2 uzeti maksimalnu vrednost γ∗2 jednaku nuli. Ova vrednost se posti`e u ta~ki za 86 7.2. SLU^AJ KADA SU k,m I T NEPARNI BROJEVI koju je yi,i = (T−i−))Ti 2 , za k ≤ i ≤ m, i svi ostali yi,j = 0. Pokaza}emo da grafovi na kojima se posti`e ekstremna vrednost ne mogu imati vi{e od jednog ~vora np. 7.2.3 Gorwa granica funkcije γ) kada je np ≥ 2 U ovom delu dokaza}emo slede}e tvr|ewe: Lema7.10. Ako jenp ≥ 2 za neko p izme|uk+1 im−1, ini ≥ 0, za k ≤ i ≤ m−1N i ̸= p, tada je γ¯)(nkN ...N nm−)) ≤ n 2 4 ( 1√ k − 1√ m )2 − 2n ( 1√ m− 1 − 1√ m )( 1√ k − 1√ m− 1 ) . Dokaz. Ozna~imo sa x = ∑m−) i5k,i̸5p( )√ i − )√ m )ni. Imamo da je γ¯) = − ( m−)∑ i5k,i ̸5p ( 1√ i − 1√ m ) ni + ( 1√ p − 1√ m ) np )2 + n m−)∑ i5k,i ̸5p ( 1√ i − 1√ m )2 ni + n ( 1√ p − 1√ m )2 np = − ( m−)∑ i5k,i ̸5p ( 1√ i − 1√ m ) ni )2 − 2np ( 1√ p − 1√ m ) m−)∑ i5k,i ̸5p ( 1√ i − 1√ m ) ni − ( 1√ p − 1√ m )2 n2p + n m−)∑ i5k,i ̸5p ( 1√ i − 1√ m )2 ni + n ( 1√ p − 1√ m )2 np ≤ −x2 − 2np ( 1√ p − 1√ m ) x+ n ( 1√ k − 1√ m ) x+ ( 1√ p − 1√ m )2 np(n− np)N po{to je ( )√ i − )√ m ) ≤ ( )√ k − )√ m ), za k ≤ i ≤ m− 1N i ̸= p. Defini{imo funkciju g = −x2 + ( n ( 1√ k − 1√ m ) − 2np ( 1√ p − 1√ m )) x+ ( 1√ p − 1√ m )2 np(n− np). Na|imo izvod funkcije g po x: Sg Sx = −2x+ n ( 1√ k − 1√ m ) − 2np ( 1√ p − 1√ m ) . Kako je drugi izvod funkcije g po x negativan, ∂ 2g ∂x2 = −2, funkcija g posti`e maksimalnu vrednost za x∗ = T 2 ( )√ k − )√ m ) − np ( )√ p − )√ m ) . Na|imo vrednost g(x∗). 87 7.2. SLU^AJ KADA SU k,m I T NEPARNI BROJEVI g(x∗) = x∗ ( n ( 1√ k − 1√ m ) − 2np ( 1√ p − 1√ m ) − x∗ ) + ( 1√ p − 1√ m )2 np(n− np) = ( n 2 ( 1√ k − 1√ m ) − np ( 1√ p − 1√ m )) · ( n ( 1√ k − 1√ m ) − 2np ( 1√ p − 1√ m ) − n 2 ( 1√ k − 1√ m ) + np ( 1√ p − 1√ m )) + ( 1√ p − 1√ m )2 np(n− np) = ( n 2 ( 1√ k − 1√ m ) − np ( 1√ p − 1√ m ))2 + ( 1√ p − 1√ m )2 np(n− np) = n 2 4 ( 1√ k − 1√ m )2 + n2p ( 1√ p − 1√ m )2 − nnp ( 1√ k − 1√ m )( 1√ p − 1√ m ) + ( 1√ p − 1√ m )2 np(n− np) = n2 4 ( 1√ k − 1√ m )2 − nnp ( 1√ p − 1√ m )( 1√ k − 1√ p ) . Na|imo sada izvod po np. Kako je ∂g(x∗) ∂Tp = −n ( )√ p − )√ m )( )√ k − )√ p ) < 0, to funkcija g(x∗) posti`e maksimalnu vrednost g¯(x∗) za np = 2. Sada je g(x∗) ≤ n 2 4 ( 1√ k − 1√ m )2 − 2n ( 1√ p − 1√ m )( 1√ k − 1√ p ) = g¯(x∗). Daqe je Sg¯(x∗) Sp = n√ p+ ( 1√ k + 1√ m − 2√ p ) . Ako va`i uslov (t), tada funkcija g¯(x∗) posti`e maksimalnu vrednost g¯)(x∗) za p = m− 1. Ako va`i uslov (u), tada funkcija g¯(x∗) posti`e maksimalnu vrednost g¯2(x ∗) za p = k+1. Ozna~imo sa△g razliku funkcija g¯)(x∗)− g¯2(x∗) funkcija. S obzirom da su prvi sabirci isti, bi}e: △g = 2n (( 1√ k + 1 − 1√ m )( 1√ k − 1√ k + 1 ) − ( 1√ m− 1 − 1√ m ) · ( 1√ k − 1√ m− 1 )) = 2n (( 1√ k + 1 − 1√ m− 1 + 1√ m− 1 − 1√ m ) · ( 1√ k − 1√ k + 1 ) − ( 1√ m− 1 − 1√ m )( 1√ k − 1√ k + 1 + 1√ k + 1 − 1√ m− 1 )) = 2n ( 1√ k + 1 − 1√ m− 1 )( 1√ k − 1√ k + 1 − 1√ m− 1 + 1√ m ) . Kako je )√ k − )√ k+) ≥ )√ m−) + )√ m , zakqu~ujemo da je maksimalna vrednost funkcije g¯(x∗) upravo g¯)(x∗) = T 2 4 ( )√ k − )√ m )2 − 2n ( )√ m−) − )√m )( )√ k − )√ m−) ) . Tako|e, dokazali smo da je γ¯) ≤ g¯)(x∗), odnosno γ) ≤ g¯)(x∗) za (nkN ...N nm) ∈ k . 2 88 7.2. SLU^AJ KADA SU k,m I T NEPARNI BROJEVI 7.2.4 Dokazi teorema Pre nego {to pre|emo na dokaz prve teoreme, doka`imo jednu lemu. Lema 7.11. Grafovi na kojima se posti`e ekstremna vrednost ne mogu imati dva ili vi{e ~vorova stepena p, za k + 1 ≤ p ≤ m− 1. Dokaz. Ozna~imo sa γ˜∗ maksimalnu vrednost funkcije γ kada postoje dva ili vi{e ~vorova stepena p, za k + 1 ≤ p ≤ m− 1. Tada je γ˜∗ ≤ g¯)(x∗) + γ∗2 = g¯)(x∗), po{to je γ∗2 = 0. Imamo da je γ∗ − γ˜∗ ≥ γ∗)(G1) + γ¯∗2 − g¯)(x∗) ≥ γ∗)(G2) + γ¯∗2 − g¯)(x∗) = ( 1√ k − 1√ m )2 (n+ 1)(n− 3) 4 + ( 1√ k − 1√ m− 1 )2 n+ 1 2 + ( 1√ m− 1 − 1√ m )2 n− 3 2 − ( 1√ m− 1 − 1√ m )2 (n−m) − n 2 4 ( 1√ k − 1√ m )2 + 2n ( 1√ m− 1 − 1√ m )( 1√ k − 1√ m− 1 ) = ( 1√ k − 1√ m )2 −2n− 3 4 + ( 1√ k − 1√ m− 1 )2 n+ 1 2 + ( 1√ m− 1 − 1√ m )2 n− 3 2 − ( 1√ m− 1 − 1√ m )2 (n−m) + 2n ( 1√ m− 1 − 1√ m )( 1√ k − 1√ m− 1 ) = n+ 1 2 ( − ( 1√ k − 1√ m )2 + ( 1√ k − 1√ m− 1 )2 + ( 1√ m− 1 − 1√ m )2) − 1 4 ( 1√ k − 1√ m )2 − (n−m+ 2) ( 1√ m− 1 − 1√ m )2 + 2n ( 1√ m− 1 − 1√ m )( 1√ k − 1√ m− 1 ) = (n− 1) ( 1√ m− 1 − 1√ m )( 1√ k − 1√ m− 1 ) − 1 4 ( 1√ k − 1√ m )2 − (n−m+ 2) ( 1√ m− 1 − 1√ m )2 N jer je: −( )√ k − )√ m )2+( )√ k − )√ m−)) 2+( )√ m−)− )√m)2 = −2( )√m−)− )√m) ( )√k− )√m−)). Kako je ( )√ m−) − )√m) ≤ ( )√k − )√m−)), imamo da je γ∗ − γ˜∗ ≥ (n− 1− n+m− 2) ( 1√ m− 1 − 1√ m )( 1√ k − 1√ m− 1 ) − 1 4 ( 1√ k − 1√ m )2 = 89 7.2. SLU^AJ KADA SU k,m I T NEPARNI BROJEVI = (m− 3) ( 1√ m− 1 − 1√ m )( 1√ k − 1√ m− 1 ) − 1 4 ( 1√ k − 1√ m− 1 )2 − 1 4 ( 1√ m− 1 − 1√ m )2 − 1 2 ( 1√ k − 1√ m− 1 )( 1√ m− 1 − 1√ m ) ≥ (4m− 12− 2− 1) 4 ( 1√ k − 1√ m− 1 )( 1√ m− 1 − 1√ m ) − 1 4 ( 1√ k − 1√ m− 1 )2 = 1 4 ( 1√ k − 1√ m− 1 )( (4m− 15) ( 1√ m− 1 − 1√ m ) − ( 1√ k − 1√ m− 1 )) ≥ 1 4 ( 1√ k − 1√ m− 1 )( (4m− 15) ( 1√ m− 1 − 1√ m ) −(m− 1− k) ( 1√ k − 1√ k + 1 )) . Ovde smo koristili: ( )√ k − )√ m−)) = ∑m−2 j5k ( )√ j − )√ j+) ) ≤ (m− 1− k)( )√ k − )√ k+) ). Kako je ( )√ j − )√ j+) ) opadaju}a funkcija i T−) 2 ≤ k < m < n, imamo da je )√ k − )√ k+) ≤ )√ n−1 2 − )√ n−1 2 +) = √ 2( )√ T−) − )√T+)) = √ 2( )√ T−) − )√T + )√T − )√T+)) ≤ 2 √ 2( )√ T−) − )√T) < 4( )√T−) − )√T) < 4( )√m−) − )√m). Kada primenimo nejednakost ( )√ k − )√ k+) ) < 4( )√ m−) − )√m), dobijamo da je (4m− 15) ( 1√ m− 1 − 1√ m ) − (m− 1− k) ( 1√ k − 1√ k + 1 ) > (4m− 15− 4m+ 4k + 4) ( 1√ m− 1 − 1√ m ) = (4k − 11) ( 1√ m− 1 − 1√ m ) > 0N za k ≥ 3. Time smo pokazali da je γ∗ > γ˜∗. Iz ovoga sledi da grafovi na kojima se posti`e ekstremna vrednost ne mogu imati dva ili vi{e ~vorova stepena p, za k + 1 ≤ p ≤ m− 1. 2 Dokaz teoreme 7.4. Na osnovu prethodnog (leme 7.11. i lema 7.8. i 7.9.) vidimo da funkcija γ posti`e maksimalnu vrednost γ∗ u ta~ki odre|enoj sa nk = T−)2 N ni = 0, za k+1 ≤ i ≤ m−2, nm−) = 1N nm = T−)2 , yk,k = (T−k−))(T−))4 N ym−),m = n−mN ym,m = (T−m−))(T−))−2(T−m) 4 , i svi ostali su yi,j = 0. Iz (9) nalazimo odgovaraju}e vred- nosti za xi,j . Bi}e: xk,k = ( Tk 2 ) − yk,k = Tk(Tk−))2 − (T−k−))(T−))4 = (T−))(T−+)0 − (T−k−))(T−)) 4 = (T−))(−T+2k−)) 0 , xk,m−) = nknm−) − yk,m−) = T−)2 · 1 − 0 = T−)2 , xk,m = nknm − yk,m = T−)2 T−)2 − 0 = (T−)) 2 4 , xm−),m = nm−)nm − ym−),m = 1· T−) 2 −(n−m) = −T+2m−) 2 , xm,m = ( Tm 2 )−ym,m = (T−))(T−+)0 − (T−m−))(T−))−2(T−m)4 = (T−))(−T+2m−)) 0 + T−m 2 i svi ostali xi,j = 0. Sve vrednosti promenqivih su celi brojevi za n ≡ 1(mod 4) (ali nisu za n ≡ 3(mod 4) ). Na osnovu (7) i vrednosti za xi,j lako dolazimo do minimalne vrednosti Randi}evog indeksa navedene u te- oremi (ili na osnovu vrednosti za γ∗). Odgovaraju}e grafove mo`emo opisati sa 90 7.2. SLU^AJ KADA SU k,m I T NEPARNI BROJEVI G(n−1 2 ,(,...,(,),n−1 2 ), te smo ovim kona~no dokazali prvu od tri teoreme. 2 Daqa razmatrawa se odnose samo na slu~aj n ≡ 3(mod 4). Kao {to smo rekli, grafovi za koje funkcija γ ima vrednost γ∗)(G2)+ γ¯ ∗ 2 postoje za n ≡ 3(mod 4), po{to su odgovaraju}e vrednosti za yi,j celi brojevi a samim tim su i vrednosti xi,j celi brojevi (na kraju }emo ih na}i). Prvo }emo pokazati da je vrednost γ∗)(G2)+ γ¯ ∗ 2 ve}a od bilo koje vrednosti funkcije γ na grafovima koji imaju jedan ~vor stepena p kada je k + 1 ≤ p ≤ m − 2. Kako smo pokazali da je navedena vrednost funkcije γ ve}a od vrednosti kada graf ima dva ~vora, ostaju kasnije za razmatrawe samo grafovi koji imaju ~vorove stepena k, stepenam i jedan ~vor stepenam− 1. Lema 7.12. Ako je k+1 < m−1, grafovi na kojima se posti`e ekstremna vrednost ne mogu imati ~vor stepena p, za k + 1 ≤ p ≤ m− 2. Dokaz. Poka`imo da je γ∗)(G2) > γ)(G1)(p), za k + 1 ≤ p ≤ m − 2. Kako γ)(G1) zavisi od kNmN n i p, tj. γ)(G1) = γ)(G1)(kNmN nN p), mi sa γ)(G1)(p) (γ)(G1)(p) = γ)(G1)) isti~emo zavisnost od p. Ozna~imo sa△ razliku γ∗)(G2)−γ)(G1)(p). Za po~etak neka je p ̸= k + 1, tj. k + 2 ≤ p ≤ m− 2. Imamo da je: △ = γ∗)(G2) − γ)(G1)(p) = ( 1√ k − 1√ m )2 (n+ 1)(n− 3) 4 + ( 1√ k − 1√ m− 1 )2 n+ 1 2 + ( 1√ m− 1 − 1√ m )2 n− 3 2 − (( 1√ k − 1√ m )2 (n− 1)2 4 + ( 1√ k − 1√ p )2 n− 1 2 + ( 1√ p − 1√ m )2 n− 1 2 ) = − ( 1√ k − 1√ m )2 + ( 1√ k − 1√ m− 1 )2 − ( 1√ m− 1 − 1√ m )2 + n− 1 2 [( 1√ k − 1√ m− 1 )2 + ( 1√ m− 1 − 1√ m )2 − ( 1√ k − 1√ p )2 − ( 1√ p − 1√ m )2] = − ( 1√ m− 1 − 1√ m )( 2√ k − 1√ m − 1√ m− 1 ) − ( 1√ m− 1 − 1√ m )2 + n− 1 2 [( 1√ p − 1√ m− 1 )( 2√ k − 1√ p − 1√ m− 1 ) − ( 1√ p − 1√ m− 1 )( 1√ p + 1√ m− 1 − 2√ m )] N odnosno da je: (19) △ = −2 ( 1√ k − 1√ m )( 1√ m− 1 − 1√ m ) + (n− 1) ( 1√ p − 1√ m− 1 ) · (( 1√ k − 1√ p ) − ( 1√ m− 1 − 1√ m )) . 91 7.2. SLU^AJ KADA SU k,m I T NEPARNI BROJEVI Po{to je )√ p − )√ m−) ≥ )√m−) − )√m , to je △ ≥ ( 1√ m− 1 − 1√ m ) · ( (n− 1) (( 1√ k − 1√ p ) − ( 1√ m− 1 − 1√ m )) − 2 ( 1√ k − 1√ m )) . Primetimo da je, za T+) 2 ≤ k < m ≤ n− 2,m− k ≤ n− 2− T+) 2 = T−5 2 . Kako je( 1√ k − 1√ m ) ≤ (m− k) ( 1√ k − 1√ k + 1 ) ≤ (n− 5) 2 ( 1√ k − 1√ k + 1 ) i k + 1 < p, imamo da je (n− 1) (( 1√ k − 1√ p ) − ( 1√ m− 1 − 1√ m )) − 2 ( 1√ k − 1√ m ) ≥ (n− 1) (( 1√ k − 1√ k + 1 ) + ( 1√ k + 1 − 1√ p ) − ( 1√ m− 1 − 1√ m )) − (n− 5) ( 1√ k − 1√ k + 1 ) ≥ 4 ( 1√ k − 1√ k + 1 ) > 0. Poka`imo da je γ∗)(G2) > γ)(G1)(k+1) = γ ∗ )(b2) . Ozna~imo sa △¯ razliku γ∗)(G2)−γ∗)(b2). Razliku △¯ dobijamo iz (19) za p = k + 1. △¯ = −2 ( 1√ k − 1√ m )( 1√ m− 1 − 1√ m ) + (n− 1) ( 1√ k + 1 − 1√ m− 1 ) · (( 1√ k − 1√ k + 1 ) − ( 1√ m− 1 − 1√ m )) = −2 ( 1√ k − 1√ k + 1 + 1√ k + 1 − 1√ m− 1 + 1√ m− 1 − 1√ m )( 1√ m− 1 − 1√ m ) +(n− 1) ( 1√ k + 1 − 1√ m− 1 )(( 1√ k − 1√ k + 1 ) − ( 1√ m− 1 − 1√ m )) = ( 1√ k + 1 − 1√ m− 1 )( (n− 1) ( 1√ k − 1√ k + 1 ) − (n+ 1) ( 1√ m− 1 − 1√ m )) −2 ( 1√ k − 1√ k + 1 )( 1√ m− 1 − 1√ m ) − 2 ( 1√ m− 1 − 1√ m )2 . Po{to je k + 1 < m− 1, ili k + 4 ≤ m po{to su neparni brojevi, pa je 1√ k + 1 − 1√ m− 1 = 1√ k + 1 − 1√ k + 2 + 1√ k + 2 − 1√ m− 1 > 2 ( 1√ m− 1 − 1√ m ) 92 7.2. SLU^AJ KADA SU k,m I T NEPARNI BROJEVI i (n− 1) ( 1√ k − 1√ k + 1 ) − (n+ 1) ( 1√ m− 1 − 1√ m ) > (n− 2) ( 1√ k − 1√ k + 1 ) − (n+ 2) ( 1√ m− 1 − 1√ m ) . Ovaj izraz sa desne strane posledwe nejednakosti je pozitivan, {to }emo pokazati kasnije. Sada je △¯ > 2 ( 1√ m− 1 − 1√ m )( (n− 1) ( 1√ k − 1√ k + 1 ) − (n+ 1) ( 1√ m− 1 − 1√ m )) −2 ( 1√ k − 1√ k + 1 )( 1√ m− 1 − 1√ m ) − 2 ( 1√ m− 1 − 1√ m )2 = 2 ( 1√ m− 1 − 1√ m )( (n− 2) ( 1√ k − 1√ k + 1 ) − (n+ 2) ( 1√ m− 1 − 1√ m )) . Sada doka`imo da je izraz (n − 2)( )√ k − )√ k+) ) − (n + 2)( )√ m−) − )√m) pozitivan. Po{to je )√ j − )√ j+) opadaju}afunkcija i va`i k < k+1 < k+2 < m−1 < m ≤ n−2, imamo da je (n − 2)( )√ k − )√ k+) ) − (n + 2)( )√ m−) − )√m) ≥ (n − 2)( )√k − )√k+)) − (n + 2)( )√ k++ − )√ k+4 ) ≥ k( )√ k − )√ k+) ) − (k + 4)( )√ k++ − )√ k+4 ) = √ k − √k + 1 + )√ k+) − )√ k++ + √ k + 4−√k + 3 = − )√ k+ √ k+) + )√ k+++ √ k+4 + 2√ (k+))(k++)( √ k+)+ √ k++) ≥ − )√ k+ √ k+) + )√ k+++ √ k+4 + 2 (k+2)( √ k+++ √ k+4) = − )√ k+ √ k+) + k+4 (k+2)( √ k+++ √ k+4) ≥ − )√ k+ √ k+) + k+4 2(k+2) √ k+4 = − )√ k+ √ k+) + √ k+4 2(k+2) . Posledwi izraz }e biti pozitivan kada je √ k + 4( √ k+ √ k + 1) > 2(k+2), a ova nejednakost se svodi na nejednakost 8k+ − k2 − 104k − 144 > 0, koja je ta~na za k ≥ 5. Za k ≤ 4 , mo`emo proveriti da je k( )√ k − )√ k+) )− (k+4)( )√ k++ − )√ k+4 ) > 0, mada i ne postoji vrednost za k za koju je T 2 < k < m < n i da su kNmN n neparni brojevi (jer ako je k = 1 mora biti n ≤ 1, a za k = 3 mora biti n ≤ 5 ). Sada je, kona~no, △¯ > 0. Dobili smo da je γ∗)(G2) > γ)(G1)(p), za k + 1 ≤ p ≤ m − 2. Po{to i γ)(G1)(p) i γ)(b2)(p) imaju isti zapis, va`i da je γ ∗ )(G2) > γ)(b2)(p) za k+1 ≤ p ≤ m−2. Mo`emo dodati jo{ i to da, kada je p = k + 1, je γ∗)(G2) > γ)(G1)(k + 1) = γ)(b2)(k + 1) = γ∗)(b2) ≥ γ)(b2)(p). Nesporno tako|e va`i da je γ∗)(G2) > γ)(G2)(p), kada je p ≤ m− 2 i va`i uslov (t) i da je γ∗)(G2) > γ)(b1)(p), kada je p ≥ k + 1 i va`i uslov (u). Kako funkcija γ2 posti`e, pod uslovom np = 1 za neko p, maksimalnu vrednost γ¯∗2 , upravo kada postoji ~vor stepena m − 1 i kada se ostvaruje vrednost γ∗)(G2), mo`emo zakqu~iti da grafovi na kojima se posti`e ekstremna vrednost ne mogu imati ~vorove nekog stepena p za k + 1 ≤ p ≤ m− 2. 2 Dokaz teorema 7.5. i 7.6. Ponovimo jo{ jednom, ekstremne vrednosti funkcija γ posti`e na grafovima koji imaju samo ~vorove stepena k, jedan ~vor stepena m−1 i ~vorove stepenam.Uporedimo daqe,pod uslovom n ≡ 3(mod 4), vrednosti funkcije γ na grafovima za koje funkcija γ) posti`e vrednosti γ ∗ )(G1) i γ∗)(G2), s tim 93 7.2. SLU^AJ KADA SU k,m I T NEPARNI BROJEVI {to }emo i u prvom slu~aju ostvariti uslov celobrojnosti. Ako je n ≡ 3(mod 4) i kako smo ranije videli da vrednost xk,k = (T−))(−T+2k−)) 0 , koja se posti`e na grafu G(n−1 2 ,(,...,(,),n−1 2 ), nije ceo broj, mo`emo izmeniti funkciju γ2 kako bismo dobili dopustivo grafovsko re{ewe. Tu promenu u~ini}emo najboqom mogu}om kako bismo sa~uvali {to ve}u vrednost funkcije γ2. Podse}amo ~itaoca da sistem jedna~ina (1′) sada ima oblik (1′′′) koji se sastoji samo od tri jedna~ine, po{to su ni = 0 za k + 1 ≤ i ≤ m− 2 (ym−),m−) = 0 jer je nm−) = 1). 2yk,k + yk,m−) + yk,m = (n− k − 1)nkN (1′′′) yk,m−) + ym−),m = (n−m) · 1N yk,m + ym−),m + 2ym,m = (n−m− 1)nm. Kako je ranije bilo ym−),m = n−m, uzmimoda su yk,m−) = 1i ym−),m = n−m−1, yk,k = (T−k−))(T−)) 4 − ) 2 N ym,m = (T−m−))(T−+) 4 , i svi ostali yi,j = 0 (sve navedene promenqive su celobrojne). Ozna~imo sa γ˜2 vrednost funkcije γ2 koja se dobija za navedene vrednosti, tj. γ˜2 = −(n−m−1)( )√m−)− )√m)2− ( )√k − )√m−))2. Ozna~imo daqe, sa △) razliku γ∗)(G2) + γ¯∗2 − γ∗)(G1) − γ˜2. Iz (19) se za p = m − 1 lako dobija da je razlika γ∗)(G2) − γ∗)(G1) = −2 ( 1√ k − 1√ m )( 1√ m− 1 − 1√ m ) (a i ranije smo upore|ivali ove vrednosti). Va`i i da je γ¯∗2 − γ˜2 = − ( 1√ m− 1 − 1√ m )2 (n−m)− ( −(n−m− 1) ( 1√ m− 1 − 1√ m )2 − ( 1√ k − 1√ m− 1 )2) = − ( 1√ m− 1 − 1√ m )2 + ( 1√ k − 1√ m− 1 )2 . Imamo da je: △) = −2 ( 1√ k − 1√ m )( 1√ m− 1 − 1√ m ) − ( 1√ m− 1 − 1√ m )2 + ( 1√ k − 1√ m− 1 )2 = −2 ( 1√ k − 1√ m )( 1√ m− 1 − 1√ m ) + ( 1√ k − 1√ m )( 1√ k − 2√ m− 1 + 1√ m ) = ( 1√ k − 1√ m )( 1√ k − 4√ m− 1 + 3√ m ) = ( 1√ k − 1√ m )(( 1√ k − 1√ m− 1 ) − 3 ( 1√ m− 1 − 1√ m )) . Kada je k + 1 < m − 1, (odnosno k ≤ m − 4), imamo da je )√ k − )√ m−) =∑m−2 j5k ( )√ j − )√ j+) ) > (m− k − 1)( )√ m−) − )√m) ≥ 3( )√m−) − )√m). Zakqu~ujemo da je 94 7.2. SLU^AJ KADA SU k,m I T NEPARNI BROJEVI △) > 0 i da je mogu}a ekstremna vrednost funkcije γ vrednost γ∗)(G2) + γ¯∗2 koja se posti`e na grafu G(n+1 2 ,(,...,(,),n−3 2 ). Kada je k + 1 = m− 1, imamo da je: △) = ( 1√ k − 1√ k + 2 )(( 1√ k − 1√ k + 1 ) − 3 ( 1√ k + 1 − 1√ k + 2 )) . Kako je )√ k − 4√ k+) + +√ k+2 = )√ k − +√ k+) − ( )√ k+) − +√ k+2 ) i za prvi izvod po k va`i ∂ ∂k ( )√ k − +√ k+) ) = − ) 2k √ k + + 2(k+)) √ k+) = +k √ k−(k+))√k+) 2k √ k(k+)) √ k+) ≥ √ (2k)3− √ (k+))3 2k √ k(k+)) √ k+) ≥ 0 za k ≥ 1, zakqu~ujemo da je )√ k − 4√ k+) + +√ k+2 ≤ 0 za k ≥ 1. Sada je △) < 0 i mogu}a ekstremna vrednost funkcije γ je vrednost γ∗)(G1) + γ˜2 koja se posti`e na grafu G˜(n−1 2 ,),n−1 2 ). Na kraju, uporedimo vrednost γ∗)(G2) sa novom maksimalnom vredno{}u funk- cije γ¯) u slu~aju (t)) koja se razlikuje od vrednosti γ ∗ )(G1) , tj. iskqu~imo ta~kua ∗ G1 za p = m − 1. Nalazimo, u tom slu~aju (t′)), maksimalnu vrednost γ¯′) funkcije γ¯) pod uslovima nk ≤ T−+2 N ni = 0 za k + 1 ≤ i ≤ m − 2 i nm−) = 1. Ova vrednost γ¯′) se lako dobija i iznosi: γ¯′) = ( 1√ k − 1√ m )2 (n− 3)(n+ 1) 4 + ( 1√ k − 1√ m− 1 )2 n− 3 2 + ( 1√ m− 1 − 1√ m )2 n+ 1 2 . Kako je γ∗)(G2) = ( 1√ k − 1√ m )2 (n+ 1)(n− 3) 4 + ( 1√ k − 1√ m− 1 )2 n+ 1 2 + ( 1√ m− 1 − 1√ m )2 n− 3 2 N razlika navedenih vrednosti }e biti: γ∗)(G2) − γ¯′) = 2 (( 1√ k − 1√ m− 1 )2 − ( 1√ m− 1 − 1√ m )2) > 0. Vidimo da je γ∗)(G2) > γ¯ ′ ). Nakon svega zakqu~ujemo da je, u slu~aju kada je k + 1 = m − 1, maksimalna vrednost funkcije γ vrednost γ∗)(G1) + γ˜2 odnosno, u slu~aju kada je k + 1 < m− 1, vrednost γ∗)(G2) + γ¯ ∗ 2 . Ranije smo videli da su sve vrednosti promenqivih ni i yi,j celobrojne u oba slu~aja postizawa maksimalne vrednosti funkcije γ. Na osnovu veza (9) xi,j = ninj − yi,j za k ≤ i ≤ mN i < j ≤ mN xi,i = ( Ti 2 )− yi,i za k ≤ i ≤ mN 95 7.3. UOP[TEWA REZULTATA U SLU^AJU KADA JE k ≤ n 2 uslov celobrojnosti je ispuwen i za promenqive xi,j . Kada jem = k + 2, vrednost γ∗)(G1) + γ˜2 se posti`e za: nk = T−) 2 , nk+) = nm−) = 1N nk+2 = nm = T−) 2 , yk,k+) = yk,m−) = 1, yk+),k+2 = ym−),m = n − m − 1 = n − k − 3, yk,k = (T−k−))(T−))4 − )2 N yk+2,k+2 = ym,m = (T−m−))(T−+)4 = (T−k−+)(T−+)4 , yk,k+2 = 0 i yk+),k+) = 0. Sada su vrednosti po~etnih promenqivih: xk,k =( Tk 2 )−yk,k = Tk(Tk−))2 − (T−k−))(T−))4 + )2 = (T−))(T−+)0 − (T−k−))(T−))4 + )2 = (T−))(2k−T−))0 + ) 2 N xk,k+) = nknk+)− yk,k+) = T−)2 1− 1 = T−+2 N xk,k+2 = nknk+2− yk,k+2 = T−)2 T−)2 − 0 = (T−)) 2 4 N xk+),k+) = ( Tk+1 2 )− yk+),k+) = Tk+1(Tk+1−))2 − 0 = )()−))2 = 0N xk+),k+2 = nk+)nk+2 − yk+),k+2 = 1T−)2 − (n− k − 3) = 2k−T+52 i xk+2,k+2 = ( Tk+2 2 )− yk+2,k+2 = Tk+2(Tk+2−)) 2 − (T−k−+)(T−+) 4 = (T−))(T−+) 0 − (T−k−+)(T−+) 4 = (T−+)(2k−T+5) 0 . Na osnovu ovih vrednosti i definicije Randi}evog indeksa lako se dolazi do vrednosti navedene u teoremi 7.5. Kada je k + 1 < m − 1, vrednost γ∗)(G2) + γ¯∗2 se posti`e za: nk = T+)2 N ni = 0, za k + 1 ≤ i ≤ m − 2, nm−) = 1N nm = T−+2 , yk,k = (T−k−))(T+))4 N ym−),m = n−mN ym,m = (T−m−))(T−+)−2(T−m)4 , i svi ostali yi,j = 0. Vrednosti po~etnih pro- menqivih su: xk,k = ( Tk 2 )−yk,k = Tk(Tk−))2 − (T−k−))(T+))4 = (T+))(T−))0 − (T−k−))(T+))4 = (T+))(2k−T+)) 0 N xk,m−) = nknm−) − yk,m−) = T+)2 1 − 0 = T+)2 N xk,m = nknm − yk,m = T+) 2 T−+ 2 − 0 = (T+))(T−+) 4 N xm−),m = nm−)nm − ym−),m = 1T−+2 − (n − m) = 2m−T−+ 2 N xm,m = ( Tm 2 ) − ym,m = Tm(Tm−))2 − (T−m−))(T−+)−2(T−m)4 = (T+))(T−))0 − (T−m−))(T−+)−2(T−m) 4 = (T−+)(2m−T−+) 0 + T−m 2 i sve ostale promenqive su jednake nuli. Na osnovu ovih vrednosti i definicije Randi}evog indeksa lako se dolazi do vrednosti navedene u teoremi 7.6. 2 7.3 Uop{tewa rezultata u slu~aju kada je k ≤ n2 U slu~aju kada je k ≤ T 2 bi}e prezentovano uop{tewe samo kada je n− k ≤ m ≤ n− 2. Iznosimo tvr|ewe koje odgovara teoremi 6.1. i do koga se dolazi na sli~an na~in. Teorema 7.7. Ako je k ≤ T 2 , n− k ≤ m ≤ n− 2 i G ∈ G(kNmN n), tada je e(G) ≥ n 2 − 1 2 ( 1√ k − 1√ m )2 (n− k)k. Ako je k paran, ili ako su k i n −m neparni brojevi, ova vrednost se posti`e na grafovima za koje je nk = n− kN nm = kN xk,m = (n− k)kN xm,m = k(k +m− n)P2, i svi ostali xi,jN xi,i i ni su jednaki nuli. Dokaz. Kako je dokaz teoreme sli~an dokazu teoreme 6.1., iznosimo samo kra}e napomene. U slu~aju kada je△(G) = n− 1, imali smo ograni~ewe nT−) ≤ k. Sada, kada je△(G) = m i n− k ≤ m ≤ n− 2, mo`e biti i nq > k. U tom slu~aju mo`emo uzeti k ~vorova stepenam i obojiti ih u crveno. Daqe }emo dokaz nastaviti kao dokaz slu~aja (v). 2 96 7.3. UOP[TEWA REZULTATA U SLU^AJU KADA JE k ≤ n 2 Ako je k neparan broj i razlika n − m paran, tada vrednost xm,m nije ceo broj i ne postoji ekstremni graf. Navedena vrednost u teoremi je dowa granica Randi}evog indeksa. Zna~i, ostaje otvoren problem u slu~aju kada su k neparan i n − q paran broj. Tako|e, i u slu~aju kada je k ≤ T 2 i k ≤ m ≤ n − k problem je otvoren. Na slici 7.17. predstavqen je graf G ∈ G(4N 13N 16) na kome se posti`e mi- nimalna vrednost Randi}evog indeksa, odnosno graf reda n = 16, minimalnog stepena ~vorova k = 4 i maksimalnog stepena ~vorova m = 13, pri ~emu je n4 = 12N n)+ = 4N x4,)+ = 48 i x)+,)+ = 2. Slika 7.17. Graf G ∈ G(4N 13N 16). Slika 7.18. Graf G ∈ G(5N 12N 15). Na slici 7.18. predstavqen je graf G ∈ G(5N 12N 15) na kome se posti`e mi- nimalna vrednost Randi}evog indeksa, odnosno graf reda n = 15, minimalnog stepena ~vorova k = 5 i maksimalnog stepena ~vorova m = 12, pri ~emu je n5 = 10N n)2 = 5N x5,)2 = 50 i x)2,)2 = 5. 97 Summary This doctoral dissertation belongs to the Combinatorial Optimization applied to graphs, which includes elements of Linear and Quadratic Programming and Graph Theory. Combinatorial Optimization, as special mathematical discipline, is relatively yo- ung, although the first papers are more than two hundred years old. The fast development emerges after the second wold war, when grows need for optimization many tasks and processes. Since many objects could be represents as graph and combinatorial optimization solve extremal problems on discrete structures, there is narrow connection with Graph Theory. The subject of this dissertation is finding minimal value of the Randic´ index on n-vertex graphs G(kN n) with given minimum degree k of vertices and describing the structure of extremal graphs. This index was introduced 1975 by chemist Milan Randic´ in order to measure the branching of some molecules. There is a good correlations between this index and some physico-chemical properties of alcanes. There is, also, connection between Randic´ index and the eigenvalues of the Laplacian matrix of graph. Hereby, we describe in short the content of this dissertation. The dissertation consists of seven Chapters divided in sections, References and Appendix. Chapter 1 corresponds to the introduction. At the end of this Chapter, is speci- fied original contribution of the author to scientific research in this field. In Chapter 2 are given some basic notions and definitions from graph theory (section 2.1), definition of the Randic´ index from [35](section 2.2) and basic notions and definitions from convex analysis and mathematical programming (section 2.3). In section 2.2 are given short review of relevant results about the Randic´ index. Chapter 3 consists of two section. In section 3.1 are given mathematical models of simple n-vertex graphs with minimum degree k of vertices from [31],[33]. Thro- ugh the complete dissertation are given many mathematical models which describes graphs from different points of view. In order to solve some optimization problem very important is mathematical model which describes it. Choosing mathematical model which fits the problem very well is half task. The other half is to choose mat- hematical method to solve the problem (section 3.2). In subsection 3.2.1 is given method of linear programming from [28] and in subsection 3.2.2 method of quadratic programming [33]. The successful applying of quadratic programming method to given problem is original contribution of the author of this dissertation [33]. In Chapter 4 is given maximal value of the Randic´ index and graphs on which it attains.These results are already known [14],[28]. 98 SMMM9RY Chapter 5 is dedicated to finding minimal value of the Randic´ index on n vertex graph with given minimum degree k and describing extremal graphs, when minimum degree k ≥ T 2 . The results are shown in [27]. This chapter consists of 4 sections. In section 5.1 are given three conjectures about the structure of the extremal graphs from [10], [1] and [27]. Minimal value of the Randic´ index depends of the parity of k and n. Since the case k ≥ T 2 is divided to three subcases, every section 5.1, 5.2 and 5.3 is dedicated to separate subcase. In section 5.2 is done subcase n ≡ 0( mod 4) and n ≡ 2( mod 4) with k odd. In section 5.3 is done subcase when n is odd and in section 5.4 subcase n ≡ 2( mod 4) and k is even. The new approach to this problem and carrying out the third subcase represents original contributions of the author. Due to the new approach, the proofs in all three subcases are substantially simplified, instead of 21 lemmas are given 5 necessary lemmas. Chapter 6 consists of the proof of the first part, when k ≤ T 2 , of all three conjec- tures dedicated to the Randic´ index. Results are shown in [11]. To give proof was the most difficult part, since this problem was open one decade. This proof gives the tools for other similar problems with given minimum degree of vertices. Chapter 7 is dedicated to generalization of the results obtained in Chapters 5 and 6. This chapter consists of 3 section. In section 7.1 are considered the n-vertex graph G(kNmN n) with given minimum degree k ≥ T 2 , maximum degree m of vertices, where kNm and n are not all odd numbers. Extremal graphs on which Randic´ index attains its minimal value are found. The results from this section are presented in [27]. In section 7.2 are considered graphs from G(kNmN n), k ≥ T 2 , where kNm and n are all odd numbers. From the technical point of view, this section is the more complicated and new mathematical models are also introduced. This section is divided into 4 subsections. Every subsection corresponds to some part of the proof. Extremal graphs are found and the results are presented in [12]. In section 7.3 are considered the graphs from G(kNmN n) for k ≤ T 2 . The results are given in [11]. 99 Literatura [1] M. Aouchiche, P. Hansen, On a conjecture about the Randic´ index, Discrete Mathematics, 307 (2), 2007, 262-265. [2] M. Aouchiche M., Hansen P., Zheng M., Variable Neighborhood Search for Extremal Graphs. 18. Conjectures and Results about the Randic´ Index, MATCH - Communications in Mathematical and in Computer Chemistry, 56 (2006), 541-550. [3] Aouchiche M., Hansen P., Zheng M., Variable Neighborhood Search for Extre- mal Graphs. 19. Further Conjectures and Results about the Randic´ Index, MATCH - Communications in Mathematical and in Computer Chemistry, 58 (2007), 83-102. [4] B. Bolloba´s, P. Erdo˝s, Graphs of Extremal Weights, Ars Combinatoria 50 (1998), 225 - 233. [5] G. Caporossi, I. Gutman, P. Hansen, Variable Neighborhood Search for Extre- mal Graphs IV:Chemical Trees with Extremal Connectivity Index, Computers & Chemistry, 23 (1999), 469 - 477. [6] G. Caporossi, I. Gutman, P. Hansen, Lj. Pavlovic´, Graphs with maximum con- nectivity index, Computational Biology and Chemistry, 2003, 27, 85-90. [7] G. Caporossi, P. Hansen, Variable Neighborhood for Extremal graphs I. The System AutoGraphix, Discrete Mathematics, 212 (2000), 29-44. [8] L.H. Clark, J.W. Moon, On the general Randic´ Index for Certain Families of Trees, Ars Combinatoria 54 (2000), 223-235. [9] D. Cvetkovic´, M. Cˇangalovic´, Dj. Dugosˇija, V. K.-Vujcˇic´, S. Simic´, J.Vuleta, Kombinatorna Optimizacija, Drusˇtvo operacionih istrazˇivacˇa, Beograd, (1996). [10] C. Delorme, O. Favaron, D. Rautenbach, On the Randic´ index, Discrete Mat- hematics, Vol. 257(2002), Issue 1, 29-38. [11] T. Divnic´, Lj. Pavlovic´, Proof of the first part of the conjecture of Aouchiche and Hansen about the Randic´ index, Discrete Applied Mathematics, Volume 161, Issues 7-8, May 2013, Pages 953-960. 100 LITERATURA [12] T. Divnic´, Lj. Pavlovic´, B. Liu, Extremal graphs for the Randic´ index when minimum, maximum degree and order of graph are odd, submitted to the jo- urnal. [13] T. Divnic´, M. Milivojevic´, Lj. Pavlovic´, Extremal graphs for the geometric- arithmetic index with given minimum degree, submitted to the journal. [14] S. Fajtlowicz (1998), Written on the Wall, Conjectures derived on the basis of the program Galatea Gabriella Graffiti, University of Houston. [15] I.Gutman, B. Furtula, Recent Results in the Theory of Randic´ index, Mathe- matical Chemistry Monographs No. 6, Kragujevac, 2008. [16] I. Gutman, Lj. Pavlovic´, O. Miljkovic´, On graphs with extremal connectivity indices, Bulletin de l’Academie Serbe des Sciences et des Arts, 2000, 24, 1-14. [17] P. Hansen, D. Vukicevic´, Variable Neighborhood Search for Extremal Graphs. 23. On the Randic´ index and the chromatic number, Discrete Mathematics,Vol. 309 (2009), Issue 13,pp. 4228-4234. [18] P. Hansen, N. Mladenovic´, Variable Neighborhood Search: Principles and Ap- plications, European Journal of Operations Research, 130 (2001), 449-467. [19] P. Hansen, H. Me´lot, Variable Neighborhood Search for Extremal Graphs VI: Analyzing bounds for the connectivity index, J. Chem. Inf. Comput. Sci. 43 (2003), 1-14. [20] L.B. Kier, L.H. Hall, Molecular Connectivity in Chemistry and Drug Research, Academic Press, New York (1976). [21] L.B. Kier, L.H. Hall, The Nature of Structure-Activity Relationships and their Relation to Molecular Connectivity, European Journal of Medicinal Chemistry, 12, 307-312 (1977b). [22] L.B. Kier, L.H. Hall, Molecular Connectivity in Structure-Activity Analysis, Research Studies Press-Wiley, Chichester (UK) (1986). [23] X. Li, I. Gutman, Mathematical Aspects of Randic´-Type Molecular Structure Descriptors, Mathematical Chemistry Monographs No. 1, Kragujevac, 2006. [24] X. Li, B. Liu, J. Liu, Complete solution to a conjecture on Randic´ index, European Journal of Operational Research, Vol. 200, Issue 1, 1 January 2010, 9-13. [25] X. Li, Y. Shi, Some new results on a conjecture about the Randic´ index, Mathe- matical Chemistry Monographs No. 6, Recent Results in the Theory of Randic´ index, Kragujevac, 2008, pp. 57-72. [26] N. Limic´, H. Pas˘agic´, C˘. Rnjak, Linearno i nelinearno programiranje, Informa- tor, Zagreb (HR)( 1978) 101 LITERATURA [27] B. Liu, Lj. Pavlovic´, T. Divnic´, J. Liu, M. Stojanovic´, On the conjecture of Aouchiche and Hansen about the Randic´ index,Discrete Mathematics, Vol. 313, Issue 3, 6 February 2013, 225-235. [28] Lj. Pavlovic´, I. Gutman, Graphs with Extremal connectivity index, Novi Sad J. Math, 2001, Vol. 31, No. 2, 53-58. [29] Lj. Pavlovic´, Maximal value of the zeroth-order Randic´ index, Discrete Applied Mathematics, 127 (2003), 615-626. [30] Lj. Pavlovic´, Graphs with extremal Randic´ index when the minimum degree of vertices is two, Kragujevac Journal of Mathematics, 25 (2003), 55-63. [31] Lj. Pavlovic´, On the conjecture of Delorme, Favaron and Rautenbach about the Randic´ index, European Journal of Operational Research , 2007, Vol. 180, Issue 1, pp. 369-377. [32] Lj. Pavlovic´, The linear Programming approach to the Randic´ index, ITOR - International Transactions in Operational Research, November 2007, Vol. 14, Issue 6, pp. 535-545. [33] Lj. Pavlovic´, T. Divnic´, A quadratic programming approach to the Randic´ index, European Journal of Operational Research, 2007, Vol. 176, Issue 1, pp. 435-444. [34] Lj. Pavlovic´, Comment on ”Complete solution to a conjecture on Randic´ index”, European Journal of Operational Research, Vol. 207, Issue 1, 16 November 2010, pp. 539-542. [35] M. Randic´, On characterization of molecular branching, J. Am. Chem. Soc., 97 (1975), 6609 -6615. [36] V. Vujcˇic´, M. Asˇic´, N. Milicˇic´, Matematicˇko programiranje, Matematicˇki Insti- tut, Beograd (1980). [37] D. Vukicˇevic´, B. Furtula, Topological index based on the ratios of geometrical and arithmetical means of end -vertex degrees of edges, Journal of Mathematical Chemistry, Vol. 46, Issue 2 (2009), 1369-1376. 102 Biografija Tomica Divni} je ro|en 01.01.1969. godine u Obre`u, od oca Radivoja i majke Dragice. Osnovnu {kolu zavr{io je u rodnom mestu. Prva dva razreda sred- we usmerenog obrazovawa je zavr{io u Varvarinu, a tre}i i ~etvrti razred u Trsteniku 1988. godine. Iste godine se upisuje na studijsku grupu Matematika Prirodno-matemati~kog fakulteta Univerziteta u Kragujevcu. Posle odslu`ewa vojnog roka prvu godinu slu{a {kolske 1989/90. godine, a s obzirom na postignut uspeh iste godine biva progla{en za najboqeg studenta Prirodno-matemati~kog fakulteta u Kragujevcu. Diplomira, za prose~nom ocenom 9.25, dana 29.06.1993. godine i sti~e zvawe Diplomirani matemati~ar za ra~unarstvo i informatiku. Godine 1995. se `eni sa Nevenkom, tako|e profesorom matematike. U sre}nom braku imaju dvoje dece Nemawu i Nikolu. Poslediplomske studije Tomica je zavr{io, na Prirodno-matemati~kom fa- kultetu u Kragujevcu, 21.02.2000. godine odbranom magistarske teze pod nazivom: "Neke primene operatora za nala`ewe pribli`nog re{ewa obi~nih diferenci- jalnih jedna~ina i sistema diferencijalnih jedna~ina". Od oktobra 1993. godine do 31.10.2003. godine radi na PMF-u u Kragujevc. Novembra 1994. godine je izabran za asistenta-pripravnika. Dr`ao je vezbe iz slede}ih predmeta: nacrtna geometrija, algebra 1, diferencijalne jedna~ine, te- orija funkcija kompleksne promenqive, operaciona istra`ivawa, analiza 1, na studijskoj grupi matematika, i matematika 2 na grupi fizika. U zvawe asistenta izabran je 2000. godine. Iz porodi~nih razloga pre{ao je da radi 01.11.2003. godine u Sredwu {kolu u Varvarinu. Tomica je bio anga`ovan na dva projektaMinistarstva za nauku. Anga`ovawe na projektu mu je prekinuto 2003. godine, kada je pre{ao u Sredwu {kolu. U svom nau~no-istra`iva~kom radu izu~ava vi{e oblasti, a najvi{e uspeha ima bave}i se problemima odre|ivawa ekstremnih vrednosti Randi}evog indeksa na grafovima. Spisak nau~nih radova 1. Tomica Divnic´, An estimation of approximation for the solution of ordinary dif- ferential equations, Mathematica, 4, (2000), pp.21-26, ISSN: 1450-5932, M52. 2. Tomica Divnic´, Zlata Djuric´, A generalization of the Riesz potential, Kragu- jevac Journal of Mathematics, 22(2000), pp.83-86, ISSN: 1450-9628, M51. 3. Tomica Divnic´, On approximative solutions of some differential equations by 103 BIOGRAFIJA means of Bernstein polynomials, Univ. Beograd, Publ. Electrotehn. Fak., 12, (2001), pp.12-15, ISSN 0353-8893, M51. (Sada: Applicable Analysis and Discrete Mathematics, ISSN 1452-8630). 4. Ljiljana Pavlovic´, Tomica Divnic´, A quadratic programming approach to the Randic´ index, European Journal of Operational Research, Vol. 176, Issue 1, (2007), pp.435-444, ISSN: 0377-2217, M21. 5. T. Divnic´, Lj. Pavlovic´, A slight modification of the first phase of the simplex algorithm, Yugoslav Journal of Operation Research, Vol.22 (2012), Number 1, 107-114, M51. 6. B. Liu, Lj. Pavlovic´, T. Divnic´, J. Liu, M. Stojanovic´, On the conjecture of Aouchiche and Hansen about the Randic´ index, Discrete Mathematics, Vol. 313, Issue 3, 6 February 2013, 225-235, M23. 7. T. Divnic´, Lj. Pavlovic´, Proof of the first part of the conjecture of Aouchiche and Hansen about the Randic´ index, Discrete Applied Mathematics, Volume 161, Issues 7-8, May 2013, Pages 953-960, M22 8. T. Divnic´, Lj. Pavlovic´, B. Liu, Extremal graphs for the Randic´ index when minimum, maximum degree and order of graph are odd, submitted to the journal. 9. T. Divnic´, M. Milivojevic´, Lj. Pavlovic´, Extremal graphs for the geometric- arithmetic index with given minimum degree, submitted to the journal. U~e{}e na konferencijama 1. Vladimir Savic´, Tomica Divnic´, Generalization of Riesz potentials, Volume of Abstract, 4th Symposium on mthematical analysis and its applications, Arand¯elovac, May 26-30, 1997, pp.65. 2. Tomica Divnic´, On p-convex functions, Volume of Abstract, 10th Congress of Yugoslav mathematicians, Belgrade, October 8-11, 2000, pp.40. 3. Tomica Divnic´, A method of solving differential equations, Volume of Abstract, 10th Congress of Yugoslav mathematicians, Belgrade, October 8-11, 2000, pp.40. 104