adjacency matrix

adjacency matrix (tsz. adjacency matrixes)

1. (informatika) szomszédsági mátrix, adjacenciamátrix

Az adjacency matrix, vagy magyarul szomszédsági mátrix, egy mátrix-alapú reprezentációja egy gráfnak, amely megmutatja, hogy az egyes csúcsok között van-e él vagy kapcsolat.

• Egy ${\textstyle n\times n}$ méretű négyzetes mátrix, ahol ${\textstyle n}$ a gráf csúcsainak száma.

• A mátrix ${\textstyle A}$ elemei:

  $${\displaystyle A_{ij}={\begin{cases}1,&{\text{ha van él az }}i{\text{-edik és }}j{\text{-edik csúcs között}}\\0,&{\text{különben}}\end{cases}}}$$

• Súlyozott gráf esetén az érték az él súlya lehet, vagy nulla, ha nincs él.

• Irányított gráf esetén: a mátrix nem feltétlenül szimmetrikus.
• Irányítatlan gráfnál: a mátrix szimmetrikus.
• Könnyen lekérdezhető az adott csúcs szomszédsága (a sor vagy oszlop alapján).

• Egyszerű és közvetlen reprezentáció.
• Könnyű implementálni.
• Gyors hozzáférés a csúcsok közti kapcsolatokhoz.

• Nagy memóriát igényel ritkás gráfok esetén (${\textstyle O(n^{2})}$).
• Nem hatékony nagy, ritkás gráfok tárolására.

A szomszédsági mátrix egy alapvető és egyszerű módja a gráfok ábrázolásának, amelyben a csúcsok közti kapcsolatok mátrixban vannak kódolva. Hasznos kis vagy sűrű gráfok esetén, de nagy, ritka gráfoknál más struktúrák (pl. szomszédsági lista) hatékonyabbak.

• adjacency matrix - Szótár.net (en-hu)
• adjacency matrix - Sztaki (en-hu)
• adjacency matrix - Merriam–Webster
• adjacency matrix - Cambridge
• adjacency matrix - WordNet
• adjacency matrix - Яндекс (en-ru)
• adjacency matrix - Google (en-hu)
• adjacency matrix - Wikidata
• adjacency matrix - Wikipédia (angol)