Teoria e grafeve

Grafet janë struktura diskrete të përbëra nga kulme dhe skaje që lidhin këto kulme. Ekzistojnë lloje të ndryshme grafesh, në varësi të faktit nëse skajet kanë drejtime, nëse skajet e shumëfishta mund të lidhin të njëjtin çift kulmesh dhe nëse lejohen sythe. Problemet pothuajse në çdo disiplinë të imagjinueshme mund të zgjidhet duke përdorur modele grafike.

Grafe dhe modelet e grafeve.

Fillojmë me përkufizimin e një grafiku.

Perkufizimi 1

Një graf G = (V, E) përbëhet nga V, një grup kulmesh (ose nyjesh) jo bosh dhe E, një grup skajesh. Çdo skaj ka një ose dy kulme të lidhura me të, të quajtura pikat e tij fundore. Një skaj është thuhet se lidh pikat e saj fundore.

Vërejtje: Bashkësia e kulmeve V të një grafi G mund të jetë e pafundme. Një graf me një kulm të pafundme grup ose një numër i pafund i skajeve quhet graf i pafund, dhe në krahasim, një graf me një bashkësi kulmore e fundme dhe një grup skajesh të fundme quhet graf i fundëm.

Tani supozoni se një rrjet përbëhet nga qendra të dhënash dhe lidhje komunikimi ndërmjet tyre kompjuterët. Ne mund të përfaqësojmë vendndodhjen e çdo qendre të dhënash me një pikë dhe çdo komunikim lidhje me një segment vije..Ky rrjet kompjuterik mund të modelohet duke përdorur një graf në të cilin kulmet e grafikut përfaqësojnë qendrat e të dhënave dhe skajet përfaqësojnë lidhjet e komunikimit. Në përgjithësi, ne vizualizojmë grafet duke përdorur pika për të përfaqësuar kulmet dhe segmente të vijës, ndoshta të lakuara, për të përfaqësuar skajet, ku pikat fundore të një segmenti të vijës që përfaqëson një skaj janë pikat që përfaqësojnë skajet e skajit. Kur vizatojmë një graf, në përgjithësi përpiqemi të vizatojmë skajet në mënyrë që ato të bëjnë jo kryq. Megjithatë, kjo nuk është e nevojshme sepse çdo përshkrim që përdor pika për të përfaqësuar kulmet dhe mund të përdoret çdo formë e lidhjes ndërmjet kulmeve. Në të vërtetë, ka disa grafikë që nuk mund të vizatohet në plan pa kryqëzimin e skajeve. Pika kryesore është se mënyra se si vizatojmë një graf është arbitrare, përderisa janë lidhjet e sakta midis kulmeve

Përkufizimi 2 Një graf (ose digraf) i drejtuar (V, E) përbëhet nga një grup jo bosh kulmesh V dhe një grup skajet e drejtuara E. Çdo skaj i drejtuar shoqërohet me një çift të renditur kulmesh. Buza e drejtuar e lidhur me çiftin e renditur (u, v) thuhet se fillon në u dhe mbaron në v.

Kur përshkruajmë një graf të drejtuar me një vizatim vijash, ne përdorim një shigjetë që tregon nga u në v në tregoni drejtimin e një skaji që fillon në u dhe përfundon në v. Një graf i drejtuar mund të përmbajë sythe dhe mund të përmbajë skaje të shumta të drejtuara që fillojnë dhe përfundojnë në të njëjtat kulme. Një e drejtuar grafiku mund të përmbajë gjithashtu skaje të drejtuara që lidhin kulmet u dhe v në të dy drejtimet; kjo eshte, kur një digraf përmban një skaj nga u në v, ai gjithashtu mund të përmbajë një ose më shumë skaje nga v në u. Vini re se marrim një graf të drejtuar kur i caktojmë një drejtim çdo skaji në një të padrejtuar grafiku. Kur një graf i drejtuar nuk ka unaza dhe nuk ka skaje të shumëfishta të drejtuara, ai quhet a graf i thjeshtë i drejtuar. Sepse një graf i thjeshtë i drejtuar ka më së shumti një skaj të lidhur me secilin çifti i renditur i kulmeve (u, v), ne quajmë (u, v) një skaj nëse ka një skaj të lidhur me të në graf. Në disa rrjete kompjuterike, mund të ketë lidhje të shumta komunikimi ndërmjet dy qendrave të të dhënave të jetë i pranishëm. grafet e drejtuar që mund të kenë skaje të shumëfishta të drejtuara nga një kulm në një kulm të dytë (ndoshta i njëjtë) përdoren për të modeluar rrjete të tilla. ne quhen grafikë të tillë multigrafë të drejtuar. Kur ka skaje m të drejtuara, secila e lidhur me një çift i renditur kulmesh (u, v), themi se (u, v) është një skaj i shumëzimit m. Për disa modele mund të na duhet një graf ku disa skaje janë të padrejtuara, ndërsa të tjerat janë i drejtuar.Agrafi me brinjë të drejtuar dhe të padrejtuar quhet graf i përzier.

