Hipergráf

1. Sablon:Label

Hipergráf definíció

Egy hipergráf a gráf általánosítása, ahol a hiperélek nem csupán két csúcsot kötnek össze, mint a hagyományos gráfokban, hanem több csúcsot is összekapcsolhatnak egyszerre. Egy hipergráfot formálisan $H=(V,E)$-vel jelölünk, ahol:

• $V$ a csúcsok halmaza.
• $E\subseteq 𝒫(V)$ a hiperélek halmaza ($𝒫(V)$ a $V$ hatványhalmaza).

Példa

Egy hagyományos gráf:

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

Egy hipergráf:

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

A hipergráfok különösen hasznosak olyan alkalmazásokban, ahol az elemek közötti kapcsolatok komplexek és több elem közötti összefüggéseket kell modellezni, például:

• Adatbázisokban (pl. rekordok összefüggései).
• Hálózatelemzésben (pl. közösségek modellezése).
• Tudományos vizualizációban.

Hipergráf reprezentáció

A hipergráfokat többféleképpen lehet reprezentálni:

Szomszédsági lista hiperélekkel

Minden hiperél egy halmaz, amely a csúcsokat tartalmazza:

hypergraph = {
    'e1': {'A', 'B', 'C'},
    'e2': {'B', 'D'}
}

Csúcs-alapú szomszédsági lista

Megmutatja, hogy mely csúcsok mely hiperélekhez tartoznak:

vertex_hyperedges = {
    'A': ['e1'],
    'B': ['e1', 'e2'],
    'C': ['e1'],
    'D': ['e2']
}

Incidenciamátrix

A mátrix soraiban a csúcsok, oszlopaiban pedig a hiperélek szerepelnek, a mátrix eleme 1, ha a csúcs része az adott hiperélnek: $$\begin{array}{ccc}& e1& e2\\ A& 1& 0\\ B& 1& 1\\ C& 1& 0\\ D& 0& 1\end{array}$$

Hipergráf algoritmusok

Hiperélek incidenciájának vizsgálata

Megvizsgálhatjuk, hogy két hiperél között van-e közös csúcs:

def hyperedge_intersection(hypergraph, edge1, edge2):
    return hypergraph[edge1].intersection(hypergraph[edge2])

# Példa
result = hyperedge_intersection(hypergraph, 'e1', 'e2')
print("Közös csúcsok:", result)

Csúcsfokok kiszámítása

Egy csúcs fokát megkaphatjuk úgy, hogy megszámoljuk, hány hiperélhez tartozik:

def vertex_degree(vertex, hypergraph):
    degree = sum(1 for edge in hypergraph.values() if vertex in edge)
    return degree

# Példa
degree_of_B = vertex_degree('B', hypergraph)
print("B csúcs foka:", degree_of_B)

Hipergráf incidenciamátrix generálása

def generate_incidence_matrix(hypergraph):
    import numpy as np
    vertices = sorted(set.union(*hypergraph.values()))
    edges = sorted(hypergraph.keys())
    matrix = np.zeros((len(vertices), len(edges)), dtype=int)

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

# Példa
matrix, vertices, edges = generate_incidence_matrix(hypergraph)
print("Incidenciamátrix:\n", matrix)
print("Csúcsok:", vertices)
print("Hiperélek:", edges)

Kimenet

$\text{Incidenciamátrix:}\left[\begin{array}{cc}1& 0\\ 1& 1\\ 1& 0\\ 0& 1\end{array}\right]$ Csúcsok: $\{A,B,C,D\}$ Hiperélek: $\{e1,e2\}$

• Sablon:En: Sablon:T
• Sablon:Ru: Sablon:T