Hipergraf

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
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[uredi | uredi kodo]

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[uredi | uredi kodo]

  • 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[uredi | uredi kodo]