Hipergrafo
De Wikipedia, la enciclopedia libre
Un hipergrafo, dado un conjunto finito A, llamado conjunto base, 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.
Un hipergrafo se puede ver además como un grafo generalizado (V,E), donde V=A, y E es el conjunto de aristas (hiperaristas, en este contexto), las cuales pueden relacionar cualquier número de nodos (elementos del conjunto base).
Este término fue acuñado por el matemático francés Claude Berge.[1] Los hipergrafos se utilizan actualmente para representar problemas de lógica, optimización, teoría de juegos, inteligencia artificial, entre muchos otros.
[editar] Propiedades
- El número de hiperaristas de un hipergrafo H corresponde a la cardinalidad del hipergrafo, y se denota | H | . Además, el tamaño o volumen del hipergrafo, está dado por |A|·|H|.
- 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.
Ejemplo. Sea A: = {a,b,c}, entonces H: = {{a,b},{b,c},{c}} es un hipergrafo propio, con dominio total, de tamaño 9 y con | H | = 3.
[editar] Estructura de hipergrafos
Una estructura de hipergrafos es un par ordenado de dos hipergrafos H y K, bajo el mismo conjunto base.
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).
El tamaño o volumen de una estructura está dada por |A|·(|H|+|K|).
[editar] Referencias
- ↑ Graphs and Hypergraphs. Dunod, París. 1970.
