right|frame| Zgled hipergrafa, kjer je in
. Hipergraf je posplošitev grafa. V hipergrafu poljubno število povezav (robov) povezuje poljubno število točk.
Hipergraf je par ,
kjer je: množica elementov, ki se imenujejo točke (vozlišča) je neprazna podmnožica množice , njeni elementi se imenujejo hiperpovezave ali kar povezave. Hiperpovezava, ki povezuje samo dve točki, je običajna povezava v grafu.
V izrazu je je podmnožica množice , kjer je potenčna množica množice .
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 hipergraf, ki ima točke:
kar pomeni, da so točke označene z indeksi in je množica povezav enaka:
s povezavami, ki so označene z .
Podhipergraf je hipergraf, ki se mu je odstranilo nekaj točk, kar se zapiše kot:
Delni hipergraf (parcialni hipergraf) je hipergraf, ki se mu je odstranilo nekaj povezav. Za dano množico množice indeksov je delni hipergraf določen kot
Za podmnožico je področni hipergraf delni hipergraf:
Dualni hipergraf (oznaka ) hipergrafu 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 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 vozlišča 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 in , ki pripadata hipergrafu , se imenujeta simetrični, če obstaja takšen avtomorfizem, da velja . Dve povezavi in sta simetrični, če obstaja takšen avtomorfizem, da velja .
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
Hipergraf na NIST
de:Graph (Graphentheorie)#Hypergraph