Hipergraf

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 je posplošitev grafa. V hipergrafu poljubno število povezav (robov) povezuje poljubno število točk.

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 $𝒫(X)\setminus \{\mathrm{\varnothing }\}$, kjer je $𝒫(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=\{x_m|m\in M\},$

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

$E=\{e_i|i\in I,e_i\subseteq X\}$

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=(A,\{e_i\cap A|e_i\cap A\ne \varnothing \}).$

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

$(X,\{e_i|i\in J\}).$

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

$H\times A=(A,\{e_i|i\in I,e_i\subseteq A\subseteq X\}).$

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 $\varphi (x)=y$. Dve povezavi $e_i$ in $e_j$ sta simetrični, če obstaja takšen avtomorfizem, da velja $\varphi (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 Predloga:Webarchive Predloga:Ikona ru
• Predloga:MathWorld
• Hipergraf Predloga:Webarchive na NIST Predloga:Ikona en