Hipergrafo

Generalización de la teoría de grafos

Un ejemplo de un hipergrafo no dirigido, con y . Este hipergrafo tiene orden 7 y tamaño 4. Aquí, las aristas no solo conectan dos vértices sino varios, y están representadas 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 hipergrafo que se muestra en la figura anterior, denominada PAOH. ^[1] Las aristas 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 las aristas.

Un ejemplo de un hipergrafo 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\})\}}$

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

Formalmente, un hipergrafo dirigido es un par , donde es un conjunto de elementos llamados nodos , vértices , puntos o elementos y es un conjunto de pares de subconjuntos de . Cada uno de estos pares se denomina arista o hiperarista ; el subconjunto de vértices se conoce como su cola o dominio , y como su cabeza o codominio . ${\displaystyle (X,E)}$ ${\displaystyle X}$ ${\displaystyle E}$ ${\displaystyle X}$ ${\displaystyle (D,C)\in E}$ ${\displaystyle D}$ ${\displaystyle C}$

El orden de un hipergrafo es el número de vértices en . El tamaño del hipergrafo es el número de aristas en . El orden de una arista en un hipergrafo dirigido es : es decir, el número de vértices en su cola seguido por el número de vértices en su cabeza. ${\displaystyle (X,E)}$ ${\displaystyle X}$ ${\displaystyle E}$ ${\displaystyle e=(D,C)}$ ${\displaystyle |e|=(|D|,|C|)}$

La definición anterior se generaliza de un grafo dirigido a un hipergrafo dirigido al definir la cabeza o la cola de cada arista como un conjunto de vértices ( o ) en lugar de como un único vértice. Un grafo es entonces el caso especial en el que cada uno de estos conjuntos contiene solo un elemento. Por lo tanto, cualquier concepto teórico de grafos estándar que sea independiente del orden de las aristas se generalizará a la teoría de hipergrafos. ${\displaystyle C\subseteq X}$ ${\displaystyle D\subseteq X}$ ${\displaystyle |e|}$

Un hipergrafo no dirigido es un grafo no dirigido cuyos bordes conectan no solo dos vértices, sino un número arbitrario. ^[2] Un hipergrafo no dirigido también se denomina sistema de conjuntos o familia de conjuntos extraídos del conjunto universal . ${\displaystyle (X,E)}$

Los hipergrafos pueden considerarse como estructuras de incidencia . En particular, existe un "grafo de incidencia" bipartito o " grafo de Levi " correspondiente a cada hipergrafo y, a la inversa, cada grafo bipartito puede considerarse como el grafo de incidencia de un hipergrafo cuando es de dos colores y se indica qué clase de color corresponde a los vértices del hipergrafo y cuál a las aristas del hipergrafo.

Los hipergrafos tienen muchos otros nombres. En geometría computacional , un hipergrafo no dirigido a veces puede llamarse espacio de rangos y luego las hiperaristas se denominan rangos . ^[3] En la teoría de juegos cooperativos , los hipergrafos 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, las aristas se denominan hipervínculos o conectores . ^[4]

La colección de hipergrafos es una categoría con homomorfismos de hipergrafos como morfismos .

Aplicaciones

Los hipergrafos no dirigidos son útiles para modelar cosas como problemas de satisfacibilidad, ^[5] bases de datos, ^[6] aprendizaje automático, ^[7] y problemas de árboles de Steiner . ^[8] Se han utilizado ampliamente en tareas de aprendizaje automático como el modelo de datos y la regularización del clasificador (matemáticas) . ^[9] Las aplicaciones incluyen el sistema de recomendación (comunidades como hiperaristas), ^{[10] [11]} recuperación de imágenes (correlaciones como hiperaristas), ^[12] y bioinformática (interacciones bioquímicas como hiperaristas). ^[13] Las técnicas representativas de aprendizaje de hipergrafos incluyen la agrupación espectral de hipergrafos que extiende la teoría de grafos espectrales con el laplaciano de hipergrafos, ^[14] y el aprendizaje semisupervisado de hipergrafos que introduce un costo estructural de hipergrafo adicional para restringir los resultados del aprendizaje. ^[15] Para hipergrafos a gran escala, también está disponible un marco distribuido ^[7] creado con Apache Spark . Puede ser deseable estudiar hipergrafos donde todos los hiperaristas tienen la misma cardinalidad; Un hipergrafo k-uniforme es un hipergrafo tal que todas sus hiperaristas tienen tamaño k . (En otras palabras, un hipergrafo de este tipo es una colección de conjuntos, y cada conjunto de estos es una hiperarista que conecta k nodos). Por lo tanto, un hipergrafo 2-uniforme es un grafo, un hipergrafo 3-uniforme es una colección de tripletas desordenadas, y así sucesivamente.

Los hipergrafos dirigidos se pueden utilizar para modelar cosas que incluyen aplicaciones de telefonía, ^[16] detección de lavado de dinero , ^[17] investigación de operaciones, ^[18] y planificación del transporte. También se pueden utilizar para modelar la satisfacibilidad de Horn . ^[19]

Generalizaciones de conceptos a partir de gráficos

Muchos teoremas y conceptos que involucran gráficos también son válidos para los hipergráficos, en particular:

• Coincidencia en hipergrafos ;
• Cobertura de vértices en hipergrafos (también conocidos como: transversales );
• Gráfica lineal de un hipergrafo ;
• Gramática de hipergrafos : se crea aumentando una clase de hipergrafos con un conjunto de reglas de reemplazo;
• Teorema de Ramsey ;
• Teorema de Erdős–Ko–Rado ;
• Teorema de Kruskal-Katona sobre hipergrafos uniformes;
• Teoremas de tipo Hall para hipergrafos .

En hipergrafos dirigidos: cierre transitivo y problemas de camino más corto. ^[18]

Dibujo hipergráfico

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

Aunque los hipergrafos son más difíciles de dibujar en papel que los gráficos, varios investigadores han estudiado métodos para la visualización de hipergrafos.