Tabela 1 Terminologjia e grafikut
Lloji	skajet	A lejohen skajet e shumëfishta?
Grafi i thjeshte	I padrejtuar	Jo
Multigraf	I padrejtuar	Po
Pseudograf	I padrejtuar	Po
graf i thjeshtë i drejtuar	Drejtuar	Jo
Multigraf i drejtuar	Drejtuar	Po
graf i përzier	Drejtuar dhe i padrejtuar	Po

Teoria e Grafëve

grafet paraqesin metoda natyrore dhe të mira për modelimin e marrëdhënieve jolineare. Veprimet me grafikë janë më komplekse sesa me strukturat e tjera .Në matematikë, dhe më konkretisht në teorinë e grafikëve, një graf është një strukturë që përbën një grup objektesh në të cilat disa çifte objektesh janë në njëfarë kuptimi "të lidhura". Objektet korrespondojnë me abstraksionet matematikore të quajtura kulme dhe secila nga çiftet e lidhura të kulmeve quhet një skaj. Në mënyrë tipike, një graf përshkruhet në formë diagrami si një grup pikash ose rrathësh për kulmet, të bashkuara me vija ose kthesa për skajet. grafet janë një nga objektet e studimit në matematikën diskrete.Skajet mund të jenë të drejtuara ose të padrejtuara. Për shembull, nëse kulmet përfaqësojnë njerëzit në një festë dhe ka një avantazh midis dy njerëzve nëse shtrëngojnë duart, atëherë ky graf është i padrejtuar sepse çdo person A mund të shtrëngojë dorën me një person B vetëm nëse B shtrëngon gjithashtu dorën me A. Në të kundërt, nëse ndonjë skaj nga një person A te një person B korrespondon me A i detyrohet para B, atëherë ky graf është i drejtuar, sepse borxhi i parave nuk është domosdoshmërisht reciprok. Lloji i parë i grafikut quhet graf i padrejtuar ndërsa lloji i dytë i grafikut quhet graf i drejtuar. Grafi 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).

Një graf bosh është një graf që ka një grup bosh kulmesh. Rendi i një grafi është numri i kulmeve të tij |V|. Madhësia e një grafiku është numri i skajeve të tij |E|. Megjithatë, në disa kontekste, si për shprehjen e kompleksitetit llogaritës të algoritmeve, madhësia është |V| + |E| (përndryshe, një graf jo bosh mund të ketë një madhësi 0). Shkalla ose valenca e një kulmi është numri i skajeve që ndodhen me të. Nëse (V,E) është graf i orientuar,atëherë vlenë: $\sum _{v\epsilon V}deg^{-}(V)=\sum _{v\epsilon V}deg^{+}(V)=|E|$

Historiku i grafeve

Historia e teorisë së grafikut mund të gjurmohet në mënyrë specifike në 1735, kur matematikani zviceran Leonhard Euler zgjidhi problemin e urës Königsberg. Problemi i urës Königsberg ishte një enigmë e vjetër në lidhje me mundësinë e gjetjes së një shtegu mbi secilën nga shtatë urat që përshkojnë një lumë të dyfishtë që kalon një ishull - por pa kaluar asnjë urë dy herë. Euler argumentoi se një rrugë e tillë nuk ekziston. Prova e tij përfshinte vetëm referenca për rregullimin fizik të urave, por në thelb ai vërtetoi teoremën e parë në teorinë e grafikëve.

