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ë ).  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 .

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). See: 

 Përkufizimet 

 Grafi i drejtuar 
parapamje| 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 )  See, for instance, Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4. ë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  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ë  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 
parapamje| 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,  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: .

 Grafi i peshuar 
parapamje| Një graf me tre kulme dhe tre brinjë
Një grafik i peshuar ose një rrjet   është një graf në të cilin çdo brinje i caktohet një numër (pesha).  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 
parapamje| Një graf me gjashtë kulme dhe shtatë brinjë

 Diagrami është një paraqitje skematike e grafit me kulme  dhe brinjë 
 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.  
 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 .