Matrica e fqinjësisë

Në teorinë e grafeve 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ë ngjjitur ose jo në graf.

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 (dmth. të gjitha skajet e tij janë me dy drejtime), matrica e fqinjësisë është simetrike . Marrëdhënia midis një grafi dhe eigenvlerave dhe eigenvektorëve të matricës së tij të afërsisë studiohet në teorinë e grafeve spektrale .

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

 Përkufizimi 
Për një graf të thjeshtë me një bashkësi të kulmeve U = { u 1, …, u n }, matrica e fqinjësisë është katrore n × n, A e tillë që elementi i saj Aij është një kur ka një skaj nga kulmi u i në kulmin uj, dhe zero kur nuk ka brinjë. . Elementet diagonale të matricës janë të gjithë zero, pasi skajet nga një kulm në vetvete ( sythe ) nuk lejohen në grafikë të thjeshtë.

 Shembuj 

 Grafet e padrejtuar 
Konventa e ndjekur këtu (për grafet e padrejtuara) është se çdo skaj shton 1 në qelizën e duhur në matricë, dhe çdo lak/syth (një skaj nga një kulm në vetvete) shton 2 në qelizën e duhur në diagonalen në matricë.  Kjo lejon që shkalla e një kulmi të gjendet lehtësisht duke marrë shumën e vlerave në rreshtin ose kolonën përkatëse në matricën e afërsisë.
Grafiku i etiketuar Matrica e fqinjësisë219x219px 

Koordinatat janë 1–6.250x250px 

Grafi Nauru250x250px
Koordinatat janë 0–23. Fushat e bardha janë zero, fushat me ngjyra janë një.

 Grafikët e drejtuar 
Matrica e fqinjësisë së një grafi të drejtuar mund të jetë asimetrike. Mund të përkufizohet matrica e fqinjësisë së një grafi të drejtuar ose të tillë që

 një element jo zero Aij tregon një skaj nga i në j ose
 tregon një skaj nga j në i .

Përkufizimi i parë përdoret zakonisht në teorinë e grafeve dhe analizën e rrjeteve sociale (p.sh. sociologji, shkenca politike, ekonomi, psikologji).  Kjo e fundit është më e zakonshme në shkencat e tjera të zbatuara (p.sh. sistemet dinamike, fizika, shkenca e rrjetit) ku A përdoret ndonjëherë për të përshkruar dinamikën lineare në grafikë. 
Grafi i etiketuar Matrica e fqinjësisë250x250px
Një graf i Cayley-t i drejtuar me S 4250x250px
Koordinatat janë 0–23. Ndërsa grafiku është i drejtuar, matrica nuk është domosdoshmërisht simetrike .