Hipergrafo

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

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

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

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

Dado un conjunto ${\displaystyle {X}}$ con su conjunto de potencia ${\displaystyle {{\mathcal {P}}\left(X\right)}}$, además un conjunto ${\displaystyle {E}}$ con ${\displaystyle {E\subseteq {\mathcal {P}}\left(X\right)}}$, la pareja ${\displaystyle {\left(X,E\right)}}$ Se denominará hipergrafo no dirigido.

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

Los hipergrafos reciben muchos otros nombres. En geometría computacional , un hipergrafo no dirigido a veces se denomina espacio de rangos , y entonces las hiperaristas se llaman rangos . ^{[ 2 ]} En teoría de juegos cooperativos , los hipergrafos se denominan juegos simples (juegos de votación); esta noción se aplica para resolver problemas en teoría de elección social . En cierta literatura, las aristas se denominan hipervínculos o conectores . ^{[ 3 ]}

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, ^{[ 4 ]} bases de datos, ^{[ 5 ]} aprendizaje automático, ^{[ 6 ]} y problemas de árboles de Steiner . ^{[ 7 ]} Se han utilizado ampliamente en tareas de aprendizaje automático como modelo de datos y regularización de clasificadores . ^{[ 8 ]} Las aplicaciones incluyen sistemas de recomendación (comunidades como hiperaristas), ^{[ 9 ] [ 10 ]} recuperación de imágenes (correlaciones como hiperaristas), ^{[ 11 ]} y bioinformática (interacciones bioquímicas como hiperaristas). ^{[ 12 ]} Las técnicas representativas de aprendizaje de hipergrafos incluyen el agrupamiento espectral de hipergrafos que extiende la teoría espectral de grafos con el laplaciano de hipergrafos, ^{[ 13 ]} y el aprendizaje semisupervisado de hipergrafos que introduce un costo estructural adicional de hipergrafos para restringir los resultados del aprendizaje. ^{[ 14 ]} Para hipergrafos a gran escala, también está disponible un marco distribuido ^{[ 6 ]} construido usando Apache Spark . Puede resultar conveniente estudiar hipergrafos donde todas las hiperaristas tengan la misma cardinalidad; un hipergrafo k-uniforme es un hipergrafo cuyas hiperaristas tienen tamaño k . (En otras palabras, un hipergrafo de este tipo es una colección de conjuntos, donde cada conjunto es una hiperarista que conecta k nodos). Así, un hipergrafo 2-uniforme es un grafo, un hipergrafo 3-uniforme es una colección de ternas no ordenadas, y así sucesivamente.

Los hipergrafos dirigidos pueden utilizarse para modelar aplicaciones de telefonía, ^{[ 15 ]} la detección de blanqueo de capitales , ^{[ 16 ]} la investigación operativa ^{[ 17 ]} y la planificación del transporte. También pueden utilizarse para modelar la satisfacibilidad de Horn . ^{[ 18 ]}

Muchos teoremas y conceptos relacionados con grafos también son válidos para hipergrafos, en particular:

• Emparejamiento en hipergrafos ;
• Cobertura de vértices en hipergrafos (también conocida como: transversal );
• Gráfico de líneas de un hipergrafo ;
• Gramática de hipergrafos : creada mediante la ampliación de 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. ^{[ 17 ]}

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 hipergrafos, similar al estilo estándar de dibujo de grafos en el que se utilizan curvas en el plano para representar las aristas del grafo, 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 hojas. ^{[ 19 ] [ 20 ]} Si los vértices se representan como puntos, las hiperaristas también pueden mostrarse como curvas suaves que conectan conjuntos de puntos, o como curvas cerradas simples que encierran conjuntos de puntos. ^{[ 21 ] [ 22 ] [ 23 ]}

En otro estilo de visualización de hipergrafos, el modelo de subdivisión de dibujo de hipergrafos, ^{[ 24 ]} 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 coloración, dibujando contornos a su alrededor 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). A diferencia del reconocimiento en tiempo polinomial de grafos planares , es NP-completo determinar si un hipergrafo tiene un dibujo de subdivisión planar, ^{[ 25 ]} pero la existencia de un dibujo de este tipo puede probarse eficientemente cuando el patrón de adyacencia de las regiones está restringido a ser un camino, un ciclo o un árbol. ^{[ 26 ]}  

En la figura que encabeza este artículo se muestra una representación alternativa del hipergrafo denominada 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. Si bien se diseñó para hipergrafos dinámicos, también puede utilizarse para hipergrafos simples.

La coloración clásica de hipergrafos consiste en asignar uno de los colores del conjunto.${\displaystyle \{1,2,3,...,\lambda \}}$Se asigna un color a cada vértice de un hipergrafo de tal manera 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.

Los hipergrafos que pueden colorearse con hasta k colores se denominan k-coloreables . Los hipergrafos bipartitos son precisamente los 2-coloreables.

