Hipergrafos

Hipergrafo

Ejemplo de hipergrafo
H={e1,e2,e3,e4}={{v1,v2,v3},{v2,v3},{v3,v5,v6},{v4}},
 definido sobre el conjunto base
A = {v1, v2, v3, v4, v5, v6, v7}.
Aquí H es propio, tiene dominio parcial,
su cardinalidad es 4 y su tamaño 28.

En matemática 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 sólo un máximo de dos como en el caso particular.
Formalmente, dado un conjunto finito A llamado conjunto base, un hipergrafo H es una familia de subconjuntos de ; es decir, un subconjunto de , que es el conjunto potencia de . Los elementos de un hipergrafo se llaman hiperaristas, las cuales a su vez son subconjuntos de .
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 |A|·|H|.

Los hipergrafos pueden ser vistos como estructuras de incidencia. En particular, hay "grafo de incidencia" bipartito o "grafo Levi" correspondiente a cada hipergrafo, y por el contrario, la mayoría, pero no todos, los gráficos bipartitos puede ser considerado como grafos de incidencia de hipergrafos.

Los hipergrafos tienen muchos otros nombres. En la geometría computacional, un hipergrafo a veces puede ser llamado un rango de espacio y luego los hiperenlaces son llamados rangos. En la teoría de juegos cooperativos, los hipergrafos se llaman juegos simples (juegos de votación); esta noción se aplica para resolver problemas en la teoría de la elección social. En alguna literatura los enlaces se conocen como hipervínculos o conectores.

Historia

Este término fue acuñado por el matemático francés Claude Berge en 1970.1 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 ésta última. 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 muchas otras.

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.

Estructura de hipergrafos

Una estructura de hipergrafos es un par ordenado G:=(H, K) de dos hipergrafos H y K, bajo el mismo conjunto base.
El tamaño o volumen de una estructura está dada por |A|·(|H|+|K|).

Ejemplo

Sea , entonces , con  y  es una estructura de hipergrafos, de tamaño 18.

Modelo de grafo bipartito 

Un hipergrafo H puede ser representado por un grafo bipartito BG de la siguiente manera: los conjuntos x y e son las particiones de BG, y (x1, e1) están conectados con un enlace si y sólo si x1 vértice está contenida en e1 borde en H. a la inversa, cualquier grafo bipartito con partes fijas y no hay nodos no conectados en la segunda parte representa algunos hipergrafos en la forma descrita anteriormente. Este gráfico bipartito también se llama grafo de incidencia.

Referencias

• Berge, Claude (1970). Graphes et hypergraphes (37 edición). Dunod, París: Monographies Universitaires de Mathématiques.