Teoria e grafeve

Grafi G quhet çifti I renditur(V,E) ku V është një bashkësi joboshe,kurse E një familje e nënbashkësish të V.Elementet e V quhet kulme(nyje) ndërsa ato të E quhen degë(brinjë).Dega e cila lidh nyjat u dhe v shënohet me {u,v }, u-v, ose ndonjë shënim tjetër.Gjeometrikisht,degët shënohen me lakore harkore ose me segmente.Dy nyje u dhe v janë fqinje nëse ekziston një degë e={u,v} e cila I lidh ato.Dega e cila fillon dhe mbaron në të njëjtën nyje quhet llupë(lak).Në figurën 3 janë paraqitur dy grafe.

Historiku

Qyteti I Konisgberg-ut në Prusinë lindore shtrihet në lumin Pregel(figura 1 ).Ai përmbanë brigjet A dhe C të lumit dhe ishujt B dhe D.Këto katër sipërfaqe tokësore janë të lidhura me shtatë ura.

Banorët e qytetit mbrëmjeve kanë shëtitur nga njëra ane e qytetit në anën tjetër.Është parashtruar pyetja:A është e mundur të shëtitet nga njëra ane e lumit në anën tjetër duke kaluar secilën urë vetëm një herë? Më 1736 Euleri publikoi zgjidhje e problemit:Asnjë shëtitje e tillë nuk është e mundur.Në fakt, ai vertetoi rezultate shumë të rëndësishme,nga të cilat problem I Konisbergut është rast special.Euleri konstruktoi modelin matematikor si në figurën 2 për problemin ku pika A dhe C paraqesin brigjet e lumit ,B dhe D dy ishujt.Lakoret që bashkojnë këto pika paraqesin shtatë urat.

Një figurë e tillë quhet graf.

Kuptimet themelore të teorisë së grafeve

Grafi(grafi jo I orientuar) G përbëhet nga:

Bashkësia e fundme dhe jo e zbrazët V e pikave, të quajtura nyje ose kulme
Bashkësia e fundme E e degëve ose brinëve
Funksioni δ:E→P(V) ashtu që, për çdo degë e ∈ E, δ(e) është nënbashkësi një ose dy elementëshe e bashkësisë V.

Për v ∈ V,(v)={e ∈ E| v e lidhur me e} quhet përmbajtja e kulmit v,|(v)|-quhet shkallë(fuqi) e kulmit v, shënohet shk(v). Vargu I shkallëve të grafit G është vargu i shkallëve të nyjave të atij grafi të radhitura në trajtë të vargut jozvogëlues.Për shembull,vargu i shkallëve të grafit të paraqitur në figuren 4 është(0,3,3,4).

Hartat e rrugëve ajrore paraqesin një shembull të mirë të grafeve,ku çdo nyje e grafit paraqet një qytet dhe çdo degë një fluturim direct nga një qytet në qytetin tjetër. Digrafi(grafi I orientuar ose grafi me degë të oriëntuara) G=(V,E) është grafi në të cilin çdo degë e={vi,vj} ka drejtimin nga “pika e fillimit” e tij vi në “pikën e mbarimit” vj.Dega{a,a} e cila fillon dhe mbaron në të njëtjën nyje a quheshte llupë.Degët paralele kanë nyje të njëjta.Grafet e thjeshta janë grafet qe nuk përmbajnë as llupa as degë paralele. Grafi te i cili bashkësia E e degëve Është bashkësi e zbrazët quhet zero graf. Le të shënojmë me e numrin e=|E| e degëve të grafit G me n nyjet v1,v2,…,vn.Atëherë

Numri i nyjave me shkallë tek në graf është numër çift.Për shembull,modeli i Konigsberg-ut përmban katër nyje me shkallë tek. Te grafet me degë të orientuara shkalla-hyrëse e nyjes v, që shënohet me shk-(v),është numri I degëve që kanë nyjën v si pikë të fillimit.Shkalla-dalëse e nyjës v,që shënohet me shk+(v),është numri i degëve që kanë nyjën v si pikë të mbarimit. Shuma e shkallëve të nyjeve te grafi i orientuar është:

Shumë nga vetitë e grafeve të orientuara nuk varen nga orientimi i degëve të atij grafi.Prandaj,është e leverdishme që në shumicën e rasteve të injorohet orientimi i degëve.

Nëngrafet e grafit

Grafi G1=(V1,E1) quhet nëngraf i grafit G=(V,E) nëse V1 është nënbashkesi e V, E1 e E dhe

Kushti δG(e)= δG(e), për për çdo degë e ϵ G1, thjeshtë do të thotë se degët e nëngrafit G1 duhet të shoqërohen nga të njëjtat nyje sikur në grafin G.Thënë ndryshe, G1 është nëngraf i grafit G nëse diagram i G1 mund të fitohet duke përjashtuar disa nga nyjat ose degët nga diagram G. Kuptohet, nëse përjashtojmë një nyje atëherë duhet të përjashtohen të gjitha degët që janë të lidhura me atë nyje.

