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 A_ij është një kur ka një skaj nga kulmi u i në kulmin u_j, dhe zero kur nuk ka brinjë. ^[1] 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ë
	${\begin{pmatrix}2&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\end{pmatrix}}$ Koordinatat janë 1–6.
Grafi Nauru	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 A_ij 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). ^[2] 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ë. ^[3]

Grafi i etiketuar	Matrica e fqinjësisë
Një graf i Cayley-t i drejtuar me S ₄	Koordinatat janë 0–23. Ndërsa grafiku është i drejtuar, matrica nuk është domosdoshmërisht simetrike .

^ Biggs, Norman (1993), Algebraic Graph Theory, Cambridge Mathematical Library (bot. 2nd), Cambridge University Press, Definition 2.1, p. 7 {{citation}}: Mungon ose është bosh parametri |language= (Ndihmë!).
^ Borgatti, Steve; Everett, Martin; Johnson, Jeffrey (2018), Analyzing Social Networks (bot. 2nd), SAGE, p. 20 {{citation}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Newman, Mark (2018), Networks (bot. 2nd), Oxford University Press, p. 110 {{citation}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[1] Biggs, Norman (1993), Algebraic Graph Theory, Cambridge Mathematical Library (bot. 2nd), Cambridge University Press, Definition 2.1, p. 7 {{citation}}: Mungon ose është bosh parametri |language= (Ndihmë!).

[2] Borgatti, Steve; Everett, Martin; Johnson, Jeffrey (2018), Analyzing Social Networks (bot. 2nd), SAGE, p. 20 {{citation}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[3] Newman, Mark (2018), Networks (bot. 2nd), Oxford University Press, p. 110 {{citation}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[1]

[2]

[3]