Grafi

Në matematikën diskrete, dhe më konkretisht në teorinë e grafeve, një graf është një strukturë që përbën një grup objektesh në të cilat disa palë objektesh janë në njëfarë kuptimi "të lidhura". Objektet korrespondojnë me abstraksione matematikore të quajtura kulme (të quajtura gjithashtu nyje ose pika ) dhe secila nga çiftet e lidhura të kulmeve quhet një skaj (i quajtur gjithashtu lidhje ose brinjë ). ^[1] Në mënyrë tipike, një grafik përshkruhet në formë diagrami si një grup pikash ose rrathësh për kulmet, të bashkuara me vija ose kthesa për skajet. Grafikët janë një nga objektet e studimit në matematikën diskrete .

Një graf me gjashtë kulme dhe shtatë skaje

Brinjët mund të jenë të drejtuara ose të padrejtuara. Për shembull, nëse kulmet përfaqësojnë njerëzit në një festë dhe vihet një brinjë 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 një brinjë nga një person A te një person B do të thotë se A i detyrohet para (monedha) B, atëherë ky graf është i drejtuar, sepse borxhi i parave nuk është domosdoshmërisht i ndërsjellë.

Grafikët janë lënda bazë e studiuar nga teoria e grafikëve. Fjala "graf" u përdor për herë të parë në këtë kuptim nga JJ Sylvester në 1878 për shkak të një lidhjeje të drejtpërdrejtë midis matematikës dhe strukturës kimike (ajo që ai e quajti një imazh kimiko-grafik). ^[2] ^[3]

Përkufizimet

Grafi i drejtuar

Një graf i peshuar me dhjetë kulme dhe dymbëdhjetë brinjë

Një graf (ndonjëherë quhet graf i padrejtuar për ta dalluar nga një graf i drejtuar, ose një graf i thjeshtë për ta dalluar nga një multigraf ) ^[4] ^[5] është një çift G = ( V, E ), ku V është një bashkësi elementet e së cilës quhen kulme (njëjës: kulm), dhe E është një grup çiftesh të parenditura $\{v_{1},v_{2}\}$ të kulmeve, elementet e të cilave quhen brinjë (nganjëherë lidhje ose vija ).

Kulmet u dhe v të një brinje {u, v } quhen pika fundore të brinjës. Thuhet se brinja bashkon u dhe v dhe është fqinje me to. Një kulm nuk mund t'i përkasë asnjë brinje, në të cilin rast nuk bashkohet me asnjë kulm tjetër dhe quhet i izoluar . Kur një buzë $\{u,v\}$ ekziston, kulmet u dhe v quhen fqinje .

Ndonjëherë, grafikët lejohen të përmbajnë sythe, të cilat janë skaje që bashkojnë një kulm me vetveten. Për të lejuar sythe, çiftet e kulmeve në E duhet të lejohen të kenë të njëjtën nyje dy herë. Grafe të tilla të përgjithësuara quhen grafikë me sythe ose thjesht grafe kur është e qartë nga konteksti që sythet lejohen.

Grafi

Një graf i drejtuar me tre kulme dhe katër brinjë të drejtuara (shigjeta e dyfishtë përfaqëson një skaj në çdo drejtim)

Një graf ose digraf i drejtuar është një graf në të cilin brinjët kanë orientime.

Në një kuptim të kufizuar, por shumë të zakonshëm të termit, ^[4] një graf i drejtuar është një çift G = ( V, E ) që përfshin:

V, një bashkësi të brinjëve (të quajtura nyje ose pika);
E, një bashkësi e brinjëve (e quajtur brinjë të drejtuara, harqe ose lidhje të drejtuara), që janë çifte të renditura të brinjëve të ndryshme: $E\subseteq \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {dhe}}\;x\neq y\}$ .

Grafi i peshuar

Një graf me tre kulme dhe tre brinjë

Një grafik i peshuar ose një rrjet ^[6] ^[7] është një graf në të cilin çdo brinje i caktohet një numër (pesha). ^[8] Pesha të tilla mund të përfaqësojnë për shembull kosto, gjatësi ose nxënësi, në varësi të problemit në fjalë. Grafe 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 .

Shembuj

Një graf me gjashtë kulme dhe shtatë brinjë

