Hypergraph

En matemáticas , un hipergráfico es una generalización de un gráfico en el que una arista puede unir cualquier número de vértices . Por el contrario, en un gráfico ordinario, una arista conecta exactamente dos vértices.

Formalmente, un hipergrafo no dirigido es un par donde hay un conjunto de elementos llamados nodos o vértices , y es (en un hipergrafo no dirigido) un conjunto de subconjuntos no vacíos de llamados hipergrafos o bordes . Por lo tanto, es un subconjunto de , donde es el conjunto de potencia de . El tamaño del conjunto de vértices se denomina orden del hipergráfico y el tamaño de los bordes establecidos es el tamaño del hipergráfico .${\ Displaystyle H}$${\ Displaystyle H = (X, E)}$${\ Displaystyle X}$${\ Displaystyle E}$${\ Displaystyle X}$${\ Displaystyle E}$${\ Displaystyle {\ mathcal {P}} (X) \ setminus \ {\ emptyset \}}$${\ Displaystyle {\ mathcal {P}} (X)}$${\ Displaystyle X}$

Un hipergrafo dirigido se diferencia en que sus hipergrafias no son conjuntos, sino un par ordenado de subconjuntos de , que constituyen la cola y la cabeza de la hipergrafia.${\ Displaystyle X}$

Mientras que los bordes del gráfico conectan solo 2 nodos, los hipermercados conectan un número arbitrario de nodos. Sin embargo, a menudo es deseable estudiar hipergráficos donde todos los hipergráficos tienen la misma cardinalidad; un hipergrafo uniforme k es un hipergrafo tal que todos sus hipergrafos tienen un tamao k . (En otras palabras, uno de esos hipergrafos es una colección de conjuntos, cada uno de estos conjuntos es un hipergrafo que conecta k nodos). De modo que un hipergrafo de 2 uniformes es un grafo, un hipergrafo de 3 uniformes es una colección de triples desordenados, etc. Un hipergrama no dirigido también se denomina sistema de conjuntos o familia de conjuntos extraídos del conjunto universal .

Los hipergráficos pueden verse como estructuras de incidencia . En particular, hay un "gráfico de incidencia" bipartito o " gráfico de Levi " correspondiente a cada hipergráfico y, a la inversa, la mayoría, pero no todos, los gráficos bipartitos pueden considerarse como gráficos de incidencia de hipergráficos.

Los hipergrafos tienen muchos otros nombres. En geometría computacional , un hipergrafo no dirigido a veces se puede llamar un espacio de rango y luego los hipergrafos se llaman rangos . ^[2] En la teoría de juegos cooperativos , los hipergráficos se denominan juegos simples (juegos de votación); esta noción se aplica para resolver problemas en la teoría de la elección social . En algunas publicaciones, los bordes se denominan hipervínculos o conectores . ^[3]

Un ejemplo de un hipergráfico no dirigido, con y . Este hipergráfico tiene orden 7 y tamaño 4. Aquí, los bordes no solo conectan dos vértices sino varios, y están representados por colores.${\displaystyle X=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\}}$${\displaystyle E=\{e_{1},e_{2},e_{3},e_{4}\}=}$ ${\displaystyle \{\{v_{1},v_{2},v_{3}\},}$ ${\displaystyle \{v_{2},v_{3}\},}$ ${\displaystyle \{v_{3},v_{5},v_{6}\},}$ ${\displaystyle \{v_{4}\}\}}$

Representación alternativa del hipergráfico informado en la figura anterior, llamado PAOH. ^[1] Los bordes son líneas verticales que conectan vértices. V7 es un vértice aislado. Los vértices están alineados a la izquierda. La leyenda de la derecha muestra los nombres de los bordes.

Un ejemplo de un hipergráfico dirigido, con y .${\displaystyle X=\{1,2,3,4,5,6\}}$${\displaystyle E=\{a_{1},a_{2},a_{3},a_{4},a_{5}\}=}$ ${\displaystyle \{(\{1\},\{2\}),}$ ${\displaystyle (\{2\},\{3\}),}$ ${\displaystyle (\{3\},\{1\}),}$ ${\displaystyle (\{2,3\},\{4,5\}),}$ ${\displaystyle (\{3,5\},\{6\})\}}$

Este diagrama de circuito se puede interpretar como un dibujo de un hipergráfico en el que cuatro vértices (representados como rectángulos y discos blancos) están conectados por tres hipergrafias dibujadas como árboles.

Un diagrama de Venn de orden 4, que se puede interpretar como un dibujo de subdivisión de un hipergráfico con 15 vértices (las 15 regiones coloreadas) y 4 hiperedges (las 4 elipses).