Szomszédsági mátrix

Innen: testwiki

Ugrás a navigációhoz Ugrás a kereséshez

Sablon:Label 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_{i j}$ eleme az $i$ csúcsból a $j$ csúcsba vezető élek száma, míg a főátlóban található $a_{i i}$ , 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{matrix} 1, & ha van él i és j között, \\ 0, & egyébként. \end{matrix}$ Az irányítatlan gráf szomszédsági mátrixa szimmetrikus.

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

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{matrix} 1, & ha az i . csúcs része a j . hiperélnek, \\ 0, & egyébként. \end{matrix}$

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{matrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}]$

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{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix}]$

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{matrix} 1 & 0 \\ 1 & 1 \\ 1 & 0 \\ 0 & 1 \end{matrix}]$

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.

A lap eredeti címe: „https://hu.wiktionary.beta.math.wmflabs.org/w/index.php?title=Szomszédsági_mátrix&oldid=307”