Existen muchas generalizaciones de la coloración clásica de hipergrafos. Una de ellas es la denominada coloración mixta de hipergrafos, en la que se permiten aristas monocromáticas. Algunos hipergrafos mixtos no se pueden colorear con ningún número de colores. Se desconoce un criterio general para determinar si un hipergrafo no se puede colorear. Cuando un hipergrafo mixto se puede colorear, el número mínimo y máximo de colores utilizados se denominan, respectivamente, número cromático inferior y superior. ^{[ 27 ]}

Un hipergrafo puede tener varias propiedades, tales 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.
• Sencillo : no tiene bucles ni bordes repetidos.
• ${\displaystyle d}$-regular - cada vértice tiene grado${\displaystyle d}$, es decir, contenido exactamente${\displaystyle d}$hiperbordes.
• 2-coloreable : sus vértices se pueden particionar en dos clases U y V de tal manera que cada hiperarista con cardinalidad al menos 2 contiene al menos un vértice de ambas clases. Un término alternativo es Propiedad B.
  • Dos propiedades más fuertes son ser bipartito y estar equilibrado .
• ${\displaystyle k}$-uniforme - cada hiperarista contiene precisamente${\displaystyle k}$vértices.
• ${\displaystyle k}$-partición - los vértices se dividen en${\displaystyle k}$partes, y cada hiperarista contiene precisamente un vértice de cada tipo.
  • Cada${\displaystyle k}$Hipergrafo -partito (para${\displaystyle k\geq 2}$) es ambos${\displaystyle k}$-uniforme y bipartito (y 2-coloreable).
• Reducido : ^{[ 28 ]} ninguna hiperarista es un subconjunto estricto de otra hiperarista; equivalentemente, toda hiperarista es máxima para su inclusión. La reducción de un hipergrafo es el hipergrafo reducido que se obtiene al eliminar toda hiperarista que está incluida en otra hiperarista.
• Hipergrafo cerrado hacia abajo : cada subconjunto de aristas de un hipergrafo no dirigido es también una hiperarista. Un hipergrafo cerrado hacia abajo se suele denominar complejo simplicial abstracto . Generalmente 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 cualesquiera dos hiperaristas, 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 .
• Conectados : para todos${\displaystyle S\subseteq X}$con${\displaystyle \emptyset \neq S\neq X}$hay${\displaystyle e\in E}$que cumpla con ambos${\displaystyle S}$y${\displaystyle X\setminus S}$Un hipergrafo que no está conectado se denomina desconectado .

Dado que los enlaces de un hipergrafo pueden tener cualquier cardinalidad, existen varias nociones del concepto de subgrafo, denominados subhipergrafos , hipergrafos parciales e hipergrafos de sección .

Dejar${\displaystyle H=(X,E)}$sea ​​el hipergrafo que consta de vértices

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

y tener el borde establecido

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

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

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

${\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}

