Hipergrafo

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

Formalmente, una hipergrafía no dirigida es un par donde hay un conjunto de elementos llamados nodos o vértices , y es (en una hipergrafía no dirigida) un conjunto de subconjuntos no vacíos llamados hiperaristas o aristas . Por lo tanto, es un subconjunto de , donde es el conjunto potencia de . El tamaño del conjunto de vértices se denomina orden de la hipergrafía , y el tamaño del conjunto de aristas es el tamaño de la hipergrafía .${\ estilo de visualización H}$${\ estilo de visualización H = (X, E)}$${\ estilo de visualización X}$${\ estilo de visualización E}$${\ estilo de visualización X}$${\ estilo de visualización E}$${\displaystyle {\mathcal {P}}(X)\setminus \{\emptyset \}}$${\displaystyle {\mathcal {P}}(X)}$${\ estilo de visualización X}$

Una hipergrafía dirigida se diferencia en que sus hiperaristas no son conjuntos, sino un par ordenado de subconjuntos de , que constituyen la cola y la cabeza de la hiperarista.${\ estilo de visualización X}$

Mientras que los bordes del gráfico conectan solo 2 nodos, los hiperbordes conectan un número arbitrario de nodos. Sin embargo, a menudo es deseable estudiar hipergráficos donde todos los hiperbordes tienen la misma cardinalidad; una hipergrafía k-uniforme es una hipergrafía tal que todos sus hiperbordes tienen tamaño k . (En otras palabras, uno de esos hipergráficos es una colección de conjuntos, cada uno de esos conjuntos es un hiperborde que conecta k nodos). Entonces, un hipergráfico de 2 uniformes es un gráfico, un hipergráfico de 3 uniformes es una colección de triples desordenados, y así sucesivamente. Una hipergrafía no dirigida 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 " que corresponde a cada hipergráfico y, a la inversa, la mayoría de los gráficos bipartitos , pero no todos, pueden considerarse gráficos de incidencia de hipergráficos.

Los hipergrafos tienen muchos otros nombres. En geometría computacional , un hipergráfico no dirigido a veces puede denominarse espacio de rango y luego los hiperbordes se denominan rangos . ^[2] En la teoría de juegos cooperativos , las hipergrafías 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 alguna literatura, los bordes se denominan hipervínculos o conectores . ^[3]

Un ejemplo de una hipergrafía no dirigida, con y . Esta hipergrafía tiene orden 7 y tamaño 4. Aquí, las aristas no solo conectan dos vértices sino varios, y se representan con 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 de la hipergrafía reportada en la figura anterior, llamada 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 una hipergrafía dirigida, 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 hiperbordes dibujados como árboles.

Un diagrama de Venn de orden 4, que se puede interpretar como un dibujo de subdivisión de una hipergrafía con 15 vértices (las 15 regiones coloreadas) y 4 hiperaristas (las 4 elipses).