En una posible representación visual de los hipergrafos, similar al estilo de dibujo de gráficos estándar en el que se utilizan curvas en el plano para representar los bordes del gráfico, los vértices de un hipergrafo se representan como puntos, discos o cajas, y sus hiperaristas se representan como árboles que tienen los vértices como sus hojas. ^{[20] [21]} Si los vértices se representan como puntos, las hiperaristas también se pueden mostrar como curvas suaves que conectan conjuntos de puntos, o como curvas cerradas simples que encierran conjuntos de puntos. ^{[22] [23] [24]}

Un diagrama de Venn de orden 4, que puede interpretarse como un dibujo de subdivisión de un hipergrafo con 15 vértices (las 15 regiones coloreadas) y 4 hiperaristas (las 4 elipses).

En otro estilo de visualización de hipergrafos, el modelo de subdivisión del dibujo de hipergrafos, ^[25] el plano se subdivide en regiones, cada una de las cuales representa un único vértice del hipergrafo. Las hiperaristas del hipergrafo se representan mediante subconjuntos contiguos de estas regiones, que pueden indicarse mediante colores, dibujando contornos alrededor de ellas o ambas cosas. Un diagrama de Venn de orden n , por ejemplo, puede verse como un dibujo de subdivisión de un hipergrafo con n hiperaristas (las curvas que definen el diagrama) y 2 ⁿ  − 1 vértices (representados por las regiones en las que estas curvas subdividen el plano). En contraste con el reconocimiento en tiempo polinomial de grafos planares , es NP-completo determinar si un hipergrafo tiene un dibujo de subdivisión planar, ^[26] pero la existencia de un dibujo de este tipo puede probarse de manera eficiente cuando el patrón de adyacencia de las regiones se restringe a ser una ruta, un ciclo o un árbol. ^[27]

En la figura que figura en la parte superior de este artículo se muestra una representación alternativa del hipergrafo llamado PAOH ^[1] . Las aristas son líneas verticales que conectan vértices. Los vértices están alineados a la izquierda. La leyenda de la derecha muestra los nombres de las aristas. Se diseñó para hipergrafos dinámicos, pero también se puede utilizar para hipergrafos simples.

Coloración de hipergrafías

La coloración clásica de hipergrafos consiste en asignar uno de los colores del conjunto a cada vértice de un hipergrafo de tal forma que cada hiperarista contenga al menos dos vértices de colores distintos. En otras palabras, no debe haber ninguna hiperarista monocromática con cardinalidad al menos 2. En este sentido, es una generalización directa de la coloración de grafos. El número mínimo de colores distintos utilizados en todas las coloraciones se denomina número cromático de un hipergrafo. ${\displaystyle \{1,2,3,...,\lambda \}}$

Los hipergrafos para los cuales existe una coloración que utiliza hasta k colores se denominan k-coloreables . Los hipergrafos 2-coloreables son exactamente los bipartitos.

Existen muchas generalizaciones de la coloración clásica de hipergrafos. Una de ellas es la llamada coloración de hipergrafos mixtos, en la que se permiten bordes monocromáticos. Algunos hipergrafos mixtos no se pueden colorear con cualquier número de colores. Se desconoce un criterio general para la no coloración. Cuando un hipergrafo mixto se puede colorear, el número mínimo y máximo de colores utilizados se denominan números cromáticos inferior y superior respectivamente. ^[28]

Propiedades de los hipergrafos

Un hipergrafo puede tener varias propiedades, como:

• Vacío : no tiene bordes.
• No simple (o múltiple ) : tiene bucles (hiperaristas con un solo vértice) o aristas repetidas, lo que significa que puede haber dos o más aristas que contengan el mismo conjunto de vértices.
• Simple : no tiene bucles ni bordes repetidos.
• ${\displaystyle d}$-regular- cada vértice tiene grado , es decir, está contenido exactamente en hiperaristas. ${\displaystyle d}$ ${\displaystyle d}$
• 2-coloreable : sus vértices pueden dividirse en dos clases U y V de tal manera que cada hiperarista con cardinalidad al menos 2 contenga al menos un vértice de ambas clases. Un término alternativo es la propiedad B.
  • Dos propiedades más fuertes son bipartita y equilibrada .
• ${\displaystyle k}$-uniforme - cada hiperarista contiene precisamente vértices. ${\displaystyle k}$
• ${\displaystyle k}$-partite - los vértices se dividen en partes y cada hiperarista contiene precisamente un vértice de cada tipo. ${\displaystyle k}$
  • Cada hipergrafo -partito (para ) es a la vez -uniforme y bipartito (y 2-coloreable). ${\displaystyle k}$ ${\displaystyle k\geq 2}$ ${\displaystyle k}$
• Reducido : ^[29] ninguna hiperarista es un subconjunto estricto de otra hiperarista; equivalentemente, cada hiperarista es máxima para su inclusión. La reducción de un hipergrafo es el hipergrafo reducido que se obtiene al eliminar cada hiperarista que está incluida en otra hiperarista.
• Cerrado hacia abajo : cada subconjunto de las aristas de un hipergrafo no dirigido también es una hiperarista. Un hipergrafo cerrado hacia abajo suele denominarse complejo simplicial abstracto . Por lo general, no se reduce, a menos que todas las hiperaristas tengan cardinalidad 1.
  • Un complejo simplicial abstracto con la propiedad de aumento se llama matroide .
• Laminar : para dos hiperaristas cualesquiera, o bien son disjuntas, o bien una está incluida en la otra. En otras palabras, el conjunto de hiperaristas forma una familia de conjuntos laminares .

Hipergrafías relacionadas

Debido a que los enlaces de hipergrafos pueden tener cualquier cardinalidad, existen varias nociones del concepto de subgrafo, llamadas subhipergrafos , hipergrafos parciales e hipergrafos de sección .

