szomszédsági mátrix

Magyar

Kiejtés

• IPA: [ ˈsomseːt͡ʃːaːɡimaːtriks]

Főnév

szomszédsági mátrix

1. (matematika, gráfelmélet) Egy véges irányított vagy irányítatlan $n$ csúcsú $G$ gráf szomszédsági mátrixa (ritkábban: adjacenciamátrixa) az az $n\times n$-es mátrix, amelynek a nem a főátlóban szereplő $a_{ij}$ eleme az $i$ csúcsból a $j$ csúcsba vezető élek száma, míg a főátlóban található $a_{ii}$, vagy az $i$ csúcsnál lévő hurkok számának kétszerese vagy csak a hurkok száma (az, hogy melyiket használjuk a matematikai felhasználástól függ.

Szomszédsági mátrix definíció

A **szomszédsági mátrix** egy gráf vagy hipergráf reprezentációja, ahol egy mátrix elemei a csúcsok közötti kapcsolatokat írják le. Hagyományos gráf esetén a mátrix sorai és oszlopai a csúcsokat jelölik, míg a mátrix elemei a csúcsokat összekötő élek súlyait vagy meglétét mutatják.

Definíció gráf esetén

Ha a gráf irányítatlan: $$A[i][j]={\begin{cases}1,&{\text{ha van él }}i{\text{ és }}j{\text{ között,}}\\0,&{\text{egyébként.}}\end{cases}}$$ Az irányítatlan gráf szomszédsági mátrixa szimmetrikus.

Ha a gráf irányított: $$A[i][j]={\begin{cases}1,&{\text{ha van irányított él }}i\to j,\\0,&{\text{egyébként.}}\end{cases}}$$

Definíció hipergráf esetén

Hipergráfban a szomszédsági mátrix sora a csúcsok, oszlopa pedig a hiperélek szerint alakul: $$A[i][j]={\begin{cases}1,&{\text{ha az }}i.{\text{ csúcs része a }}j.{\text{ hiperélnek,}}\\0,&{\text{egyébként.}}\end{cases}}$$

Szomszédsági mátrix példák

1. Gráf szomszédsági mátrixa (irányítatlan gráf)

Példa:

• Csúcsok: $V=\{A,B,C\}$
• Élek: $E=\{\{A,B\},\{B,C\}\}$

A mátrix: $$A={\begin{bmatrix}0&1&0\\1&0&1\\0&1&0\end{bmatrix}}$$

2. Gráf szomszédsági mátrixa (irányított gráf)

Példa:

• Csúcsok: $V=\{A,B,C\}$
• Irányított élek: $E=\{(A,B),(B,C)\}$

A mátrix: $$A={\begin{bmatrix}0&1&0\\0&0&1\\0&0&0\end{bmatrix}}$$

3. Hipergráf szomszédsági mátrixa

Példa:

• Csúcsok: $V=\{A,B,C,D\}$
• Hiperélek: $E=\{e_{1}=\{A,B,C\},e_{2}=\{B,D\}\}$

A mátrix: $$A={\begin{bmatrix}1&0\\1&1\\1&0\\0&1\end{bmatrix}}$$

Szomszédsági mátrix generálása

Gráf szomszédsági mátrixának generálása

def create_adjacency_matrix(edges, num_nodes):
    import numpy as np
    matrix = np.zeros((num_nodes, num_nodes), dtype=int)

    for u, v in edges:
        matrix[u][v] = 1
        matrix[v][u] = 1  # Irányítatlan gráf esetén

    return matrix

# Példa: Irányítatlan gráf
edges = [(0, 1), (1, 2)]  # A=0, B=1, C=2
num_nodes = 3
adj_matrix = create_adjacency_matrix(edges, num_nodes)

print("Szomszédsági mátrix:\n", adj_matrix)

Hipergráf szomszédsági mátrixának generálása

def create_hypergraph_adjacency_matrix(hyperedges, vertices):
    import numpy as np
    num_vertices = len(vertices)
    num_edges = len(hyperedges)
    matrix = np.zeros((num_vertices, num_edges), dtype=int)

    for j, edge in enumerate(hyperedges):
        for i, vertex in enumerate(vertices):
            if vertex in edge:
                matrix[i][j] = 1

    return matrix

# Példa
vertices = ['A', 'B', 'C', 'D']
hyperedges = [{'A', 'B', 'C'}, {'B', 'D'}]
matrix = create_hypergraph_adjacency_matrix(hyperedges, vertices)

print("Hipergráf szomszédsági mátrix:\n", matrix)

Szomszédsági mátrix előnyei és hátrányai

Előnyök

• Egyszerű és közvetlen reprezentáció.
• Könnyen implementálható algoritmusokhoz, mint például:

 * Gráf bejárás (DFS, BFS).
 * Legrövidebb út keresése (pl. Floyd-Warshall).

• Hatékony éleket keresni: $O(1)$.

Hátrányok

• Nagy memóriaigény sűrű gráfokhoz: $O(V^{2})$, ahol $V$ a csúcsok száma.
• Ritka gráfok esetén sok felesleges nulla érték.

Összegzés

A szomszédsági mátrix egyszerű, de nagy memóriaigényű reprezentációja miatt főként sűrű gráfokhoz használatos. Hipergráfok esetében szintén hasznos, különösen incidenciamátrixként alkalmazva, amikor a csúcsok és hiperélek kapcsolatait vizsgáljuk.

Fordítások

• angol: adjacency matrix (en)
• német: Adjazenzmatrix (de)
• orosz: матрица смежности (ru) (matrica smežnosti)

További információk

• szomszédsági mátrix - Értelmező szótár (MEK)
• szomszédsági mátrix - Etimológiai szótár (UMIL)
• szomszédsági mátrix - Szótár.net (hu-hu)
• szomszédsági mátrix - DeepL (hu-de)
• szomszédsági mátrix - Яндекс (hu-ru)
• szomszédsági mátrix - Google (hu-en)
• szomszédsági mátrix - Helyesírási szótár (MTA)
• szomszédsági mátrix - Wikidata
• szomszédsági mátrix - Wikipédia (magyar)