Hipergráf

A Wikipédiából, a szabad enciklopédiából
Példa hipergráfra: a csúcshalmaz V = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\}, az élhalmaz: E= \{e_1,e_2,e_3,e_4\} =\{\{v_1, v_2, v_3\}, \{v_2,v_3\}, \{v_3,v_5,v_6\},\{v_4\}\}.

A hipergráf vagy halmazrendszer a kombinatorika által vizsgált matematikai struktúrák egyike; elméletük a gráfelméletből vált le; mert a gráfok olyan általánosításainak tekinthetőek, ahol egy él kettőnél több csúcsot is összeköthet („hiperélek”). Az elnevezés bevezetésére Claude Berge francia kombinatorikaprofesszor tett javaslatot 1966-ban egy tihanyi matematikustalálkozón, és ő írta a hipergráfok elméletének első összefoglaló munkáit is.

Matematikailag egy hipergráf egy (V,E) páros, ahol V tetszőleges (általában, de nem szükségszerűen: véges) halmaz, E pedig a V részhalmazainak egy családja; bár ha pontosak akarnánk lenni, azt mondanánk, hogy egy hipergráf valójában ilyen párok egy ekvivalenciaosztálya az izomorfia nevű relációra nézve. A V elemeit (hiper)csúcsoknak, az E elemeit (hiper)éleknek is szokás nevezni.

A hipergráfok tulajdonképpen az incidenciastruktúrák közé tartoznak. Megfordítva, az incidenciastruktúrák is tekinthetők hipergráfoknak. Például minden hipergráfnak megvan a Levi-gráfja, és megfordítva. Hipergráf helyett használják a halmazrendszer és a halmazcsalád elnevezéseket is.

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]