hipergrafo

Generalización de la teoría de grafos.

Un ejemplo de 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 hipergráfico 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 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\})\}}$

En matemáticas , un hipergrafo 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 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 hiperborde ; 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 que tiene . El tamaño del hipergráfico es el número de aristas . El orden de una arista en un hipergrafo dirigido es : es decir, el número de vértices en su cola seguido del 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 desde un gráfico dirigido a un hipergráfico dirigido al definir la cabeza o la cola de cada borde como un conjunto de vértices ( o ) en lugar de como un solo vértice. Un gráfico es entonces el caso especial en el que cada uno de estos conjuntos contiene un solo elemento. Por lo tanto, cualquier concepto teórico de grafos estándar que sea independiente de los órdenes de los bordes se generalizará a la teoría de hipergrafos. ${\displaystyle C\subseteq X}$ ${\displaystyle D\subseteq X}$ ${\displaystyle |e|}$

Según una definición, un hipergrafo no dirigido es un hipergrafo dirigido que tiene un conjunto de bordes simétricos: Si entonces . Para simplificar la notación, se pueden eliminar los hiperbordes "duplicados", ya que el modificador "no dirigido" nos informa precisamente que existen: Si entonces , dónde significa implícitamente en . ${\displaystyle (X,E)}$ ${\displaystyle (D,C)\in E}$ ${\displaystyle (C,D)\in E}$ ${\displaystyle (D,C)\in E}$ ${\displaystyle (C,D){\vec {\in }}E}$ ${\displaystyle {\vec {\in }}}$

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 hipergrafías donde todos los hiperbordes tienen la misma cardinalidad; un hipergrafo k-uniforme es un hipergrafo tal que todos sus hipergrafos tienen tamaño k . (En otras palabras, uno de esos hipergrafos es una colección de conjuntos, cada uno de los cuales es un hiperborde que conecta k nodos). Entonces, un hipergrafo de 2 uniformes es un gráfico, un hipergráfico de 3 uniformes es una colección de triples desordenados, y así sucesivamente. Un hipergrafo 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, existe un "gráfico de incidencia" bipartito o " gráfico de Levi " correspondiente a cada hipergráfico y, a la inversa, cada gráfico bipartito puede considerarse como el gráfico de incidencia de un hipergráfico cuando es de 2 colores y se indica qué clase de color corresponde a los vértices del hipergrafo y cuál a los bordes del hipergrafo.

Los hipergrafos tienen muchos otros nombres. En geometría computacional , un hipergrafo no dirigido a veces puede denominarse espacio de rango y luego los hipergrafos se denominan 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 alguna literatura, los bordes se denominan hipervínculos o conectores . ^[3]

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

Aplicaciones

Los hipergráficos no dirigidos son útiles para modelar cosas como problemas de satisfacibilidad, ^[4] bases de datos, ^[5] aprendizaje automático, ^[6] y problemas de árbol de Steiner . ^[7] Se han utilizado ampliamente en tareas de aprendizaje automático como modelo de datos y regularización de clasificadores (matemáticas) . ^[8] Las aplicaciones incluyen sistemas de recomendación (comunidades como hiperbordes), ^{[9] [10]} recuperación de imágenes (correlaciones como hiperbordes), ^[11] y bioinformática (interacciones bioquímicas como hiperbordes). ^[12] Las técnicas representativas de aprendizaje de hipergrafos incluyen la agrupación espectral de hipergrafos que extiende la teoría del grafo espectral con hipergrafos laplacianos, ^[13] y el aprendizaje semisupervisado de hipergrafos que introduce un costo estructural adicional de hipergrafos para restringir los resultados del aprendizaje. ^[14] Para hipergráficos a gran escala, también está disponible un marco distribuido ^[6] creado con Apache Spark .

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

Generalizaciones de conceptos a partir de gráficos.

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

• Coincidencia en hipergrafías ;
• Cobertura de vértices en hipergrafías (también conocida como: transversal );
• Gráfico lineal de un hipergrafo ;
• Gramática de hipergrafos : creada 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 hipergrafías uniformes;
• Teoremas de tipo Hall para hipergrafos .

