Hipergraf

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

Zgled hipergrafa, kjer je $X=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\}$ in $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}\}\}$.

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

kjer je:

• $X\,$ množica elementov, ki se imenujejo točke (vozlišča)
• $E\,$ je neprazna podmnožica množice $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 $E\,$ je podmnožica množice ${\mathcal {P}}(X)\setminus \{\emptyset \}$, kjer je ${\mathcal {P}}(X)\,$ potenčna množica množice $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 $H=(X,E)\,$ hipergraf, ki ima točke:

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

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

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

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

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

$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 $J\subset I$ množice indeksov $I\,$ je delni hipergraf določen kot

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

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

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

Dualni hipergraf (oznaka $H^{*}\,$) hipergrafu $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 $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 $d(v)\,$ vozlišča $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 $x\,$ in $y\,$, ki pripadata hipergrafu $H\,$, se imenujeta simetrični, če obstaja takšen avtomorfizem, da velja $\phi (x)=y\,$. Dve povezavi $e_{i}\,$ in $e_{j}\,$ sta simetrični, če obstaja takšen avtomorfizem, da velja $\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)