Hipergrafo

Eixemple de hipergrafo de vèrtiços v₁, v₂, v₃, v₄, v₅, v₆ i v₇, en hiperaristas i₁, i₂, i₃ i i₄. És propi, té domini parcial, el seu cardinalidad és 4 i el seu tamany 28.

En matemàtiques i ciències de la computació, un hipergrafo és una generalisació d'un grafo, que les seues arestes ací es diuen hiperaristas, i poden relacionar a qualsevol cantitat de vèrtiços, en lloc de solament un màxim de dos com en el cas dels grafos. Aixina, un grafo és una classe particular de hipergrafos, en que cada hiperarista té a lo més dos vèrtiços.

Definició formal

Formalment, un hipergrafo $H$ és un parell ordenat $H=(A,E)$, a on $A$ és un conjunt finito de vèrtiços o punts, també cridat conjunt base, i $E$ és el conjunt de hiperaristas, a voltes cridades simplement arestes, corresponent a una família de subconjunts de $A$, és dir, a un subconjunt de $P(A)$, que és el conjunt potencia de $A$. D'acort en la definició original, les hiperaristas no poden ser buides.

La cardinalidad d'un hipergrafo és el seu número de hiperaristas, i es denota |H|. El tamany o volum d'un hipergrafo, es definix com la suma del tamany dels seus hiperaristas, valor acotat superiormente per |A|·|H|.

Història

Este terme va ser falcat pel matemàtic francés Claude Berge en 1970. Des de llavors, s'ha desenrollat tota una teoria de hipergrafos, que encara que a voltes tracta conceptes i problemes similars als de la teoria de grafos, moltes voltes es distancia d'esta última.

Bibliografia

• (2013) Anàlisis de rets socials: Métodos i aplicacions, Madrit: Centre d'Investigacions Sociològiques. OCLC 871814053. ISBN 978-84-7476-631-8.