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
[Redakto | Redakto nëpërmjet kodit]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ë. [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
[Redakto | Redakto nëpërmjet kodit]Grafet e padrejtuar
[Redakto | Redakto nëpërmjet kodit]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ë |
---|---|
Koordinatat janë 1–6. | |
Koordinatat janë 0–23. Fushat e bardha janë zero, fushat me ngjyra janë një. |
Grafikët e drejtuar
[Redakto | Redakto nëpërmjet kodit]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). [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 4 |
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ë!)