Ura e Konisgbergut.

Disa grafikë të thjeshtë

Tani do të prezantojmë disa klasa të grafikëve të thjeshtë. Këta grafikë shpesh përdoren si shembuj dhe lindin në shumë aplikime. SHEMBULL: grafet e plotë Një graf i plotë në n kulme, i shënuar me Kn, është një graf i thjeshtë që përmban saktësisht një skaj midis çdo çifti kulmesh të dallueshme. grafet Kn, për

n = 1, 2, 3, 4, 5, 6, janë paraqitur në figurën 3. Një graf i thjeshtë për të cilin ka të paktën një palë i kulmit të veçantë që nuk lidhet me një skaj quhet jo i plotë.

Grafi kub

grafet kub, të quajtur edhe grafikë trevalent, janë grafikë, të gjitha nyjet e të cilëve kanë shkallën 3 (d.m.th., grafikë 3 të rregullt). grafet kub në n nyje ekzistojnë vetëm për n çift (Harary 1994, f. 15). grafet kub jo domosdoshmërisht të lidhur në n=4, 6 dhe 8 janë ilustruar më sipër. Një numërim i grafikëve kub në n nyje për n të vogla zbatohet në gjuhën Wolfram si GraphData["Cubic", n]. Një kriter i domosdoshëm (por jo i mjaftueshëm) që një graf të jetë kub është ai m/n=3/2, ku m është numërimi i skajeve dhe n është numri i kulmeve. Numrat e grafikëve kub jo domosdoshmërisht të lidhur në nyjet 2, 4, 6, ... janë 0, 1, 2, 6, 21, 94, 540, 4207, ... (OEIS A005638; Robinson dhe Wormald 1983) . Grafiku unik kub me 4 nyje është grafiku i plotë K_4 (grafi tetraedral). Dy grafet kub me 6 nyje janë grafet qarkullues Ci_(1,3)(6) (grafi i dobisë) dhe Ci_(2,3)(6). Tre nga gjashtë grafet kubikë me 8 nyje janë grafet kub dhe grafikë qarkullues Ci_(1,4)(8) dhe Ci_(2,4)(8). grafet kub të lidhur janë përcaktuar nga Brinkmann (1996) deri në 24 nyje, dhe numrat e grafikëve të tillë për n=2, 4, ... janë 0, 1, 2, 5, 19, 85, 509, 4060, 41301, ... (OEIS A002851). Meringer dhe Royle mbajnë në mënyrë të pavarur numërimin e grafikëve kub të e kafazit janë kub. Përveç kësaj, tabelat e mëposhtme japin disa grafikë të emërtuar që janë skelete poliedrikësh.^[1]

Grafi kub

Grafet bipartite

Në fushën matematikore të teorisë së grafikëve, një graf (ose bigraf) dypalësh është një graf kulmet e të cilit mund të ndahen në dy grupe të shkëputura dhe të pavarura ${U}$ dhe ${V}$ ashtu që çdo skaj të lidh një kulm në ${U}$ në një në ${V}$ . Kompletet kulmor ${U}$ dhe ${V}$ zakonisht quhen pjesë të grafikut. Në mënyrë ekuivalente, një graf bipartit është një graf që nuk përmban asnjë cikël me gjatësi tek.

Dy grupet ${U}$ dhe ${V}$ mund të mendohen si një ngjyrosje e grafikut me dy ngjyra: nëse një ngjyros të gjitha nyjet në ${U}$ blu dhe të gjitha nyjet në ${V}$ jeshile, çdo skaj ka pika fundore me ngjyra të ndryshme, siç kërkohet në problemin e ngjyrosjes së grafikut. Në të kundërt, një ngjyrosje e tillë është e pamundur në rastin e një grafiku jo dypalësh, siç është një trekëndësh: pasi një nyje është ngjyrosur blu dhe një tjetër jeshile, kulmi i tretë i trekëndëshit lidhet me kulmet e të dyja ngjyrat, duke mos lejuar që t'i caktohet ndonjë ngjyrë.

Një graf i plotë bipartit me m = 5 dhe n =