Sea el hipergrafo formado por vértices ${\displaystyle H=(X,E)}$

${\displaystyle X=\lbrace x_{i}\mid i\in I_{v}\rbrace ,}$

y teniendo el borde fijado

${\displaystyle E=\lbrace e_{i}\mid i\in I_{e},e_{i}\subseteq X,e_{i}\neq \emptyset \rbrace ,}$

donde y son los conjuntos de índices de los vértices y las aristas respectivamente. ${\displaystyle I_{v}}$ ${\displaystyle I_{e}}$

Un subhipergrafo es un hipergrafo al que se le han quitado algunos vértices. Formalmente, el subhipergrafo inducido por se define como ${\displaystyle H_{A}}$ ${\displaystyle A\subseteq X}$

${\displaystyle H_{A}=\left(A,\lbrace e\cap A\mid e\in E,e\cap A\neq \emptyset \rbrace \right).}$

Un término alternativo es la restricción de H a A. ^[30] : ⁴⁶⁸

Una extensión de un subhipergrafo es un hipergrafo donde cada hiperarista del cual está parcialmente contenida en el subhipergrafo está completamente contenida en la extensión . Formalmente ${\displaystyle H}$ ${\displaystyle H_{A}}$ ${\displaystyle Ex(H_{A})}$

${\displaystyle Ex(H_{A})=(A\cup A',E')}$con y . ${\displaystyle A'=\bigcup _{e\in E}e\setminus A}$ ${\displaystyle E'=\lbrace e\in E\mid e\subseteq (A\cup A')\rbrace }$

El hipergrafo parcial es un hipergrafo con algunos bordes eliminados. ^{[30] : 468} Dado un subconjunto del conjunto de índices de bordes, el hipergrafo parcial generado por es el hipergrafo ${\displaystyle J\subset I_{e}}$ ${\displaystyle J}$

${\displaystyle \left(X,\lbrace e_{i}\mid i\in J\rbrace \right).}$

Dado un subconjunto , el hipergrafo de sección es el hipergrafo parcial ${\displaystyle A\subseteq X}$

${\displaystyle H\times A=\left(A,\lbrace e_{i}\mid i\in I_{e},e_{i}\subseteq A\rbrace \right).}$

El dual de es un hipergrafo cuyos vértices y aristas están intercambiados, de modo que los vértices están dados por y cuyas aristas están dadas por donde ${\displaystyle H^{*}}$ ${\displaystyle H}$ ${\displaystyle \lbrace e_{i}\rbrace }$ ${\displaystyle \lbrace X_{m}\rbrace }$

${\displaystyle X_{m}=\lbrace e_{i}\mid x_{m}\in e_{i}\rbrace .}$

Cuando se define adecuadamente una noción de igualdad, como se hace a continuación, la operación de tomar el dual de un hipergrafo es una involución , es decir,

${\displaystyle \left(H^{*}\right)^{*}=H.}$

Un grafo conexo G con el mismo conjunto de vértices que un hipergrafo conexo H es un grafo anfitrión para H si cada hiperarista de H induce un subgrafo conexo en G . Para un hipergrafo desconectado H , G es un grafo anfitrión si hay una biyección entre los componentes conexos de G y de H , de modo que cada componente conexo G' de G es un anfitrión del H' correspondiente .

El gráfico de 2 secciones (o gráfico de camarilla , que representa al gráfico , al gráfico primal , al gráfico de Gaifman ) de un hipergrafo es el gráfico con los mismos vértices del hipergrafo y aristas entre todos los pares de vértices contenidos en la misma hiperarista.

Matriz de incidencia

Sea y . Todo hipergrafo tiene una matriz de incidencia . ${\displaystyle V=\{v_{1},v_{2},~\ldots ,~v_{n}\}}$ ${\displaystyle E=\{e_{1},e_{2},~\ldots ~e_{m}\}}$ ${\displaystyle n\times m}$

Para un hipergrafo no dirigido, donde ${\displaystyle I=(b_{ij})}$

${\displaystyle b_{ij}=\left\{{\begin{matrix}1&\mathrm {if} ~v_{i}\in e_{j}\\0&\mathrm {otherwise} .\end{matrix}}\right.}$

La transpuesta de la matriz de incidencia define un hipergrafo llamado dual de , donde es un conjunto de m elementos y es un conjunto de n elementos de subconjuntos de . Para y si y solo si . ${\displaystyle I^{t}}$ ${\displaystyle H^{*}=(V^{*},\ E^{*})}$ ${\displaystyle H}$ ${\displaystyle V^{*}}$ ${\displaystyle E^{*}}$ ${\displaystyle V^{*}}$ ${\displaystyle v_{j}^{*}\in V^{*}}$ ${\displaystyle e_{i}^{*}\in E^{*},~v_{j}^{*}\in e_{i}^{*}}$ ${\displaystyle b_{ij}=1}$

Para un hipergrafo dirigido, las cabezas y las colas de cada hiperarista se denotan por y respectivamente. ^[19] donde ${\displaystyle e_{j}}$ ${\displaystyle H(e_{j})}$ ${\displaystyle T(e_{j})}$ ${\displaystyle I=(b_{ij})}$

${\displaystyle b_{ij}=\left\{{\begin{matrix}-1&\mathrm {if} ~v_{i}\in T(e_{j})\\1&\mathrm {if} ~v_{i}\in H(e_{j})\\0&\mathrm {otherwise} .\end{matrix}}\right.}$

Gráfica de incidencia

Un hipergrafo H puede representarse mediante un grafo bipartito BG de la siguiente manera: los conjuntos X y E son las partes de BG , y ( x ₁ , e ₁ ) están conectados con una arista si y solo si el vértice x ₁ está contenido en la arista e ₁ en H .

Por el contrario, cualquier grafo bipartito con partes fijas y sin nodos no conectados en la segunda parte representa algún hipergrafo de la manera descrita anteriormente. Este grafo bipartito también se denomina grafo de incidencia .

Matriz de adyacencia

Se puede trazar un paralelo para la matriz de adyacencia de un hipergrafo a partir de la matriz de adyacencia de un grafo. En el caso de un grafo, la matriz de adyacencia es una matriz cuadrada que indica si los pares de vértices son adyacentes . Del mismo modo, podemos definir la matriz de adyacencia para un hipergrafo en general donde las hiperaristas tienen pesos reales con ${\displaystyle A=(a_{ij})}$ ${\displaystyle e_{k\leq m}}$ ${\displaystyle w_{e_{k}}\in \mathbb {R} }$

${\displaystyle a_{ij}=\left\{{\begin{matrix}w_{e_{k}}&\mathrm {if} ~(v_{i},v_{j})\in E\\0&\mathrm {otherwise} .\end{matrix}}\right.}$

Ciclos

A diferencia de los gráficos ordinarios no dirigidos para los cuales existe una única noción natural de ciclos y gráficos acíclicos , existen múltiples definiciones naturales no equivalentes de aciclicidad para hipergráficos que colapsan a la aciclicidad de gráficos ordinarios para el caso especial de gráficos ordinarios.

Claude Berge dio una primera definición de aciclicidad para hipergrafos : ^[31] un hipergrafo es Berge-acíclico si su grafo de incidencia (el grafo bipartito definido anteriormente) es acíclico. Esta definición es muy restrictiva: por ejemplo, si un hipergrafo tiene algún par de vértices y algún par de hiperaristas tales que y , entonces es Berge-cíclico. Obviamente, la ciclicidad de Berge se puede probar en tiempo lineal mediante una exploración del grafo de incidencia. ${\displaystyle v\neq v'}$ ${\displaystyle f\neq f'}$ ${\displaystyle v,v'\in f}$ ${\displaystyle v,v'\in f'}$

Podemos definir una noción más débil de aciclicidad de hipergrafos, ^[6] posteriormente denominada α-aciclicidad. Esta noción de aciclicidad es equivalente a que el hipergrafo sea conforme (cada camarilla del grafo primario está cubierta por alguna hiperarista) y su grafo primario sea cordal ; también es equivalente a la reducibilidad al grafo vacío a través del algoritmo GYO ^{[32] [33]} (también conocido como algoritmo de Graham), un proceso iterativo confluente que elimina las hiperaristas utilizando una definición generalizada de ears . En el dominio de la teoría de bases de datos , se sabe que un esquema de base de datos disfruta de ciertas propiedades deseables si su hipergrafo subyacente es α-acíclico. ^[34] Además, la α-aciclicidad también está relacionada con la expresividad del fragmento guardado de la lógica de primer orden .

Podemos probar en tiempo lineal si un hipergrafo es α-acíclico. ^[35]

Nótese que la α-aciclicidad tiene la propiedad contra-intuitiva de que agregar hiperaristas a un hipergrafo α-cíclico puede hacerlo α-acíclico (por ejemplo, agregar una hiperarista que contenga todos los vértices del hipergrafo siempre lo hará α-acíclico). Motivado en parte por esta deficiencia percibida, Ronald Fagin ^[36] definió las nociones más fuertes de β-aciclicidad y γ-aciclicidad. Podemos enunciar la β-aciclicidad como el requisito de que todos los subhipergrafos del hipergrafo sean α-acíclicos, lo que es equivalente ^[36] a una definición anterior de Graham. ^[33] La noción de γ-aciclicidad es una condición más restrictiva que es equivalente a varias propiedades deseables de los esquemas de bases de datos y está relacionada con los diagramas de Bachman . Tanto la β-aciclicidad como la γ-aciclicidad pueden probarse en tiempo polinomial .

Esas cuatro nociones de aciclicidad son comparables: la aciclicidad de Berge implica γ-aciclicidad, lo que implica β-aciclicidad, lo que implica α-aciclicidad. Sin embargo, ninguna de las implicaciones inversas se cumple, por lo que esas cuatro nociones son diferentes. ^[36]

Isomorfismo, simetría e igualdad

Un homomorfismo de hipergrafo es un mapa del conjunto de vértices de un hipergrafo a otro tal que cada arista se mapea a otra arista.

Un hipergrafo es isomorfo a un hipergrafo , escrito como si existiera una biyección. ${\displaystyle H=(X,E)}$ ${\displaystyle G=(Y,F)}$ ${\displaystyle H\simeq G}$

${\displaystyle \phi :X\to Y}$

y una permutación de tal que ${\displaystyle \pi }$ ${\displaystyle I}$

${\displaystyle \phi (e_{i})=f_{\pi (i)}}$

La biyección se denomina entonces isomorfismo de los grafos. Nótese que ${\displaystyle \phi }$

${\displaystyle H\simeq G}$si y sólo si . ${\displaystyle H^{*}\simeq G^{*}}$

Cuando los bordes de un hipergrafo están etiquetados explícitamente, se tiene la noción adicional de isomorfismo fuerte . Se dice que es fuertemente isomorfo a si la permutación es la identidad. Entonces se escribe . Nótese que todos los grafos fuertemente isomorfos son isomorfos, pero no al revés. ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H\cong G}$

Cuando los vértices de un hipergrafo están etiquetados explícitamente, se tienen las nociones de equivalencia y también de igualdad . Se dice que es equivalente a y se escribe si el isomorfismo tiene ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H\equiv G}$ ${\displaystyle \phi }$

${\displaystyle \phi (x_{n})=y_{n}}$

y

${\displaystyle \phi (e_{i})=f_{\pi (i)}}$

Tenga en cuenta que

${\displaystyle H\equiv G}$Si y sólo si ${\displaystyle H^{*}\cong G^{*}}$

Si, además, la permutación es la identidad, se dice que es igual a , y se escribe . Nótese que, con esta definición de igualdad, los grafos son autoduales: ${\displaystyle \pi }$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H=G}$

${\displaystyle \left(H^{*}\right)^{*}=H}$

Un automorfismo de hipergrafo es un isomorfismo de un conjunto de vértices en sí mismo, es decir, un reetiquetado de vértices. El conjunto de automorfismos de un hipergrafo H (= ( X ,  E )) es un grupo bajo composición, llamado grupo de automorfismos del hipergrafo y escrito Aut( H ).

Ejemplos

Consideremos el hipergrafo con aristas ${\displaystyle H}$

${\displaystyle H=\lbrace e_{1}=\lbrace a,b\rbrace ,e_{2}=\lbrace b,c\rbrace ,e_{3}=\lbrace c,d\rbrace ,e_{4}=\lbrace d,a\rbrace ,e_{5}=\lbrace b,d\rbrace ,e_{6}=\lbrace a,c\rbrace \rbrace }$

y

${\displaystyle G=\lbrace f_{1}=\lbrace \alpha ,\beta \rbrace ,f_{2}=\lbrace \beta ,\gamma \rbrace ,f_{3}=\lbrace \gamma ,\delta \rbrace ,f_{4}=\lbrace \delta ,\alpha \rbrace ,f_{5}=\lbrace \alpha ,\gamma \rbrace ,f_{6}=\lbrace \beta ,\delta \rbrace \rbrace }$

Entonces claramente y son isomorfos (con , etc. ), pero no son fuertemente isomorfos. Así, por ejemplo, en , el vértice se encuentra con las aristas 1, 4 y 6, de modo que, ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle \phi (a)=\alpha }$ ${\displaystyle H}$ ${\displaystyle a}$

${\displaystyle e_{1}\cap e_{4}\cap e_{6}=\lbrace a\rbrace }$

En el grafo , no existe ningún vértice que corte las aristas 1, 4 y 6: ${\displaystyle G}$

${\displaystyle f_{1}\cap f_{4}\cap f_{6}=\varnothing }$

En este ejemplo, y son equivalentes, y los duales son fuertemente isomorfos: . ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H\equiv G}$ ${\displaystyle H^{*}\cong G^{*}}$

Simetría

ElEl rango de un hipergrafoes la cardinalidad máxima de cualquiera de las aristas del hipergrafo. Si todas las aristas tienen la misma cardinalidadk, se dice que el hipergrafo esuniformeok-uniforme, o se denominak-hipergrafo. Un grafo es simplemente un hipergrafo 2-uniforme. ${\displaystyle r(H)}$ ${\displaystyle H}$

El grado d(v) de un vértice v es el número de aristas que lo contienen. H es k-regular si cada vértice tiene grado k .

El dual de un hipergrafo uniforme es regular y viceversa.

Dos vértices x e y de H se denominan simétricos si existe un automorfismo tal que . Se dice que dos aristas y son simétricas si existe un automorfismo tal que . ${\displaystyle \phi (x)=y}$ ${\displaystyle e_{i}}$ ${\displaystyle e_{j}}$ ${\displaystyle \phi (e_{i})=e_{j}}$

Se dice que un hipergrafo es transitivo respecto de los vértices (o simétrico respecto de los vértices ) si todos sus vértices son simétricos. De manera similar, un hipergrafo es transitivo respecto de las aristas si todas sus aristas son simétricas. Si un hipergrafo es simétrico respecto de las aristas y de los vértices, entonces el hipergrafo es simplemente transitivo .

Debido a la dualidad del hipergrafo, el estudio de la transitividad de los bordes es idéntico al estudio de la transitividad de los vértices.

Particiones

Un teorema de partición debido a E. Dauber ^[37] establece que, para un hipergrafo transitivo de aristas , existe una partición ${\displaystyle H=(X,E)}$

${\displaystyle (X_{1},X_{2},\cdots ,X_{K})}$

del conjunto de vértices tal que el subhipergrafo generado por es transitivo para cada , y tal que ${\displaystyle X}$ ${\displaystyle H_{X_{k}}}$ ${\displaystyle X_{k}}$ ${\displaystyle 1\leq k\leq K}$

${\displaystyle \sum _{k=1}^{K}r\left(H_{X_{k}}\right)=r(H)}$

¿Dónde está el rango de H ? ${\displaystyle r(H)}$

Como corolario, un hipergrafo transitivo de aristas que no es transitivo de vértices es bicolor.

La partición de gráficos (y en particular, la partición de hipergráficos) tiene muchas aplicaciones para el diseño de circuitos integrados ^[38] y la computación paralela . ^{[39] [40] [41]} Los algoritmos de partición de hipergráficos eficientes y escalables también son importantes para procesar hipergráficos a gran escala en tareas de aprendizaje automático. ^[7]

Otras generalizaciones

Una posible generalización de un hipergrafo es permitir que las aristas apunten a otras aristas. Hay dos variaciones de esta generalización. En una, las aristas no solo consisten en un conjunto de vértices, sino que también pueden contener subconjuntos de vértices, subconjuntos de subconjuntos de vértices y así sucesivamente hasta el infinito . En esencia, cada arista es solo un nodo interno de un árbol o grafo acíclico dirigido , y los vértices son los nodos de las hojas. Un hipergrafo es entonces solo una colección de árboles con nodos comunes compartidos (es decir, un nodo interno o una hoja dados pueden aparecer en varios árboles diferentes). Por el contrario, cada colección de árboles puede entenderse como este hipergrafo generalizado. Dado que los árboles se utilizan ampliamente en la informática y en muchas otras ramas de las matemáticas, se podría decir que los hipergrafos también aparecen de forma natural. Así, por ejemplo, esta generalización surge de forma natural como un modelo de álgebra de términos ; las aristas corresponden a términos y los vértices corresponden a constantes o variables.

Para un hipergrafo de este tipo, la pertenencia al conjunto proporciona entonces un ordenamiento, pero el ordenamiento no es ni un orden parcial ni un preorden , ya que no es transitivo. El grafo correspondiente al grafo de Levi de esta generalización es un grafo acíclico dirigido . Considérese, por ejemplo, el hipergrafo generalizado cuyo conjunto de vértices es y cuyas aristas son y . Entonces, aunque y , no es cierto que . Sin embargo, el cierre transitivo de la pertenencia al conjunto para tales hipergrafos induce un orden parcial , y "aplana" el hipergrafo en un conjunto parcialmente ordenado . ${\displaystyle V=\{a,b\}}$ ${\displaystyle e_{1}=\{a,b\}}$ ${\displaystyle e_{2}=\{a,e_{1}\}}$ ${\displaystyle b\in e_{1}}$ ${\displaystyle e_{1}\in e_{2}}$ ${\displaystyle b\in e_{2}}$

Alternativamente, se puede permitir que las aristas apunten a otras aristas, independientemente del requisito de que las aristas estén ordenadas como grafos dirigidos y acíclicos. Esto permite grafos con bucles de aristas, que no necesitan contener vértices en absoluto. Por ejemplo, considere el hipergrafo generalizado que consta de dos aristas y , y cero vértices, de modo que y . Como este bucle es infinitamente recursivo, los conjuntos que son las aristas violan el axioma de fundación . En particular, no hay un cierre transitivo de pertenencia al conjunto para tales hipergrafos. Aunque tales estructuras pueden parecer extrañas al principio, se pueden entender fácilmente al notar que la generalización equivalente de su grafo de Levi ya no es bipartita , sino que es simplemente un grafo dirigido general . ${\displaystyle e_{1}}$ ${\displaystyle e_{2}}$ ${\displaystyle e_{1}=\{e_{2}\}}$ ${\displaystyle e_{2}=\{e_{1}\}}$

La matriz de incidencia generalizada para estos hipergrafos es, por definición, una matriz cuadrada, de rango igual al número total de vértices más las aristas. Por lo tanto, para el ejemplo anterior, la matriz de incidencia es simplemente

${\displaystyle \left[{\begin{matrix}0&1\\1&0\end{matrix}}\right].}$

Véase también

• BF-graph  – Tipo de hipergrafo dirigido
• Diseño combinatorio  – Disposición simétrica de conjuntos finitos
• Gráfico factorial  : gráfico bipartito que representa la factorización de una función.Pages displaying wikidata descriptions as a fallback
• Greedoid  : sistema de conjuntos utilizado en la optimización voraz
• Estructura de incidencia  : sistema matemático abstracto de dos tipos de objetos y una relación entre ellos.
• Multigrafo  : gráfico con múltiples aristas entre dos vértices
• Sistema P  – Modelo computacional
• Multiplicación de matrices dispersas por vectores  : rutina de cálculo
• Red de Petri  : modelo para describir sistemas distribuidosPages displaying short descriptions of redirect targets

Notas

1. Valdivia, Paola; Buono, Paolo; Plaisant, Catherine; Dufournaud, Nicole; Fekete, Jean-Daniel (2020). "Análisis de hipergrafos dinámicos con visualización de hipergrafos ordenados agregados en paralelo" (PDF) . IEEE Transactions on Visualization and Computer Graphics . 26 (1). IEEE: 12. doi :10.1109/TVCG.2019.2933196. eISSN  1941-0506. ISSN  1077-2626. PMID  31398121. S2CID  199518871. Archivado (PDF) desde el original el 26 de enero de 2021 . Consultado el 8 de septiembre de 2020 .
2. Ouvrard, Xavier (2020), "Hipergrafos: una introducción y revisión", arXiv : 2002.05014 [cs.DM].
3. Haussler, David ; Welzl, Emo (1987), "ε-nets y consultas de rango simplex", Geometría discreta y computacional , 2 (2): 127–151, doi : 10.1007/BF02187876 , MR  0884223.
4. Pearl, Judea (1984). Heurística: estrategias de búsqueda inteligente para la resolución de problemas informáticos. Addison-Wesley Publishing Company. pág. 25. ISBN 978-0-201-05594-8Archivado desde el original el 4 de febrero de 2023. Consultado el 12 de junio de 2021 .
5. Feige, Uriel; Kim, Jeong Han; Ofek, Eran (2006). Testigos de la no satisfacibilidad de fórmulas 3CNF aleatorias densas. 47.º Simposio anual IEEE sobre fundamentos de la informática (FOCS'06). IEEE. págs. 497–508. doi :10.1109/FOCS.2006.78. Archivado desde el original el 27 de enero de 2021. Consultado el 20 de enero de 2021 .
6. Beeri, C.; Fagin, R .; Maier, D.; Yannakakis, M. (1983). "Sobre la conveniencia de los esquemas de bases de datos acíclicos" (PDF) . Revista de la ACM . 30 (3): 479–513. doi :10.1145/2402.322389. S2CID  2418740. Archivado (PDF) desde el original el 21 de abril de 2021 . Consultado el 3 de enero de 2021 .
7. Huang, Jin; Zhang, Rui; Yu, Jeffrey Xu (2015). "Aprendizaje y procesamiento de hipergrafos escalables". Conferencia internacional IEEE sobre minería de datos de 2015 (PDF) . págs. 775–780. doi :10.1109/ICDM.2015.33. ISBN 978-1-4673-9504-5. S2CID  5130573. Archivado (PDF) del original el 26 de enero de 2021. Consultado el 8 de enero de 2021 .
8. Brasil, M; Zachariasen, M (2015). "Árboles de Steiner en grafos e hipergrafos". Árboles de interconexión óptima en el plano . Algoritmos y combinatoria. Vol. 29. Springer. págs. 301–317. doi :10.1007/978-3-319-13915-9_5. ISBN . 978-3-319-13915-9Archivado desde el original el 29 de enero de 2021. Consultado el 20 de enero de 2021 .
9. Zhou, Dengyong; Huang, Jiayuan; Scholkopf, Bernhard (2006), "Aprendizaje con hipergrafos: agrupamiento, clasificación e incrustación", Avances en sistemas de procesamiento de información neuronal , MIT Press, págs. 1601–8, ISBN 9780262256919, archivado del original el 22 de octubre de 2021 , consultado el 24 de julio de 2021
10. Ghoshal, Gourab; Zlatic, Vinko; Caldarelli, Guido; Newman, Mark EJ (2009), "Hipergrafos aleatorios y sus aplicaciones", Physical Review E , 79 (6): 066118, arXiv : 0903.0419 , Bibcode :2009PhRvE..79f6118G, doi :10.1103/PhysRevE.79.066118, PMID  19658575, S2CID  6391099
11. Tan, Shulong; Bu, Jiajun; Chen, Chun; Xu, Bin; Wang, Can; He, Xiaofei (octubre de 2011), "Uso de información enriquecida de las redes sociales para la recomendación de música a través del modelo de hipergrafo", ACM Transactions on Multimedia Computing, Communications, and Applications , 7S (1), Artículo 22, Bibcode :2011smma.book..213T, doi :10.1145/2037676.2037679, S2CID  432036
12. Liu, Qingshan; Huang, Yuchi; Metaxas, Dimitris N. (2013), "Hipergrafo con muestreo para recuperación de imágenes", Pattern Recognition , 44 (10–11): 2255–2262, doi :10.1016/j.patcog.2010.07.014
13. Patro, Rob; Kingsoford, Carl (2013), "Predicción de interacciones de proteínas mediante inferencia parsimoniosa de la historia de la red", Bioinformatics , 29 (10–11): 237–246, doi :10.1093/bioinformatics/btt224, PMC 3694678 , PMID  23812989 
14. Gao, Tue; Wang, Meng; Zha, Zheng-Jun; Shen, Jialie; Li, Xuelong; Wu, Xindong (2013), "Aprendizaje de relevancia conjunta visual-textual para búsqueda social de imágenes basada en etiquetas", IEEE Transactions on Image Processing , 22 (1): 363–376, Bibcode :2013ITIP...22..363Y, doi :10.1109/tip.2012.2202676, PMID  22692911, S2CID  7432373, archivado desde el original el 23 de septiembre de 2017 , consultado el 22 de septiembre de 2017
15. Tian, ​​Ze; Hwang, TaeHyun; Kuang, Rui (2009), "Un algoritmo de aprendizaje basado en hipergrafos para clasificar la expresión genética y los datos arrayCGH con conocimiento previo", Bioinformatics , 25 (21): 2831–2838, doi : 10.1093/bioinformatics/btp467 , PMID  19648139
16. Goldstein, A. (1982). "Una base de datos de hipergrafos dirigidos: un modelo para la planta telefónica de bucle local". Bell System Technical Journal . 61 (9): 2529–54. doi :10.1002/j.1538-7305.1982.tb03439.x. S2CID  11290643.
17. Ranshous, Stephen; Joslyn, Cliff; Kreyling, Sean; Nowak, Kathleen; Samatova, Nagiza; West, Curtis; Winters, Samuel (2017). Minería de patrones de intercambio en el hipergrafo dirigido por transacciones de Bitcoin (PDF) . Criptografía financiera y seguridad de datos. Springer. doi :10.1007/978-3-319-70278-0_16. Archivado (PDF) desde el original el 2021-07-15 . Consultado el 2021-01-20 .
18. Ausiello, Giorgio; Laura, Luigi (2017). "Hipergrafos dirigidos: Introducción y algoritmos fundamentales - Una revisión". Ciencias de la Computación Teórica . 658 : 293–306. doi : 10.1016/j.tcs.2016.03.016 .
19. Gallo, G.; Longo, G.; Pallottino, S.; Nguyen, S. (1993). "Hipergrafos dirigidos y aplicaciones". Matemáticas Aplicadas Discretas . 42 (2–3): 177–201. doi : 10.1016/0166-218X(93)90045-P .
20. Sander, G. (2003), "Diseño de hipergrafos dirigidos con hiperaristas ortogonales", Proc. 11th International Symposium on Graph Drawing (GD 2003) , Notas de clase en informática , vol. 2912, Springer, págs. 381–6, ISBN 978-3-540-24595-7, archivado desde el original el 18 de julio de 2011 , consultado el 17 de mayo de 2010.
21. Eschbach, Thomas; Günther, Wolfgang; Becker, Bernd (2006), "Dibujo de hipergrafos ortogonales para una mejor visibilidad" (PDF) , Journal of Graph Algorithms and Applications , 10 (2): 141–157, doi : 10.7155/jgaa.00122 , archivado (PDF) desde el original el 2011-07-18 , consultado el 2010-05-17.
22. Mäkinen, Erkki (1990), "Cómo dibujar un hipergrafo", Revista internacional de matemáticas informáticas , 34 (3): 177–185, doi :10.1080/00207169008803875.
23. Bertault, François; Eades, Peter (2001), "Dibujo de hipergrafos en el subconjunto estándar", Graph Drawing , Lecture Notes in Computer Science, vol. 1984, Springer-Verlag, págs. 45-76, doi : 10.1007/3-540-44541-2_15 , ISBN 978-3-540-41554-1.
24. Naheed Anjum, Arafat; Bressan, Stéphane (2017), "Dibujo de hipergrafos mediante colocación dirigida por fuerza", Aplicaciones de bases de datos y sistemas expertos , Lecture Notes in Computer Science, vol. 10439, Springer International Publishing, págs. 387–394, doi :10.1007/978-3-319-64471-4_31, ISBN 978-3-319-64470-7.
25. Kaufmann, Michael; van Kreveld, Marc; Speckmann, Bettina (2009), "Dibujos de subdivisión de hipergrafos", Dibujo gráfico , Lecture Notes in Computer Science, vol. 5417, Springer-Verlag, págs. 396–407, doi : 10.1007/978-3-642-00219-9_39 , ISBN 978-3-642-00218-2.
26. Johnson, David S.; Pollak, HO (2006), "Planaridad de hipergrafos y la complejidad de dibujar diagramas de Venn", Journal of Graph Theory , 11 (3): 309–325, doi :10.1002/jgt.3190110306.
27. Buchin, Kevin; van Kreveld, Marc; Meijer, Henk; Speckmann, Bettina; Verbeek, Kevin (2010), "Sobre soportes planos para hipergrafos", Dibujo gráfico , Lecture Notes in Computer Science, vol. 5849, Springer-Verlag, págs. 345–356, doi : 10.1007/978-3-642-11805-0_33 , ISBN 978-3-642-11804-3.
28. "Vitaly Voloshin: sitio web de coloración de hipergrafías mixtas". spectrum.troy.edu . Archivado desde el original el 20 de enero de 2022 . Consultado el 27 de abril de 2022 .
29. Fagin, Ronald (1 de julio de 1983). "Grados de aciclicidad para hipergrafos y esquemas de bases de datos relacionales". Revista de la ACM . 30 (3): 514–550. doi : 10.1145/2402.322390 . ISSN  0004-5411.
30. Lovász, László ; Plummer, MD (1986), Teoría de correspondencias , Annals of Discrete Mathematics, vol. 29, Holanda Septentrional, ISBN 0-444-87916-1, Sr.  0859549
31. Berge, Claude (1973). Gráficos e hipergráficos . Ámsterdam: Holanda Septentrional. ISBN 0-7204-2450-X.
32. Yu, CT; Özsoyoğlu, MZ (1979). "Un algoritmo para la pertenencia a consultas de árbol de una consulta distribuida" (PDF) . Proc. IEEE COMPSAC : 306–312. doi :10.1109/CMPSAC.1979.762509. Archivado (PDF) desde el original el 2 de septiembre de 2018 . Consultado el 2 de septiembre de 2018 .
33. Graham, MH (1979). "Sobre la relación universal". Informe técnico . Toronto, Ontario, Canadá: Universidad de Toronto.
34. Abiteboul, S .; Hull, RB; Vianu, V. (1995). Fundamentos de bases de datos . Addison-Wesley. ISBN 0-201-53771-0.
35. Tarjan, RE ; Yannakakis, M. (1984). "Algoritmos simples de tiempo lineal para probar la cordalidad de grafos, probar la aciclicidad de hipergrafos y reducir selectivamente los hipergrafos acíclicos". Revista SIAM de Computación . 13 (3): 566–579. doi :10.1137/0213035.
36. Fagin, Ronald (1983). "Grados de aciclicidad para hipergrafos y esquemas de bases de datos relacionales". Revista de la ACM . 30 (3): 514–550. doi : 10.1145/2402.322390 . S2CID  597990.
37. Harary, F. (2018) [1969]. Teoría de grafos. CRC Press. pág. 172. ISBN 978-0-429-96231-8. Archivado desde el original el 4 de febrero de 2023 . Consultado el 12 de junio de 2021 . A continuación, enunciamos un teorema de Elayne Dauber cuyos corolarios describen propiedades de los grafos simétricos lineales. Nótese la observación obvia pero importante de que todo grafo simétrico lineal es regular linealmente.
38. Karypis, G., Aggarwal, R., Kumar, V. y Shekhar, S. (marzo de 1999), "Particionamiento de hipergrafos multinivel: aplicaciones en el dominio VLSI", IEEE Transactions on Very Large Scale Integration (VLSI) Systems , 7 (1): 69–79, CiteSeerX 10.1.1.553.2367 , doi :10.1109/92.748202. {{citation}}: CS1 maint: multiple names: authors list (link)
39. Hendrickson, B., Kolda, TG (2000), "Graph particioning models for parallel computing", Parallel Computing (manuscrito enviado), 26 (12): 1519–1545, doi :10.1016/S0167-8191(00)00048-X, archivado desde el original el 2021-01-26 , consultado el 2018-10-13 .{{citation}}: CS1 maint: multiple names: authors list (link)
40. Catalyurek, UV; Aykanat, C. (1995). Un modelo hipergráfico para mapear cálculos repetidos de productos de matriz dispersa y vector en multicomputadoras . Proc. Conferencia internacional sobre computación de alto rendimiento (HiPC'95).
41. Catalyurek, UV; Aykanat, C. (1999), "Descomposición basada en particionamiento de hipergrafos para multiplicación de vectores de matrices dispersas en paralelo", IEEE Transactions on Parallel and Distributed Systems , 10 (7): 673–693, CiteSeerX 10.1.1.67.2498 , doi :10.1109/71.780863. 

Referencias

• Berge, Claude (1984). Hipergrafos: combinatoria de conjuntos finitos. Elsevier. ISBN 978-0-08-088023-5.
• Berge, C.; Ray-Chaudhuri, D. (2006). Hypergraph Seminar: Ohio State University, 1972. Lecture Notes in Mathematics. Vol. 411. Springer. ISBN 978-3-540-37803-7.
• "Hipergrafo", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Bretto, Alain (2013). Teoría de los hipergrafos: una introducción. Springer. ISBN 978-3-319-00080-0.
• Voloshin, Vitaly I. (2002). Coloración de hipergrafos mixtos: teoría, algoritmos y aplicaciones: teoría, algoritmos y aplicaciones. Monografías del Instituto Fields. Vol. 17. Sociedad Americana de Matemáticas. ISBN 978-0-8218-2812-0.
• Voloshin, Vitaly I. (2009). Introducción a la teoría de grafos e hipergrafos. Nova Science. ISBN 978-1-61470-112-5.
• Este artículo incorpora material de hypergraph en PlanetMath , que está licenciado bajo la Licencia Creative Commons Atribución/Compartir-Igual .

Enlaces externos

• PAOHVis: sistema PAOHVis de código abierto para visualizar hipergráficos dinámicos.