Grafikët

Graf komplet(i përsosur) quhet grafi i thjeshtë te i cili çdo nyje është e lidhur me çdo nyje tjetër të grafit. Grafi komplet me n nyje shënohet me Kn. Numri i degëve te grafi komplet Kn është I barabartë me m= (n(n-1))/2 = (n¦2), dmth çdo çift i nyjeve është i lidhur me një degë dhe çdo nyje ka shkallën n-1. Shembull.(Problemi me shtrëngim duarsh).Në festën e një njëqind vjetori, secili nga n të ftuarit ka përshëndetur secilin person tjetër me shtrëngim duarsh saktësisht vetëm një herë.Sa përshëndetje me shtrëngim duarsh janë bërë? Grafi G quhet graf rregullar I shkallës k ose k-rregullar, në qoftë se çdo nyje e atij grafi ka shkallën k. Me fjalë të tjera, grafi është rregullar, në qoftë se çdo nyje ka shkallë të njëtjë. Çdo graf komplet me n nyje është (n-1)-rregullar.

Grafet ciklike dhe grafet komplementare

Grafet ciklike (n-kulmësh) Cn me gjatësi n (n ≥3)përbëhet prej n nyjave v1,v2,…,vn dhe degëve { vi,vi+1} ku 1≤i ≤ n dhe vn+1= v1.Grafi komplementar i grafit G quhet grafi H që i ka nyjet e njëjta me grafin G dhe te i cili nyjat janë të lidhura në qoftë se dhe vetëm në qoftë se nuk janë të lidhura në grafit G.

Grafet rrotë:

Lidhshmëria

Në shumicën e rasteve grafet janë “njëpjesësh”,mirëpo ka raste kur grafi është ndërtuar nga disa pjesë. Te rrjetat kompjuterike, çdo kompjuter mund të komunikojë me çdo kompjuter tjetër. Në qoft se rruga shkon nga çdo nyje(kompjuter) në tjetër,për grafin e tillë themi se është i lidhur. Pra grafi është i lidhur,nëse çdo dy kulme të tij janë të lidhur. Për dy kulme themi se janë të lidhur, nëse ekziston rruga në mes të çdo dy nyjave të ndryshme të grafit; në të kundërtën grafi është jo I lidhur.Në figurën 9 janë paraqitur dy grafe jot ë lidhura.

Grafi I Eulerit

Le të jetë G grafi i lidhur. Rrugë e Eulerit është rruga e cila përfshin çdo degë të G vetëm një herë( graf semi-Eulerian).Qark I Eulerit është rruga e Eulerit për të cilën nyja e parë dhe e fundit përputhen (graf i Eulerit). Për grafin e lidhur G ekziston një kusht i nevojshëm i cili mundëson që të vërehet shumë lehtë ekzistenca e rrugës së Eulerit:

1.Çdo nyje duhet të jetë e shkallës çift. Prandaj banorët e Konigsberg-ut për një arsye shumë të qartë nuk kanë pasur mundësi që të gjejnë rrugën e tyre të Eulerit-sepse nuk ka ekzistuar.

2.Çdo graf I lidhur me më shumë se dy nyje me shkallë tek nuk mund të ketë rrugë të Eulerit. 3.Nëse saktësisht dy nyje të G kanë shkallë teke,atëherë G është semieulerian, dhe çdo rrugë e Eulerit në G duhet të fillojë në njërën nyje me shkallë tek dhe mbaron në tjetrën.

Grafi I Hamiltonit

Le të jetë G graf i lidhur. Rrugë e Hamiltonit është rruga e cila përmban çdo nyje të G saktësisht vetëm një herë,përveç se nyja e parë dhe e fundit mund të përputhen. Qark i Hamiltonit është rruga e Hamiltonit për të cilën nyja e parë dhe e fundit përputhen. Grafi i lidhur që ka qark të Hamiltonit quhet graf I Hamiltonit. Vërejmë se rruga e Hamiltonit nuk është e thënë që ti përmbajë të gjitha degët e grafit.Grafi i Hamiltonit mund të ketë rrugë të Hamiltonit por jo edhe e kundërta. Nuk mund të përcaktohet nëse një graf I lidhur përmban qark të Hamiltonit.Gjetja e një testi që përcakton këtë mbetet një problem I madh dhe I pazgjidhur në teorinë e grafeve. Megjithatë,ekzistojnë disa kushte të mjaftueshme që grafi I lidhur të jetë graf I Hamiltonit por jo edhe të nevojshme.dy nga kushtet janë: Teorema e Dirac-ut –Grafi I thjeshtë dhe I lidhur G me n≥ 3 nyje është graf I Hamiltonit nëse

Teorema e Ore-sit-Le të jetë G graf i thjeshtë dhe i lidhur ne n≥ 3 nyje. Në qoftë se shk(u)+shk(v) ≥ n për çdo çift të nyjave jo të lidhura u dhe v, atëherë G është graf I Hamiltonit.