Hipergrafo

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 .

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]

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]

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]}

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.

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]

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 .

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.

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.}$

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 .

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.}$

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]

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 ).

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^{*}}$

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.

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]

This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. (January 2021) (Learn how and when to remove this message)

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].}$

Wikimedia Commons tiene medios relacionados con Hipergrafos .

• 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 .

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