Gjatë modelimit të marrëdhënieve ndërmjet dy klasave të ndryshme të objekteve, grafet dypalësh shumë shpesh lindin natyrshëm. Për shembull, një graf i futbollistëve dhe klubeve, me një skaj midis një lojtari dhe një klubi nëse lojtari ka luajtur për atë klub, është një shembull natyror i një rrjeti anëtarësimi, një lloj grafiku dypalësh i përdorur në analizën e rrjeteve sociale.

Për një kulm, numri i kulmeve ngjitur quhet shkalla e kulmit dhe shënohet $deg(v)$ . Formula e shumës së shkallës për një graf dypalësh thotë se:

$\sum _{v\in V}deg(v)=\sum _{v\in V}deg(u)=|E|$

Matrica e fqinjësisë

Në teorinë e grafikëve dhe shkencën kompjuterike, një matricë fqinjësie është një matricë katrore e përdorur për të përfaqësuar një graf të fundëm. Elementet e matricës tregojnë nëse çiftet e kulmeve janë ngjitur ose jo në grafik.Në rastin e veçantë të një grafi të thjeshtë të fundëm, matrica e fqinjësisë është një matricë (0,1) me zero në diagonalen e saj. Nëse grafiku është i padrejtuar (d.m.th., të gjitha skajet e tij janë me dy drejtime), matrica e fqinjësisë është simetrike. Marrëdhënia midis një grafiku dhe eigenvlerave dhe eigenvektorëve të matricës së tij të afërsisë studiohet në teorinë e grafikut spektral.

Matrica e afërsisë së një grafiku duhet të dallohet nga matrica e saj e incidencës, një paraqitje e ndryshme matrice, elementët e së cilës tregojnë nëse çiftet kulm – skaj janë incidente apo jo, dhe matrica e shkallës së saj, e cila përmban informacion për shkallën e secilës kulm.

Matrica simetrike

Izometria e grafeve

Në teorinë e grafikëve, një izomorfizëm i grafëve G dhe H është një bijeksion midis grupeve të kulmeve të G dhe H

$\int :V(G)\rightarrow V(H)$

të tilla që çdo dy kulme u dhe v të G janë ngjitur në G nëse dhe vetëm nëse ${f(u)}$ dhe ${f(v)}$ janë ngjitur në H. Ky lloj i bijeksionit zakonisht përshkruhet si "bijeksion i ruajtjes së skajeve", në përputhje me nocionin e përgjithshëm të izomorfizmit që është një bijeksion që ruan strukturën.Nëse ekziston një izomorfizëm midis dy grafikëve, atëherë grafet quhen izomorfikë dhe shënohen si ${G\simeq H}$ . Në rastin kur bijeksioni është një hartë e një grafi në vetvete, dmth, kur G dhe H janë një dhe i njëjti graf, bijeksioni quhet automorfizëm i G.

Izomorfizmi i grafikut është një lidhje ekuivalente në grafikë dhe si e tillë ndan klasën e të gjithë grafëve në klasa ekuivalente. Një grup grafikësh izomorfikë me njëri-tjetrin quhet një klasë izomorfizmi grafikësh.

Dy grafet e paraqitur më poshtë janë izomorfikë, pavarësisht vizatimeve me pamje të ndryshme.

Grafiku izometrik.

Një graf i plotë është një graf në të cilin çdo palë kulme është e bashkuar nga një skaj. Një graf i plotë përmban të gjitha skajet e mundshme.

Një graf i peshuar ose një rrjet është një graf në të cilin një numër (pesha) i caktohet çdo skaji. Pesha të tilla mund të përfaqësojnë për shembull kosto, gjatësi ose kapacitete, në varësi të problemit në fjalë. Grafikë të tillë lindin në shumë kontekste, për shembull në problemet e rrugës më të shkurtër, siç është problemi i shitësit udhëtues.

Një graf planar është një graf kulmet dhe skajet e të cilit mund të vizatohen në një rrafsh të tillë që të mos kryqëzohen dy nga skajet.

Një graf i peshuar me dhjetë kulme dhe dymbëdhjetë skaje.

^ Weisstein, Eric W. "Cubic Graph". mathworld.wolfram.com (në anglisht). Marrë më 2022-02-08.

[1] Weisstein, Eric W. "Cubic Graph". mathworld.wolfram.com (në anglisht). Marrë më 2022-02-08.

[1]