Un componente conectado de${\displaystyle H}$es un subhipergrafo conectado maximal de${\displaystyle H}$, es decir, un subhipergrafo${\displaystyle H_{A}}$de${\displaystyle H}$inducido por${\displaystyle A}$de tal manera que${\displaystyle H_{A}}$está conectado y no hay subhipergrafo${\displaystyle H_{A'}}$con${\displaystyle A\subsetneq A'}$está conectado.

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

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

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

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

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

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

El dual${\displaystyle H^{*}}$de${\displaystyle H}$es un hipergrafo cuyos vértices y aristas se intercambian, de modo que los vértices vienen dados por${\displaystyle \lbrace e_{i}\rbrace }$y cuyos bordes están dados por${\displaystyle \lbrace X_{m}\rbrace }$dónde

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

Cuando se define correctamente 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 existe una biyección entre las componentes conexas de G y de H , de tal manera que cada componente conexa G ' de G es un anfitrión del H ' correspondiente .

La sección 2 (o grafo de clique , grafo representativo , grafo primal , grafo de Gaifman ) de un hipergrafo es el grafo con los mismos vértices del hipergrafo y aristas entre todos los pares de vértices contenidos en la misma hiperarista.

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

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

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

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

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

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

Se puede establecer un paralelismo entre la matriz de adyacencia de un hipergrafo y la matriz de adyacencia de un grafo. En el caso de un grafo, la matriz de adyacencia es una matriz cuadrada que indica si pares de vértices son adyacentes . De manera similar, podemos definir la matriz de adyacencia.${\displaystyle A=(a_{ij})}$para un hipergrafo en general donde las hiperaristas${\displaystyle e_{k\leq m}}$tienen pesos reales${\displaystyle w_{e_{k}}\in \mathbb {R} }$con

${\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 grafos no dirigidos ordinarios, para los que existe una única noción natural de ciclos y grafos acíclicos , en el caso de los hipergrafos existen múltiples definiciones naturales no equivalentes de ciclos que se reducen a la noción ordinaria de ciclo cuando se considera el caso de los grafos.

Un homomorfismo de hipergrafos es una función que mapea el conjunto de vértices de un hipergrafo a otro, de manera que cada arista se corresponde con otra arista.

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

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

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

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

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

${\displaystyle H\simeq G}$si y solo si${\displaystyle H^{*}\simeq G^{*}}$.

Cuando las aristas de un hipergrafo están etiquetadas explícitamente, se tiene la noción adicional de isomorfismo fuerte . Se dice que${\displaystyle H}$es fuertemente isomorfo a${\displaystyle G}$si la permutación es la identidad. Entonces se escribe${\displaystyle H\cong G}$Cabe señalar que todos los grafos fuertemente isomorfos son isomorfos, pero no a la inversa.

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${\displaystyle H}$es equivalente a${\displaystyle G}$y escribe${\displaystyle H\equiv G}$si el isomorfismo${\displaystyle \phi }$tiene

${\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${\displaystyle \pi }$es la identidad, uno dice que${\displaystyle H}$igual${\displaystyle G}$y escribe${\displaystyle H=G}$Nótese que, con esta definición de igualdad, los grafos son autoduales:

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

Un automorfismo de hipergrafo es un isomorfismo de un conjunto de vértices en sí mismo, es decir, un cambio de etiquetas de los 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 ). 

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

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

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

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

dónde${\displaystyle r(H)}$es el rango de H.

Como corolario, un hipergrafo transitivo en aristas que no es transitivo en vértices es bicoloreable.

La partición de grafos (y en particular, la partición de hipergrafos) tiene muchas aplicaciones en el diseño de circuitos integrados ^{[ 43 ]} y la computación paralela . ^{[ 44 ] [ 45 ] [ 46 ]} Los algoritmos de partición de hipergrafos eficientes y escalables también son importantes para el procesamiento de hipergrafos a gran escala en tareas de aprendizaje automático. ^{[ 6 ]}

Una posible generalización de un hipergrafo es permitir que las aristas apunten a otras aristas. ^{[ 47 ]} Hay dos variaciones de esta generalización. En una, las aristas consisten no solo 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 simplemente un nodo interno de un árbol o grafo dirigido acíclico , y los vértices son los nodos hoja. Un hipergrafo es entonces simplemente una colección de árboles con nodos comunes y compartidos (es decir, un nodo interno o una hoja dados pueden aparecer en varios árboles diferentes). ^{[ 48 ] [ 49 ]} A la inversa, toda 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. ^{[ 50 ]} 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. ^{[ 51 ]}

Para tal hipergrafo, la pertenencia a un conjunto proporciona un ordenamiento, pero este ordenamiento no es ni un orden parcial ni un preorden , ya que no es transitivo. ^{[ 52 ]} El grafo correspondiente al grafo de Levi de esta generalización es un grafo dirigido acíclico . ^{[ 53 ]} Consideremos, por ejemplo, el hipergrafo generalizado cuyo conjunto de vértices es${\displaystyle V=\{a,b\}}$y cuyos bordes son${\displaystyle e_{1}=\{a,b\}}$y${\displaystyle e_{2}=\{a,e_{1}\}}$. Entonces, aunque${\displaystyle b\in e_{1}}$y${\displaystyle e_{1}\in e_{2}}$, no es cierto que${\displaystyle b\in e_{2}}$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 . ^{[ 54 ]}

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. ^{[ 47 ] [ 48 ]} Esto permite grafos con bucles de aristas, que no necesitan contener vértices en absoluto. Por ejemplo, considérese el hipergrafo generalizado que consta de dos aristas.${\displaystyle e_{1}}$y${\displaystyle e_{2}}$y cero vértices, de modo que${\displaystyle e_{1}=\{e_{2}\}}$y${\displaystyle e_{2}=\{e_{1}\}}$Como este bucle es infinitamente recursivo, los conjuntos que son las aristas violan el axioma de fundación . ^{[ 48 ]} En particular, no hay cierre transitivo de pertenencia a conjuntos para tales hipergrafos. Aunque tales estructuras puedan parecer extrañas al principio, se pueden comprender fácilmente al observar que la generalización equivalente de su grafo de Levi ya no es bipartita , sino que es simplemente un grafo dirigido general . ^{[ 55 ]}

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

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

• Berge, Claude (1984). Hipergrafos: Combinatoria de conjuntos finitos . Elsevier. ISBN 978-0-08-088023-5.
• Berge, C.; Ray-Chaudhuri, D. (2006). Seminario sobre hipergrafos: Universidad Estatal de Ohio, 1972. Notas de clase en matemáticas. 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). Coloring Mixed Hypergraphs: Theory, Algorithms and Applications: Theory, Algorithms, and Applications . Fields Institute Monographs. Vol.  17. American Mathematical Society. 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á bajo la licencia Creative Commons Attribution/Share-Alike License .

• PAOHVis : sistema PAOHVis de código abierto para la visualización de hipergrafos dinámicos.