En hipergrafías dirigidas: cierre transitivo y problemas del camino más corto. ^[17]

Dibujo de hipergrafo

Este diagrama de circuito se puede interpretar como el 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.

Aunque los hipergráficos son más difíciles de dibujar en papel que los gráficos, varios investigadores han estudiado métodos para visualizarlos.

En una posible representación visual de los hipergráficos, 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 hipergráfico se representan como puntos, discos o cajas, y sus hiperbordes se representan como árboles que tienen los vértices como sus hojas. ^{[19] [20]} Si los vértices se representan como puntos, los hiperbordes también se pueden mostrar como curvas suaves que conectan conjuntos de puntos, o como curvas cerradas simples que encierran conjuntos de puntos. ^{[21] [22] [23]}

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

En otro estilo de visualización de hipergrafo, el modelo de subdivisión del dibujo de hipergrafo, ^[24] el plano se subdivide en regiones, cada una de las cuales representa un único vértice del hipergrafo. Los hiperbordes del hipergráfico están representados por subconjuntos contiguos de estas regiones, que pueden indicarse coloreando, dibujando contornos alrededor de ellos, o ambos. Un diagrama de Venn de orden n , por ejemplo, puede verse como un dibujo de subdivisión de un hipergráfico con n hiperbordes (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 de tiempo polinomial de gráficos planos , es NP-completo determinar si un hipergráfico tiene un dibujo de subdivisión plana, ^[25] pero la existencia de un dibujo de este tipo se puede probar de manera eficiente cuando el patrón de adyacencia de los gráficos planos es NP-completo. Las regiones están obligadas a ser una ruta, un ciclo o un árbol. ^[26]

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

Coloración de hipergrafía

La coloración clásica del hipergrafo consiste en asignar uno de los colores del conjunto a cada vértice de un hipergrafo de tal manera que cada hiperborde contenga al menos dos vértices de colores distintos. En otras palabras, no debe haber ningún hiperborde monocromático con cardinalidad al menos 2. En este sentido, es una generalización directa de la coloración de gráficos. El número mínimo de colores distintos utilizados entre todos los colorantes se denomina número cromático de un hipergráfico. ${\displaystyle \{1,2,3,...,\lambda \}}$

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

Existen muchas generalizaciones de la coloración hipergráfica clásica. Uno de ellos es la llamada coloración hipergráfica mixta, cuando se permiten bordes monocromáticos. Algunos hipergráficos mixtos no se pueden colorear en ningún número de colores. Se desconoce un criterio general para la incolorabilidad. Cuando un hipergráfico 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. ^[27]

Propiedades de los hipergrafos

Un hipergrafo puede tener varias propiedades, como por ejemplo:

• 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.
• Sencillo : no tiene bucles ni bordes repetidos.
• ${\displaystyle d}$-regular : cada vértice tiene grado , es decir, está contenido exactamente en hiperbordes. ${\displaystyle d}$ ${\displaystyle d}$
• Bicolorable : sus vértices se pueden dividir en dos clases U y V de tal manera que cada hiperborde con cardinalidad al menos 2 contenga al menos un vértice de ambas clases. Un término alternativo es Propiedad B.
  • Dos propiedades más fuertes son bipartitas y equilibradas .
• ${\displaystyle k}$-uniforme : cada hiperborde contiene precisamente vértices. ${\displaystyle k}$
• ${\displaystyle k}$-partite : los vértices se dividen en partes y cada hiperborde contiene precisamente un vértice de cada tipo. ${\displaystyle k}$
  • Cada hipergrafo -partito (para ) es a la vez -uniforme y bipartito (y bicolorable). ${\displaystyle k}$ ${\displaystyle k\geq 2}$ ${\displaystyle k}$
• Reducido : ^[28] ningún hiperborde es un subconjunto estricto de otro hiperborde; de manera equivalente, cada hiperborde es máximo para la inclusión. La reducción de un hipergrafo es el hipergrafo reducido que se obtiene eliminando cada hiperborde que se incluye en otro hiperborde.
• Cerrado hacia abajo : cada subconjunto de los bordes de un hipergráfico no dirigido también es un hiperborde. Un hipergrafo cerrado hacia abajo generalmente se denomina complejo simplicial abstracto . Generalmente no se reduce, a menos que todos los hiperbordes tengan cardinalidad 1.
  • Un complejo simplicial abstracto con la propiedad de aumento se llama matroide .
• Laminar : para dos hiperbordes cualesquiera, o son disjuntos o uno está incluido en el otro. En otras palabras, el conjunto de hiperbordes forma una familia de conjuntos laminares .

Hipergrafos relacionados

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

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

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

y tener el borde puesto

${\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 aristas respectivamente. ${\displaystyle I_{v}}$ ${\displaystyle I_{e}}$

Un subhipergrafo es un hipergrafo al que se le han eliminado 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. ^{[29] : 468}

Una extensión de un subhipergrafo es un hipergrafo donde cada hiperborde está parcialmente contenido en el subhipergrafo y está completamente contenido 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 al que se le han eliminado algunos bordes. ^{[29] : 468} Dado un subconjunto del conjunto de índices de borde, el hipergráfico parcial generado por es el hipergráfico ${\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 se intercambian, 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 gráfico conectado G con el mismo conjunto de vértices que un hipergráfico conectado H es un gráfico anfitrión para H si cada hiperborde de H induce un subgrafo conectado en G. Para un hipergrafo H desconectado , G es un gráfico anfitrión si hay una biyección entre los componentes conectados de G y de H , de modo que cada componente conectado G' de G es un anfitrión del H' correspondiente .

La sección de 2 (o gráfico de camarilla , que representa el gráfico , el gráfico primario , el gráfico de Gaifman ) de un hipergrafo es el gráfico con los mismos vértices del hipergrafo y bordes entre todos los pares de vértices contenidos en el mismo hipergrafo.

Matriz de incidencia

Deja y . Cada 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 hipergráfico llamado dual de , donde es un conjunto de m elementos y es un conjunto de n elementos de subconjuntos de . Para y si y sólo 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 colas de cada hiperborde se denotan por y respectivamente. ^[18] 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áfico 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 gráfico bipartito con partes fijas y sin nodos desconectados en la segunda parte representa algún hipergráfico de la manera descrita anteriormente. Este gráfico bipartito también se llama gráfico 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 gráfico. En el caso de un gráfico, la matriz de adyacencia es una matriz cuadrada que indica si los pares de vértices son adyacentes . Asimismo, podemos definir la matriz de adyacencia para un hipergrafo en general donde los hiperbordes 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

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

Claude Berge dio una primera definición de aciclicidad para hipergrafos : ^[30] un hipergrafo es Berge-acíclico si su gráfico de incidencia (el gráfico 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 comprobar en tiempo lineal mediante una exploración del gráfico 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 del hipergrafo, ^[5] más tarde denominada α-aciclicidad. Esta noción de aciclicidad es equivalente a que el hipergrafo sea conforme (cada camarilla del grafo primario está cubierta por algún hiperborde) y que su grafo primario sea cordal ; también es equivalente a la reducibilidad al gráfico vacío a través del algoritmo GYO ^{[31] [32]} (también conocido como algoritmo de Graham), un proceso iterativo confluente que elimina los hiperbordes utilizando una definición generalizada de orejas . 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. ^[33] 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. ^[34]

Tenga en cuenta que la α-aciclicidad tiene la propiedad contraria a la intuición de que agregar hiperaristas a un hipergrafo α-cíclico puede convertirlo en α-acíclico (por ejemplo, agregar un hiperarista que contenga todos los vértices del hipergrafo siempre lo convertirá en α-acíclico). Motivado en parte por esta deficiencia percibida, Ronald Fagin ^[35] definió las nociones más fuertes de β-aciclicidad y γ-aciclicidad. Podemos afirmar la β-aciclicidad como el requisito de que todos los subhipergrafos del hipergrafo sean α-acíclicos, lo que equivale ^[35] a una definición anterior de Graham. ^[32] La noción de γ-aciclicidad es una condición más restrictiva que equivale 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 se pueden probar en tiempo polinomial .

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

Isomorfismo, simetría e igualdad.

Un homomorfismo de hipergrafo es un mapa del conjunto de vértices de un hipergrafo a otro de modo que cada borde se asigna a otro borde.

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 llama entonces isomorfismo de las gráficas. Tenga en cuenta que ${\displaystyle \phi }$

${\displaystyle H\simeq G}$si y solo 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 si la permutación es la identidad. Entonces se escribe . Tenga en cuenta que todos los gráficos fuertemente isomórficos son isomórficos, 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 solo si ${\displaystyle H^{*}\cong G^{*}}$

Si, además, la permutación es la identidad, se dice que es igual a , y se escribe . Tenga en cuenta que, con esta definición de igualdad, las gráficas 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 vértice colocado 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

Considere 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. Entonces, por ejemplo, en , el vértice se encuentra con los bordes 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 gráfico , no existe ningún vértice que coincida con los bordes 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 isomórficos: . ${\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 los bordes del hipergrafo. Si todas las aristas tienen la misma cardinalidadk, se dice que el hipergrafo esuniformeok-uniforme, o se llamak-hipergrafo. Una gráfica es solo una hipergrafía de 2 uniformes. ${\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 xey de H se llaman simétricos si existe un automorfismo tal que . Dos aristas y se dicen 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 de vértice (o simétrico de vértice ) si todos sus vértices son simétricos. De manera similar, un hipergrafo es transitivo de aristas si todas las aristas son simétricas. Si un hipergrafo es simétrico tanto en los bordes como en los vértices, entonces el hipergrafo es simplemente transitivo .

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

Particiones

Un teorema de partición debido a E. Dauber ^[36] 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 sea transitivo para cada uno , 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 bordes 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 ^[37] y la computación paralela . ^{[38] [39] [40]} 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. ^[6]

Más generalizaciones

Una posible generalización de un hipergráfico es permitir que los bordes apunten a otros bordes. Hay dos variaciones de esta generalización. En uno, las aristas no sólo constan de un conjunto de vértices, sino que también pueden contener subconjuntos de vértices, subconjuntos de subconjuntos de vértices, etc. hasta el infinito . En esencia, cada arista es solo un nodo interno de un árbol o gráfico acíclico dirigido , y los vértices son los nodos hoja. Un hipergráfico es entonces simplemente una colección de árboles con nodos comunes y compartidos (es decir, un nodo interno u hoja determinados pueden aparecer en varios árboles diferentes). Por el contrario, cada colección de árboles puede entenderse como este hipergráfico 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 hipergráficos también aparecen de forma natural. Así, por ejemplo, esta generalización surge naturalmente como modelo del álgebra de términos ; Las aristas corresponden a términos y los vértices corresponden a constantes o variables.

Para tal hipergrafo, la membresía del conjunto proporciona un orden, pero el orden no es ni un orden parcial ni un preorden , ya que no es transitivo. La gráfica correspondiente a la gráfica de Levi de esta generalización es una gráfica acíclica dirigida . Considere, 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 a conjuntos 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 los bordes apunten a otros bordes, independientemente del requisito de que los bordes estén ordenados como gráficos acíclicos dirigidos. Esto permite gráficos con bucles de borde, que no necesitan contener ningún vértice. 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 fundamento . En particular, no existe un cierre transitivo de pertenencia a conjuntos para dichos hipergráficos. Aunque tales estructuras pueden parecer extrañas al principio, pueden entenderse fácilmente si se observa que la generalización equivalente de su gráfico de Levi ya no es bipartita , sino que es simplemente un gráfico dirigido general . ${\displaystyle e_{1}}$ ${\displaystyle e_{2}}$ ${\displaystyle e_{1}=\{e_{2}\}}$ ${\displaystyle e_{2}=\{e_{1}\}}$

La matriz de incidencia generalizada para tales hipergráficos es, por definición, una matriz cuadrada, de un rango igual al número total de vértices más aristas. Así, para el ejemplo anterior, la matriz de incidencia es simplemente

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

Ver también

• Gráfico BF
• Diseño combinatorio
• Gráfico de factores
• Codicioso
• Estructura de incidencia
• multigrafo
• sistema P
• Multiplicación de vectores y matrices dispersas
• Red de Petri

Notas

1. , Paola; Buono, Paolo; Plaisant, Catalina; Dufournaud, Nicole; Fekete, Jean-Daniel (2020). "Análisis de hipergráficos dinámicos con visualización de hipergráficos ordenados agregados paralelos" (PDF) . Transacciones IEEE sobre visualización y gráficos por computadora . IEEE. 26 (1): 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. Haussler, David ; Welzl, Emo (1987), "ε-nets y consultas de rango simplex", Geometría computacional y discreta , 2 (2): 127–151, doi : 10.1007/BF02187876 , SEÑOR  0884223.
3. Perla, Judea (1984). Heurística: estrategias de búsqueda inteligente para la resolución de problemas informáticos. Compañía editorial Addison-Wesley. pag. 25.ISBN _ 978-0-201-05594-8. Archivado desde el original el 4 de febrero de 2023 . Consultado el 12 de junio de 2021 .
4. Feige, Uriel; Kim, Jeong Han; Ofek, Eran (2006). Testigos de insatisfacción de fórmulas densas aleatorias 3CNF. 47º Simposio anual del 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 .
5. 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 .
6. Huang, Jin; Zhang, Rui; Yu, Jeffrey Xu (2015). "Aprendizaje y procesamiento de hipergráficos escalables". Conferencia internacional IEEE 2015 sobre minería de datos (PDF) . págs. 775–780. doi :10.1109/ICDM.2015.33. ISBN 978-1-4673-9504-5. S2CID  5130573. Archivado (PDF) desde el original el 26 de enero de 2021 . Consultado el 8 de enero de 2021 .
7. Brasil, M; Zachariasen, M (2015). "Árboles de Steiner en gráficos e hipergrafías". Árboles de interconexión óptimos en el plano . Algoritmos y Combinatoria. vol. 29. Saltador. págs. 301–317. doi :10.1007/978-3-319-13915-9_5. ISBN 978-3-319-13915-9. Archivado desde el original el 29 de enero de 2021 . Consultado el 20 de enero de 2021 .
8. Zhou, Dengyong; Huang, Jiayuan; Scholkopf, Bernhard (2006), "Aprendizaje con hipergrafías: agrupación, clasificación e incrustación", Avances en sistemas de procesamiento de información neuronal , MIT Press, págs. 1601–8, ISBN 9780262256919, archivado desde el original el 22 de octubre de 2021 , consultado el 24 de julio de 2021
9. Ghoshal, Gourab; Zlatic, Vinko; Caldarelli, Guido; Newman, Mark EJ (2009), "Hypergrafos aleatorios y sus aplicaciones", Physical Review E , 79 (6): 066118, arXiv : 0903.0419 , Bibcode : 2009PhRvE..79f6118G, doi : 10.1103/PhysRevE.79.066118, PMID  19658575, S2 CID  6391099
10. Bronceado, Shulong; Bu, Jiajun; Chen, Chun; Xu, Bin; Wang, puede; Él, Xiaofei (octubre de 2011), "Uso de información rica de las redes sociales para la recomendación de música mediante un modelo de hipergráfico", Transacciones ACM sobre informática, comunicaciones y aplicaciones multimedia , 7S (1), artículo 22, Bibcode : 2011smma.book..213T, doi :10.1145/2037676.2037679, S2CID  432036
11. Liu, Qingshan; Huang, Yuchi; Metaxas, Dimitris N. (2013), "Hypergraph con muestreo para recuperación de imágenes", Reconocimiento de patrones , 44 (10–11): 2255–2262, doi :10.1016/j.patcog.2010.07.014
12. Patro, Rob; Kingsoford, Carl (2013), "Predicción de interacciones de proteínas mediante inferencia parsimoniosa del historial de redes", Bioinformática , 29 (10–11): 237–246, doi :10.1093/bioinformatics/btt224, PMC 3694678 , PMID  23812989 
13. Gao, martes; Wang, Meng; Zha, Zheng-Jun; Shen, Jialie; Li, Xuelong; Wu, Xindong (2013), "Aprendizaje de relevancia conjunta visual-textual para la búsqueda de imágenes sociales 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
14. Tian, ​​Ze; Hwang, Tae Hyun; Kuang, Rui (2009), "Un algoritmo de aprendizaje basado en hipergráficos para clasificar la expresión genética y los datos de arrayCGH con conocimientos previos", Bioinformatics , 25 (21): 2831–2838, doi : 10.1093/bioinformatics/btp467 , PMID  19648139
15. Goldstein, A. (1982). "Una base de datos de hipergrafía dirigida: un modelo para la planta telefónica de bucle local". Revista técnica del sistema Bell . 61 (9): 2529–54. doi :10.1002/j.1538-7305.1982.tb03439.x. S2CID  11290643.{{cite journal}}: CS1 maint: date and year (link)
16. Ranshous, Stephen; Joslyn, acantilado; Kreyling, Sean; Nowak, Kathleen; Samatova, Nagiza; Oeste, Curtis; Inviernos, Samuel (2017). Minería de patrones de intercambio en el hipergráfico dirigido a transacciones de Bitcoin (PDF) . Criptografía financiera y seguridad de datos. Saltador. doi :10.1007/978-3-319-70278-0_16. Archivado (PDF) desde el original el 15 de julio de 2021 . Consultado el 20 de enero de 2021 .
17. Ausiello, Giorgio; Laura, Luigi (2017). "Hipergrafías dirigidas: Introducción y algoritmos fundamentales - Una encuesta". Informática Teórica . 658 : 293–306. doi : 10.1016/j.tcs.2016.03.016 .
18. Gallo, G.; Longo, G.; Palotino, S.; Nguyen, S. (1993). "Hipergrafías dirigidas y aplicaciones". Matemática Aplicada Discreta . 42 (2–3): 177–201. doi : 10.1016/0166-218X(93)90045-P .
19. Sander, G. (2003), "Diseño de hipergrafías dirigidas con hiperbordes ortogonales", Proc. XI Simposio internacional sobre dibujo de gráficos (GD 2003) , Lecture Notes in Computer Science , 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.
20. Eschbach, Thomas; Günther, Wolfgang; Becker, Bernd (2006), "Dibujo de hipergrafía ortogonal para mejorar la visibilidad" (PDF) , Journal of Graph Algorithms and Applications , 10 (2): 141–157, doi : 10.7155/jgaa.00122 , archivado (PDF) del original el 18 de julio de 2011 , consultado el 17 de mayo de 2010.
21. Mäkinen, Erkki (1990), "Cómo dibujar un hipergrafo", Revista Internacional de Matemáticas Informáticas , 34 (3): 177–185, doi :10.1080/00207169008803875.
22. Bertault, François; Eades, Peter (2001), "Dibujo de hipergrafías en el estándar de subconjunto", Dibujo de gráficos , 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.
23. Naheed Anjum, Arafat; Bressan, Stéphane (2017), "Dibujo de hipergrafo mediante colocación dirigida por fuerza", Aplicaciones de sistemas expertos y bases de datos , Apuntes de conferencias sobre informática, vol. 10439, Springer International Publishing, págs. 387–394, doi :10.1007/978-3-319-64471-4_31, ISBN 978-3-319-64470-7.
24. 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.
25. Johnson, David S .; Pollak, HO (2006), "La planaridad del hipergrafo y la complejidad de dibujar diagramas de Venn", Journal of Graph Theory , 11 (3): 309–325, doi :10.1002/jgt.3190110306.
26. 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.
27. "Vitaly Voloshin: sitio web para colorear hipergráficos mixtos". espectro.troy.edu . Archivado desde el original el 2022-01-20 . Consultado el 27 de abril de 2022 .
28. Fagin, Ronald (1 de julio de 1983). "Grados de aciclicidad para hipergráficos y esquemas de bases de datos relacionales". Revista de la ACM . 30 (3): 514–550. doi : 10.1145/2402.322390 . ISSN  0004-5411.
29. Lovász, László ; Plummer, MD (1986), Teoría de correspondencias , Annals of Discrete Mathematics, vol. 29, Holanda Septentrional, ISBN 0-444-87916-1, señor  0859549
30. Bergé, Claude (1973). Gráficos e Hipergrafos . Ámsterdam: Holanda Septentrional. ISBN 0-7204-2450-X.
31. 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 .
32. Graham, MH (1979). "Sobre la relación universal". Reporte técnico . Toronto, Ontario, Canadá: Universidad de Toronto.
33. Abiteboul, S .; Casco, RB; Vianu, V. (1995). Fundamentos de Bases de Datos . Addison-Wesley. ISBN 0-201-53771-0.
34. Tarjan, RE ; Yannakakis, M. (1984). "Algoritmos simples de tiempo lineal para probar la cordalidad de gráficos, probar la aciclicidad de hipergráficos y reducir selectivamente los hipergráficos acíclicos". Revista SIAM de Computación . 13 (3): 566–579. doi :10.1137/0213035.
35. Fagin, Ronald (1983). "Grados de aciclicidad para hipergráficos y esquemas de bases de datos relacionales". Revista de la ACM . 30 (3): 514–550. doi : 10.1145/2402.322390 . S2CID  597990.
36. Harary, F. (2018) [1969]. Teoría de grafos. Prensa CRC. pag. 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 debido a Elayne Dauber cuyos corolarios describen propiedades de gráficos lineales simétricos. Tenga en cuenta la observación obvia pero importante de que todo gráfico linealmente simétrico es linealmente regular.
37. Karypis, G., Aggarwal, R., Kumar, V. y Shekhar, S. (marzo de 1999), "Partición de hipergrafos multinivel: aplicaciones en el dominio VLSI", Transacciones IEEE en sistemas de integración a muy gran escala (VLSI) , 7 (1): 69–79, CiteSeerX 10.1.1.553.2367 , doi :10.1109/92.748202. {{citation}}: CS1 maint: multiple names: authors list (link)
38. Hendrickson, B., Kolda, TG (2000), "Modelos de partición de gráficos para computación paralela", Parallel Computing (manuscrito enviado), 26 (12): 1519–1545, doi :10.1016/S0167-8191(00)00048- X, archivado desde el original el 26 de enero de 2021 , consultado el 13 de octubre de 2018 .{{citation}}: CS1 maint: multiple names: authors list (link)
39. Catalyurek, UV; Aykanat, C. (1995). "Un modelo de hipergráfico para mapear cálculos repetidos de productos vectoriales de matrices dispersas en multicomputadoras ". Proc. Conferencia internacional sobre informática de alto rendimiento (HiPC'95).
40. Catalyurek, UV; Aykanat, C. (1999), "Descomposición basada en partición de hipergrafo para multiplicación de vectores de matriz dispersa paralela", IEEE Transactions on Parallel and Distributed Systems , 10 (7): 673–693, CiteSeerX 10.1.1.67.2498 , doi :10.1109 /71.780863. 

Referencias

• Bergé, Claude (1984). Hipergrafos: combinatoria de conjuntos finitos. Elsevier. ISBN 978-0-08-088023-5.
• Bergé, C.; Ray-Chaudhuri, D. (2006). Seminario Hypergraph: Universidad Estatal de Ohio, 1972. Apuntes de conferencias sobre matemáticas. vol. 411. Saltador. ISBN 978-3-540-37803-7.
• "Hypergraph", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Bretto, Alain (2013). Teoría del hipergrafo: una introducción. Saltador. ISBN 978-3-319-00080-0.
• Voloshin, Vitaly I. (2002). Coloración de hipergrafías mixtas: teoría, algoritmos y aplicaciones: teoría, algoritmos y aplicaciones. Monografías del Fields Institute. vol. 17. Sociedad Matemática Estadounidense. ISBN 978-0-8218-2812-0.
• Voloshin, Vitaly I. (2009). Introducción a la teoría de grafos e hipergrafos. Ciencia nueva. ISBN 978-1-61470-112-5.
• Este artículo incorpora material de Hypergraph en PlanetMath , que tiene la licencia Creative Commons Attribution/Share-Alike License .

enlaces externos

• PAOHVis: sistema PAOHVis de código abierto para visualizar hipergrafías dinámicas.