hipergráf
Kiejtés
- IPA:
Főnév
hipergráf
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 -vel jelölünk, ahol:
- a csúcsok halmaza.
- a hiperélek halmaza ( a hatványhalmaza).
Példa
Egy hagyományos gráf:
- Csúcsok:
- Élek:
Egy hipergráf:
- Csúcsok:
- Hiperélek:
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': ,
'B': ,
'C': ,
'D':
}
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:
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.intersection(hypergraph)
# 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:
matrix = 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
Csúcsok: Hiperélek:
