Hipergrafo

En matemáticas y ciencias de la computación, un hipergrafo es una generalización de un grafo, cuyas aristas aquí se llaman hiperaristas, y pueden relacionar a cualquier cantidad de vértices, en lugar de solo un máximo de dos como en el caso de los grafos. Así, un grafo es una clase particular de hipergrafos, en que cada hiperarista tiene a lo más dos vértices.^[1]​

Ejemplo de hipergrafo de vértices v₁, v₂, v₃, v₄, v₅, v₆ y v₇, con hiperaristas e₁, e₂, e₃ y e₄. Es propio, tiene dominio parcial, su cardinalidad es 4 y su tamaño 28.

Definición formal

Formalmente, un hipergrafo ${\displaystyle H}$  es un par ordenado ${\displaystyle H=(A,E)}$ , donde ${\displaystyle A}$  es un conjunto finito de vértices o puntos, también llamado conjunto base, y ${\displaystyle E}$  es el conjunto de hiperaristas, a veces llamadas simplemente aristas, correspondiente a una familia de subconjuntos de ${\displaystyle A}$ , es decir, a un subconjunto de ${\displaystyle P(A)}$ , que es el conjunto potencia de ${\displaystyle A}$ .^[1]​ De acuerdo con la definición original, las hiperaristas no pueden ser vacías.^[2]​

La cardinalidad de un hipergrafo es su número de hiperaristas, y se denota |H|. El tamaño o volumen de un hipergrafo, se define como la suma del tamaño de sus hiperaristas, valor acotado superiormente por |A|·|H|.

Historia

Este término fue acuñado por el matemático francés Claude Berge en 1970.^[3]​ Desde entonces, se ha desarrollado toda una teoría de hipergrafos, que aunque a veces trata conceptos y problemas similares a los de la teoría de grafos, muchas veces se distancia de esta última.

Propiedades

• Un hipergrafo es propio, si no es vacío ni contiene la hiperarista vacía.
• Un hipergrafo tiene dominio total si la unión de las hiperaristas es igual al conjunto A; de lo contrario, se dice que tiene dominio parcial.

Dualidad de hipergrafos

Dado un hipergrafo ${\displaystyle H=(A,E)}$ , se puede definir su hipergrafo dual ${\displaystyle H^{*}=(E,A)}$  invirtiendo los roles de los vértices y las hiperaristas.^[1]​

Aplicaciones

Los hipergrafos se utilizan actualmente en distintas áreas, tales como la lógica, la optimización, teoría de juegos, inteligencia artificial, minería de datos, indexación de bases de datos, entre otras.

En análisis de redes sociales, los hipergrafos permiten representar redes de afiliación o de pertenencia, esto es, redes bimodales, en que uno de los tipos de actores representan «acontecimientos» asociados a subconjuntos de actores del otro tipo. Por ejemplo, una red conformada por personas y por clubes, de modo que las personas se relacionan con los clubes a los que pertenecen.^[4]​^[1]​

Referencias

1. Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.
2. Berge, C. (1989). Hypergraphs: Combinatorics of finite sets. Amsterdam: North-Holland. 
3. Berge, C. (1970). Graphes et hypergraphes (37 edición). Dunod, París: Monographies Universitaires de Mathématiques. 
4. Wasserman y Faust, 2013, «Datos de redes sociales: recogida y aplicaciones», pp. 59-96.

Bibliografía

• Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053. 

•   Datos: Q840247
•   Multimedia: Hypergraphs