Hipergraf

Hipergraf je posplošitev grafa. V hipergrafu poljubno število povezav (robov) povezuje poljubno število točk.

Zgled hipergrafa, kjer je ${\displaystyle X=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\}}$ in ${\displaystyle E=\{e_{1},e_{2},e_{3},e_{4}\}=}$ ${\displaystyle \{\{v_{1},v_{2},v_{3}\},}$ ${\displaystyle \{v_{2},v_{3}\},}$ ${\displaystyle \{v_{3},v_{5},v_{6}\},}$ ${\displaystyle \{v_{4}\}\}}$.

Hipergraf ${\displaystyle H\,}$ je par ${\displaystyle H=(X,E)\,}$,

kjer je:

• ${\displaystyle X\,}$ množica elementov, ki se imenujejo točke (vozlišča)
• ${\displaystyle E\,}$ je neprazna podmnožica množice ${\displaystyle X\,}$, njeni elementi se imenujejo hiperpovezave ali kar povezave. Hiperpovezava, ki povezuje samo dve točki, je običajna povezava v grafu.

V izrazu je ${\displaystyle E\,}$ je podmnožica množice ${\displaystyle {\mathcal {P}}(X)\setminus \{\emptyset \}}$, kjer je ${\displaystyle {\mathcal {P}}(X)\,}$ potenčna množica množice ${\displaystyle X\,}$.

V grafu povezava pripada paru točk. V hipergrafu so hiperpovezave množice, ki povezujejo točke, in tako lahko vsebujejo poljubno število točk.

Množica vseh hipergrafov je kategorija s homomorfizmom hipergrafov.

Vrste hipergrafov

Ker imajo povezave v hipergrafu poljubno kardinalnost, se lahko hipergrafe razdeli na več vrst:

• podhipergrafe
• delne hipergrafe
• področne hipergrafe

Naj bo ${\displaystyle H=(X,E)\,}$ hipergraf, ki ima točke:

${\displaystyle X=\lbrace x_{m}|m\in M\rbrace \!\,,}$

kar pomeni, da so točke označene z indeksi ${\displaystyle m\in M\,}$ in je množica povezav enaka:

${\displaystyle E=\lbrace e_{i}|i\in I,e_{i}\subseteq X\rbrace \!\,}$

s povezavami, ki so označene z ${\displaystyle i\in I\,}$.

Podhipergraf je hipergraf, ki se mu je odstranilo nekaj točk, kar se zapiše kot:

${\displaystyle H_{A}=\left(A,\lbrace e_{i}\cap A|e_{i}\cap A\neq \varnothing \rbrace \right)\!\,.}$

Delni hipergraf (parcialni hipergraf) je hipergraf, ki se mu je odstranilo nekaj povezav.

Za dano množico ${\displaystyle J\subset I}$ množice indeksov ${\displaystyle I\,}$ je delni hipergraf določen kot

${\displaystyle \left(X,\lbrace e_{i}|i\in J\rbrace \right)\!\,.}$

Za podmnožico ${\displaystyle A\subseteq X}$ je področni hipergraf delni hipergraf:

${\displaystyle H\times A=\left(A,\lbrace e_{i}|i\in I,e_{i}\subseteq A\subseteq X\rbrace \right)\!\,.}$

Dualni hipergraf (oznaka ${\displaystyle H^{*}\,}$) hipergrafu ${\displaystyle H\,}$ je hipergraf, ki ima zamenjane točke in povezave glede na prvotni hipergraf.

Osnovni graf (tudi Gaifmanov graf hipergrafa) hipergrafa je graf z enakimi točkami, kot jih ima hipergraf, in enakimi povezavami med vsemi pari točk, ki se jih najde v isti hiperpovezavi.

Simetrični hipergrafi

• Rang hipergrafa ${\displaystyle r(H)\,}$ je največja kardinalnost vseh povezav v hipergrafu. Če imajo vse povezave isto kardinalnost, je hipergraf enakomeren ali k-krat enakomeren ali tudi k-hipergraf. Graf je 2-krat enakomeren.

• Stopnja ${\displaystyle d(v)\,}$ vozlišča ${\displaystyle v\,}$ je enaka številu povezav, ki vsebuje točka. Hipergraf je k-regularen, če ima vsaka točka stopnjo k.

• Dualni hipergraf uniformnega hipergrafa je regularni hipergraf in obratno.

• Dve točki ${\displaystyle x\,}$ in ${\displaystyle y\,}$, ki pripadata hipergrafu ${\displaystyle H\,}$, se imenujeta simetrični, če obstaja takšen avtomorfizem, da velja ${\displaystyle \phi (x)=y\,}$. Dve povezavi ${\displaystyle e_{i}\,}$ in ${\displaystyle e_{j}\,}$ sta simetrični, če obstaja takšen avtomorfizem, da velja ${\displaystyle \phi (e_{i})=e_{j}\,}$.

• Hipergraf je točkovnoprehoden (tudi točkovnosimetričen), če so vse njegove točke simetrične. Podobno velja za povezave (dobi se povezavnosimetričen hipergraf). Kadar je hipergraf točkovno in povezavnosimetričen, je prehoden.

Zunanje povezave

• Hipergraf Arhivirano 2008-06-29 na Wayback Machine. (rusko)
• Weisstein, Eric Wolfgang. »Hypergraph«. MathWorld.
• Hipergraf Arhivirano 2011-01-08 na Wayback Machine. na NIST (angleško)