Grafi

parapamje| Një graf me gjashtë kulme dhe shtatë skaje
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).  

## 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 )   ë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 
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: E \subseteq \{(x,y) \mid (x,y) \in V^2 \;\textrm{ dhe }\; x \neq y \}.

### 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 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.  
* 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 .