- 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 A; es decir, un subconjunto de P(A), que es el conjunto potencia de A. Los elementos de un hipergrafo se llaman hiperaristas, las cuales a su vez son subconjuntos de A.
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|.
Contenido
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 A: = {a,b,c}, entonces G: = (H,K), con H: = {{a,b},{b,c},{c}} y K: = {{a,c},{b,c},{a,b,c}} es una estructura de hipergrafos, de tamaño 18.
Referencias
Categorías:- Teoría de conjuntos
- Teoría de hipergrafos
- Familias de grafos
Wikimedia foundation. 2010.
