szomszédsági mátrix

• IPA:

szomszédsági mátrix

1. (matematika, gráfelmélet) Egy véges irányított vagy irányítatlan ${\displaystyle n}$ csúcsú ${\displaystyle G}$ gráf szomszédsági mátrixa (ritkábban: adjacenciamátrixa) az az ${\displaystyle n\times n}$-es mátrix, amelynek a nem a főátlóban szereplő ${\displaystyle a_{ij}}$ eleme az ${\displaystyle i}$ csúcsból a ${\displaystyle j}$ csúcsba vezető élek száma, míg a főátlóban található ${\displaystyle a_{ii}}$, vagy az ${\displaystyle 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.

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.

Ha a gráf irányítatlan: $${\displaystyle A={\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: $${\displaystyle A={\begin{cases}1,&{\text{ha van irányított él }}i\to j,\\0,&{\text{egyébként.}}\end{cases}}}$$

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

Példa:

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

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

Példa:

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

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

Példa:

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

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

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 = 1
        matrix = 1  # Irányítatlan gráf esetén

    return matrix

# Példa: Irányítatlan gráf
edges =   # 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)

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 = 1

    return matrix

# Példa
vertices = 
hyperedges = 
matrix = create_hypergraph_adjacency_matrix(hyperedges, vertices)

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

• 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: ${\displaystyle O(1)}$.

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

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.

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

• 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)