Hipergraf

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Primer hipergrafa, kjer je in .

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

Hipergraf je par ,

kjer je
  • množica elementov, ki jih imenujemo vozlišča
  • je neprazna podmnožica množice , njene elemente imenujemo hiperpovezave. Hiperpovezava, ki povezuje samo dve vozlišči 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 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[uredi | uredi kodo]

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

  • subhipergrafe
  • delne hipergrafe
  • področne hipergrafe

Naj bo hipergraf, ki ima vozlišča

kar pomeni, da so vozlišča označena z indeksi in je množica povezav enaka

s povezavami, ki so označene z .

Subhipergraf je hipergraf, ki smo mu odstranili nekaj vozlišč, kar zapišemo kot

.

Delni hipergraf (parcialni hipergraf) je hipergraf, ki smo mu odstranili 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 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[uredi | uredi kodo]

  • Rang hipergrafa 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 vozlišča 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 in , ki pripadata hipergrafu , se imenujeta simetrični, če obstoja takšen avtomorfizem, da velja . Dve povezavi in sta simetrični, če obstoja takšen avtomorfizem, da velja .
  • 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[uredi | uredi kodo]