Hipergraf

Primer 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 ali točk) povezuje poljubno število vozlišč.

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

kjer je

• $X \,$ množica elementov, ki jih imenujemo vozlišča
• $E \,$ je neprazna podmnožica množice $X \,$, njene elemente imenujemo hiperpovezave. Hiperpovezava, ki povezuje samo dve vozlišči 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 vozlišč. V hipergrafu so hiperpovezave množice, ki povezujejo vozlišča, in tako lahko vsebujejo poljubno število vozlišč.

Množica vseh hipergrafov je kategorija s homomorfizmom hipergrafov.

Vrste hipergrafov

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

• subhipergrafe
• delne hipergrafe
• področne hipergrafe

Naj bo $H = (X, E) \,$ hipergraf, ki ima vozlišča

$X = \lbrace x_m | m \in M \rbrace$

kar pomeni, da so vozlišča označena 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$.

Subhipergraf je hipergraf, ki smo mu odstranili nekaj vozlišč, kar zapišemo 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 smo mu odstranili 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 zamenjana vozliča in povezave glede na prvotni hipergraf.

Osnovni graf (tudi Gaifmanov graf hipergrafa) hipergrafa je graf z enakimi vozlišči, kot jih ima hipergraf, in enakimi povezavami med vsemi pari vozlišč, ki jih najdemo v isti hiperpovezavi.

Simetrični hipergrafi

• Rang hipergrafa $r(H) \,$ je največja kardinalnost vseh povezav v hipergrafu. Če imajo vse povezave isto kardinalnost pravimo, da 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 jih vozlišče vsebuje. Hipergraf je k-regularen, če ima vsako vozlišče stopnjo k.

• Dualni hipergraf uniformnega hipergrafa je regularni hipergraf in obratno.

• Dve vozlišči $x \,$ in $y \,$, ki pripadata hipergrafu $H \,$, se imenujeta simetrični, če obstoja takšen avtomorfizem, da velja $\phi(x) = y \,$. Dve povezavi $e_i \,$ in $e_j \,$ sta simetrični, če obstoja takšen avtomorfizem, da velja $\phi(e_i) = e_j \,$.

• Hipergraf je vozliščno tranzitiven (tudi vozliščno simetričen), če so vsa njegova vozlišča simetrična. Podobno velja za povezave (dobimo povezavno simetričen hipergraf). Kadar pa je hipergraf vozliščno in povezavno simetričen, pravimo, da je hipergraf tranzitiven.

Zunanje povezave

• Hipergraf (v ruščini)
• Hipergraf na Mathworld (v angleščini)
• Hipergraf na NIST (v angleščini)