Diagrami është një paraqitje skematike e grafit me kulme $V=\{1,2,3,4,5,6\}$ dhe brinjë $E=\{\{1,2\},\{1,5\},\{2,3\},\{2,5\},\{3,4\},\{4,5\},\{4,6\}\}.$
Në shkencat kompjuterike, grafet e drejtuara përdoren për të përfaqësuar njohuritë (p.sh. grafi konceptual ), makinat me gjendje të fundme dhe shumë struktura të tjera diskrete.
Një relacion binar R në një bashkësi X përcakton një graf të drejtuar. Një element x i X është një paraardhës i drejtpërdrejtë i një elementi y të X nëse dhe vetëm nëse xRy .
Një graf i drejtuar mund të modelojë rrjete informacioni si Twitter, me një përdorues që ndjek (ang. follows) tjetrin. ^[9]
Shembuj veçanërisht të rregullt të grafeve të drejtuar jepen nga grafikët Cayley të grupeve të krijuara në fund të fundit, si dhe nga grafikët e kosetit të Schreier.

Veprime mbi grafe

Ekzistojnë disa veprime që prodhojnë grafe të rinj nga ato fillestare, të cilët mund të klasifikohen në kategoritë e mëposhtme:

operacionet unare, të cilat krijojnë një graf të ri nga një fillestar, si p.sh.
- tkurrja e brinjës ,
- grafi i vijës ,
- grafi i dyfishtë ,
- grafi plotësues ,
- rishkrimi i grafit ;
operacionet binare, të cilat krijojnë një graf të ri nga dy ato fillestare, si p.sh.
- bashkim i shkëputur i grafeve ,
- prodhimi kartezian i grafeve ,
- prodhimi tensorial i grafeve ,
- prodhimi i fortë i grafeve ,
- prodhimi leksikografik i grafeve ,
- grafet seri-paralel .

^ Trudeau, Richard J. (1993). Introduction to Graph Theory (bot. Corrected, enlarged republication.). New York: Dover Pub. fq. 19. ISBN 978-0-486-67870-2. Arkivuar nga origjinali më 5 maj 2019. Marrë më 8 gusht 2012. A graph is an object consisting of two sets called its vertex set and its edge set. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ See:
^ Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. fq. 35. ISBN 978-1-58488-090-5. Arkivuar nga origjinali më 2023-02-04. Marrë më 2016-02-16. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ ^a ^b Bender & Williamson 2010.
^ See, for instance, Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.
^ Strang, Gilbert (2005), Linear Algebra and Its Applications (bot. 4th), Brooks Cole, ISBN 978-0-03-010567-8 {{citation}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Lewis, John (2013), Java Software Structures (bot. 4th), Pearson, fq. 405, ISBN 978-0133250121 {{citation}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). Foundations of Discrete Mathematics (bot. International student). Boston: PWS-KENT Pub. Co. fq. 463. ISBN 978-0-53492-373-0. A weighted graph is a graph in which a number w(e), called its weight, is assigned to each edge e. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Grandjean, Martin (2016). "A social network analysis of Twitter: Mapping the digital humanities community". Cogent Arts & Humanities. 3 (1): 1171458. doi:10.1080/23311983.2016.1171458. Arkivuar nga origjinali më 2021-03-02. Marrë më 2019-09-16. {{cite journal}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[:0-1] Trudeau, Richard J. (1993). Introduction to Graph Theory (bot. Corrected, enlarged republication.). New York: Dover Pub. fq. 19. ISBN 978-0-486-67870-2. Arkivuar nga origjinali më 5 maj 2019. Marrë më 8 gusht 2012. A graph is an object consisting of two sets called its vertex set and its edge set. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[2] See:

[3] Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. fq. 35. ISBN 978-1-58488-090-5. Arkivuar nga origjinali më 2023-02-04. Marrë më 2016-02-16. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[FOOTNOTEBenderWilliamson2010-4] Bender & Williamson 2010.

[5] See, for instance, Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.

[6] Strang, Gilbert (2005), Linear Algebra and Its Applications (bot. 4th), Brooks Cole, ISBN 978-0-03-010567-8 {{citation}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[7] Lewis, John (2013), Java Software Structures (bot. 4th), Pearson, fq. 405, ISBN 978-0133250121 {{citation}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[8] Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). Foundations of Discrete Mathematics (bot. International student). Boston: PWS-KENT Pub. Co. fq. 463. ISBN 978-0-53492-373-0. A weighted graph is a graph in which a number w(e), called its weight, is assigned to each edge e. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[snatwitter-9] Grandjean, Martin (2016). "A social network analysis of Twitter: Mapping the digital humanities community". Cogent Arts & Humanities. 3 (1): 1171458. doi:10.1080/23311983.2016.1171458. Arkivuar nga origjinali më 2021-03-02. Marrë më 2019-09-16. {{cite journal}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]