Hipergrafo

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En matemáticas, una hipergrafía es una generalización de una gráfica en la 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, una hipergrafía no dirigida $H$ es un par $H = (X, E)$ donde $X$ hay un conjunto de elementos llamados nodos o vértices, y $mi$ es (en una hipergrafía no dirigida) un conjunto de subconjuntos no vacíos $X$ llamados hiperaristas o aristas. Por lo tanto, $mi$ es un subconjunto de $mathcal{P}(X) setminus{emptyset}$ , donde ${ matemáticas {P}} (X)$ es el conjunto potencia de $X$ . El tamaño del conjunto de vértices se denomina orden de la hipergrafía, y el tamaño del conjunto de aristas es el tamaño de la hipergrafía.

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

Mientras que los bordes del gráfico conectan solo 2 nodos, los hiperbordes conectan un número arbitrario de nodos. Sin embargo, a menudo es deseable estudiar hipergráficos donde todos los hiperbordes tienen la misma cardinalidad; una hipergrafía k-uniforme es una hipergrafía tal que todos sus hiperbordes tienen tamaño k. (En otras palabras, uno de esos hipergráficos es una colección de conjuntos, cada uno de esos conjuntos es un hiperborde que conecta k nodos). Entonces, un hipergráfico de 2 uniformes es un gráfico, un hipergráfico de 3 uniformes es una colección de triples desordenados, y así sucesivamente. Una hipergrafía no dirigida también se denomina sistema de conjuntos o familia de conjuntos extraídos del conjunto universal.

Los hipergráficos pueden verse como estructuras de incidencia. En particular, hay un "gráfico de incidencia" bipartito o "gráfico de Levi" que corresponde a cada hipergráfico y, a la inversa, la mayoría, pero no todos, los gráficos bipartitos pueden considerarse gráficos de incidencia de hipergráficos.

Los hipergrafos tienen muchos otros nombres. En geometría computacional, un hipergráfico no dirigido a veces se puede llamar un espacio de rango y luego los hiperbordes se llaman rangos. En la teoría de juegos cooperativos, las hipergrafías se denominan juegos simples (juegos de votación); esta noción se aplica para resolver problemas en la teoría de la elección social. En alguna literatura, los bordes se denominan hipervínculos o conectores.

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

Aplicaciones

Los hipergráficos no dirigidos son útiles para modelar cosas como problemas de satisfacibilidad, bases de datos, aprendizaje automático y problemas del árbol de Steiner. Se han utilizado ampliamente en tareas de aprendizaje automático como el modelo de datos y la regularización del clasificador (matemáticas). Las aplicaciones incluyen sistema de recomendación (comunidades como hiperbordes), recuperación de imágenes (correlaciones como hiperbordes) y bioinformática (interacciones bioquímicas como hiperbordes). Las técnicas representativas de aprendizaje de hipergrafías incluyen el agrupamiento espectral de hipergrafías que amplía la teoría de grafos espectrales con hipergrafías laplacianas y el aprendizaje semisupervisado de hipergrafías que introduce un costo estructural adicional de hipergrafías para restringir los resultados del aprendizaje.Para hipergrafías a gran escala, también está disponible un marco distribuido creado con Apache Spark.

Los hipergráficos dirigidos se pueden usar para modelar cosas, incluidas aplicaciones de telefonía, detección de lavado de dinero, investigación de operaciones y planificación del transporte. También se pueden usar para modelar la satisfacción de Horn.

Generalizaciones de conceptos a partir de grafos

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

Emparejamiento en hipergrafías;
Cobertura de vértices en hipergrafías (también conocido como: transversal);
Gráfico lineal de una hipergrafía;
Gramática hipergráfica: creada al aumentar una clase de hipergrafías con un conjunto de reglas de reemplazo;
el teorema de Ramsey;
teorema de Erdős-Ko-Rado;
Teorema de Kruskal-Katona sobre hipergrafías uniformes;
Teoremas de tipo Hall para hipergrafías.

En hipergrafías dirigidas: clausura transitiva y problemas del camino más corto.

Dibujo hipergráfico

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

En una posible representación visual de las hipergrafías, similar al estilo estándar de dibujo de gráficos en el que se utilizan curvas en el plano para representar los bordes del gráfico, los vértices de una hipergrafía se representan como puntos, discos o cajas, y sus hiperbordes se representan como árboles que tienen los vértices como sus hojas. 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 simples curvas cerradas que encierran conjuntos de puntos.

En otro estilo de visualización de hipergrafía, el modelo de subdivisión del dibujo de hipergrafía, el plano se subdivide en regiones, cada una de las cuales representa un único vértice de la hipergrafía. Los hiperbordes de la hipergrafía están representados por subconjuntos contiguos de estas regiones, que pueden indicarse coloreando, dibujando contornos a su alrededor, o ambos. Un diagrama de Venn de orden n, por ejemplo, puede verse como un dibujo de subdivisión de una hipergrafía 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 de tiempo polinómico de grafos planos, es NP-completo para determinar si una hipergrafía tiene un dibujo de subdivisión plana,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.

Una representación alternativa de la hipergrafía llamada PAOH se muestra en la figura en la parte superior de este artículo. Los bordes 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 los bordes. Ha sido diseñado para hipergrafías dinámicas, pero también se puede utilizar para hipergrafías simples.

Coloración hipergráfica

La coloración clásica de hipergrafías consiste en asignar uno de los colores del conjunto ${displaystyle{1,2,3,...,lambda}}$ a cada vértice de una hipergrafía 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 de al menos 2. En este sentido, es una generalización directa del coloreado de grafos. El número mínimo de colores distintos utilizados sobre todos los colorantes se denomina número cromático de una hipergrafía.

Los hipergráficos para los que existe una coloración que utiliza hasta k colores se denominan k-coloreables. Las hipergrafías de 2 colores son exactamente las bipartitas.

Hay muchas generalizaciones de la coloración hipergráfica clásica. Uno de ellos es el llamado coloreado hipergráfico mixto, cuando se permiten bordes monocromáticos. Algunas hipergrafías mixtas no se pueden colorear para cualquier número de colores. Se desconoce un criterio general para la falta de coloración. Cuando una hipergrafía mixta es coloreable, el número mínimo y máximo de colores utilizados se denominan números cromáticos inferior y superior, respectivamente.

Propiedades de las hipergrafías

Una hipergrafía 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.
Simple: no tiene bucles ni bordes repetidos.
-regular - cada vértice tiene un grado $d$ , es decir, contenido exactamente en $d$ hiperaristas.
2-colorable: sus vértices se pueden dividir en dos clases U y V de tal manera que cada hiperarista con cardinalidad de 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 bipartitas y equilibradas.
-uniforme: cada hiperarista contiene $k$ vértices precisos.
-partido: los vértices se dividen en partes y cada hiperarista contiene precisamente un vértice de cada tipo.
- Cada hipergrafía -partita (para $kgeq 2$ ) es tanto -uniforme como bipartita (y 2-coloreable).
Cerrado hacia abajo: cada subconjunto de los bordes de un hipergráfico no dirigido también es un hiperborde. Un hipergráfico cerrado hacia abajo generalmente se llama un complejo simplicial abstracto.
- Un complejo simplicial abstracto con la propiedad de aumento se llama matroide.

Hipergrafías relacionadas

Debido a que los enlaces hipergráficos pueden tener cualquier cardinalidad, existen varias nociones del concepto de subgráfico, llamadas subhipergráficos, hipergráficos parciales e hipergráficos de sección.

Sea $H=(X,E)$ la hipergrafía formada por vértices ${displaystyle X=lbrace x_{i}mid iin I_{v}rbrace,}$

y teniendo borde establecido ${displaystyle E=lbrace e_{i}mid iin I_{e}land e_{i}subseteq Xland e_{i}neq emptyset rbrace,}$

donde $yo_v$ y $Es decir$ son los conjuntos índice de los vértices y aristas respectivamente.

Un subhipergrafo es un hipergrafo al que se le han quitado algunos vertices. Formalmente, el subhipergrafo $DECIR AH$ inducido por ${displaystyle Asubseteq X}$ se define como ${displaystyle H_{A}=left(A,lbrace ecap Amid ein Eland ecap Aneq emptyset rbrace right).}$

Un término alternativo es la restricción de H a A.

Una extensión de un subhipergráfico es un hipergráfico en el que cada hiperborde $H$ que está parcialmente contenido en el subhipergráfico $DECIR AH$ está completamente contenido en la extensión ${displaystyle Ex(H_{A})}$ . Formalmente ${displaystyle Ex(H_{A})=(Ataza A',E')}$ con ${displaystyle A'=bigcup_{ein E} ysetminus A}$ y ${displaystyle E'=lbrace ein Emid esubseteq (Acup A')rbrace }$ .

La hipergrafía parcial es una hipergrafía con algunos bordes eliminados. Dado un subconjunto $J subconjunto I_e$ del conjunto de índices de borde, la hipergrafía parcial generada por $j$ es la hipergrafía ${displaystyle left(X,lbrace e_{i}mid iin Jrbrace right).}$

Dado un subconjunto $Asubconjunto X$ , la hipergrafía de sección es la hipergrafía parcial ${displaystyle Htimes A=left(A,lbrace e_{i}mid iin I_{e}land e_{i}subseteq Arbrace right).}$

El dual $H^{*}$ de $H$ es una hipergrafía cuyos vértices y aristas están intercambiados, de modo que los vértices están dados por $lbrace e_i rbrace$ y cuyas aristas están dadas por $lbrace X_m rbrace$ donde ${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 una hipergrafía es una involución, es decir, $izquierda(H^*derecha)^* = 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 H desconectado, G es un grafo anfitrión si existe una biyección entre las componentes conexas de G y de H, tal que cada componente conexa G' de G es una anfitriona de la H' correspondiente.

El gráfico de 2 secciones (o gráfico clique, que representa el gráfico, el gráfico primario, el gráfico de Gaifman) de un hipergráfico es el gráfico con los mismos vértices del hipergráfico y los bordes entre todos los pares de vértices contenidos en el mismo hiperrango.

Matriz de incidencia

Sea $V = {v_1, v_2, ~ldots, ~ v_n}$ y $mi = {e_1, e_2, ~ ldots ~ e_m}$ . Toda hipergrafía tiene una $nveces m$ matriz de incidencia.

Para una hipergrafía no dirigida, ${displaystyle I=(b_{ij})}$ donde ${displaystyle b_{ij}=left{{begin{matriz}1&mathrm {si} ~v_{i}in e_{j}\0&mathrm {de lo contrario}.end{matriz}} Correcto.}$

La transposición ${displaystyle yo^{t}}$ de la matriz de incidencia define una hipergrafía $H^* = (V^*, E^*)$ denominada dual de $H$ , donde $V^{*}$ es un conjunto de m elementos y $mi^{*}$ es un conjunto de n elementos de subconjuntos de $V^{*}$ . Para $v^*_j en V^*$ y $e^*_i in E^*, ~ v^*_j in e^*_i$ si y sólo si $b_{{ij}}=1$ .

Para una hipergrafía dirigida, las cabezas y las colas de cada hiperarista $e_{j}$ se denotan por ${displaystyle H(e_{j})}$ y ${displaystyle T(e_{j})}$ respectivamente. dónde ${displaystyle I=(b_{ij})}$ ${displaystyle b_{ij}=left{{begin{matriz}-1&mathrm {si} ~v_{i}in T(e_{j})\1&mathrm {si} ~v_{ i}in H(e_{j})\0&mathrm {de lo contrario}.end{matriz}}right.}$

Gráfico de incidencia

Un hipergrafo H puede ser representado por un grafo bipartito BG como sigue: los conjuntos X y E son las partes de BG, y (x ₁, e ₁) estan conectados con una arista si y solo si el vertice x ₁ esta 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 una hipergrafía de la manera descrita anteriormente. Este gráfico bipartito también se llama gráfico de incidencia.

Matriz de adyacencia

Se puede dibujar un paralelo para la matriz de adyacencia de un hipergráfico 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 $A=(a_{ij})$ para un hipergrafo en general donde los hiperbordes ${displaystyle e_{kleq m}}$ tienen pesos reales ${displaystyle w_{e_{k}}en mathbb {R} }$ con

{displaystyle a_{ij}=left{{begin{matriz}w_{e_{k}}&mathrm {si} ~(v_{i},v_{j})en E\0& mathrm {de lo contrario}.end{matriz}}right.}

Ciclos

En contraste con los grafos ordinarios no dirigidos para los que existe una sola noción natural de ciclos y grafos acíclicos, existen múltiples definiciones naturales no equivalentes de aciclicidad para hipergrafos que colapsan en aciclicidad de grafos ordinarios para el caso especial de grafos ordinarios.

Claude Berge dio una primera definición de aciclicidad para hipergrafías: una hipergrafía es acíclica de Berge si su gráfico de incidencia (el gráfico bipartito definido anteriormente) es acíclico. Esta definición es muy restrictiva: por ejemplo, si una hipergrafía tiene algún par $v neq v'$ de vértices y algún par $f neq f'$ de hiperaristas tales que $v, v' in f$ y $v, v' in f'$ , entonces es cíclica de Berge. Obviamente, la ciclicidad de Berge se puede probar en tiempo lineal mediante una exploración del gráfico de incidencia.

Podemos definir una noción más débil de aciclicidad hipergráfica, más tarde denominada aciclicidad α. Esta noción de aciclicidad es equivalente a que la hipergrafía sea conforme (cada camarilla del gráfico primario está cubierta por algún hiperborde) y su gráfico primario sea cordal; también es equivalente a la reducibilidad al gráfico vacío a través del algoritmo GYO (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 hipergrafía subyacente es α-acíclica. Además, la α-aciclicidad también está relacionada con la expresividad del fragmento protegido de la lógica de primer orden.

Podemos probar en tiempo lineal si una hipergrafía es α-acíclica.

Tenga en cuenta que la α-aciclicidad tiene la propiedad contraria a la intuición de que agregar hiperaristas a un hipergráfico α-cíclico puede convertirlo en α-acíclico (por ejemplo, agregar un hiperarista que contenga todos los vértices del hipergráfico siempre lo convertirá en α-acíclico). Motivado en parte por esta deficiencia percibida, Ronald Fagin definió las nociones más fuertes de β-aciclicidad y γ-aciclicidad. Podemos establecer la β-aciclicidad como el requisito de que todas las subhipergrafías de la hipergrafía sean α-acíclicas, lo que equivale a una definición anterior de Graham. 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 se pueden probar en tiempo polinomial.

Esas cuatro nociones de aciclicidad son comparables: Berge-aciclicidad 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.

Isomorfismo, simetría e igualdad

Un homomorfismo de hipergrafía es un mapa del conjunto de vértices de una hipergrafía a otra tal que cada borde se asigna a otro borde.

Una hipergrafía $H=(X,E)$ es isomorfa a una hipergrafía $G=(Y,F)$ , escrita como $H simeq G$ si existiera una biyección $phi:X a Y$

y una permutación $Pi$ de $yo$ tal que $phi(e_i) = f_{pi(i)}$

La biyección $fi$ entonces se llama el isomorfismo de los gráficos. Tenga en cuenta que $H simeq G$ si y solo si $H^* simeq G^*$ .

Cuando los bordes de una hipergrafía se etiquetan explícitamente, se tiene la noción adicional de isomorfismo fuerte. Se dice que $H$ es fuertemente isomorfo a $GRAMO$ si la permutación es la identidad. Uno entonces escribe $H cong G$ . Tenga en cuenta que todos los gráficos fuertemente isomorfos son isomorfos, pero no al revés.

Cuando los vértices de una hipergrafía se etiquetan explícitamente, se tienen las nociones de equivalencia y también de igualdad. Se dice que $H$ es equivalente a $GRAMO$ , y se escribe $Hequiv G$ si el isomorfismo $fi$ tiene $phi(x_n) = y_n$

y $phi(e_i) = f_{pi(i)}$

Tenga en cuenta que $Hequiv G$ si y solo si $H^* cong G^*$

Si, además, la permutación $Pi$ es la identidad, se dice que $H$ es igual a $GRAMO$ , y se escribe $H=G$ . Tenga en cuenta que, con esta definición de igualdad, los gráficos son autodual: $izquierda(H^*derecha) ^* = H$

Un automorfismo hipergráfico es un isomorfismo de un conjunto de vértices en sí mismo, es decir, un reetiquetado de vértices. El conjunto de automorfismos de una hipergrafía H (= (X, E)) es un grupo en composición, llamado grupo de automorfismos de la hipergrafía y escrito Aut(H).

Ejemplos

Considere la hipergrafía $H$ con bordes $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 $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 $H$ y $GRAMO$ son isomorfos (con $phi(a)=alfa$ , etc.), pero no son fuertemente isomorfos. Entonces, por ejemplo, en $H$ , el vértice $a$ se encuentra con los bordes 1, 4 y 6, de modo que, $e_1 cap e_4 cap e_6 = lbrace arbrace$

En el grafo $GRAMO$ no existe ningún vértice que coincida con las aristas 1, 4 y 6: $f_1 cap f_4 cap f_6 = varnada$

En este ejemplo, $H$ y $GRAMO$ son equivalentes, $Hequiv G$ y los duales son fuertemente isomorfos: $H^*cong G^*$ .

Simetría

losEl rango $Rh)$ de una hipergrafía $H$ es la cardinalidad máxima de cualquiera de los bordes de la hipergrafía. Si todas las aristas tienen la misma cardinalidadk, se dice que la hipergrafía esuniformeok-uniforme, o se denominak-hipergrafía. Una gráfica es simplemente una hipergrafía de 2 uniformes.

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

El dual de una hipergrafía uniforme es regular y viceversa.

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

Se dice que un hipergráfico es transitivo de vértice (o simétrico de vértice) si todos sus vértices son simétricos. De manera similar, una hipergrafía es transitiva por aristas si todas las aristas son simétricas. Si una hipergrafía es simétrica tanto en el borde como en el vértice, entonces la hipergrafía es simplemente transitiva.

Debido a la dualidad hipergráfica, el estudio de la transitividad de los bordes es idéntico al estudio de la transitividad de los vértices.

Particiones

Un teorema de partición debido a E. Dauber establece que, para una hipergrafía transitiva de borde $H=(X,E)$ , existe una partición $(X_1, X_2,cdots,X_K)$

del conjunto de vértices $X$ tal que el subhipergrafo $H_{X_k}$ generado por $X_{k}$ es transitivo para cada $1la kla K$ , y tal que $sum_{k=1}^K rleft(H_{X_k} right) = r(H)$

donde $Rh)$ es el rango de H.

Como corolario, una hipergrafía transitiva de borde que no es transitiva de vértice 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 y la computación paralela. 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.

Otras generalizaciones

Una posible generalización de una hipergrafía es permitir que los bordes apunten a otros bordes. Hay dos variaciones de esta generalización. En uno, los bordes 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í 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. Entonces, una hipergrafía es solo una colección de árboles con nodos comunes compartidos (es decir, un nodo interno u hoja determinado puede aparecer en varios árboles diferentes). A la inversa, toda colección de árboles puede entenderse como esta hipergrafía generalizada. 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 las hipergrafías también aparecen de forma natural. Entonces, por ejemplo, esta generalización surge naturalmente como un modelo de álgebra de términos; las aristas corresponden a términos y los vértices corresponden a constantes o variables.

Para una hipergrafía de este tipo, la pertenencia a un conjunto proporciona un orden, pero el orden no es ni un orden parcial ni un preorden, ya que no es transitivo. El gráfico correspondiente al gráfico de Levi de esta generalización es un gráfico acíclico dirigido. Considere, por ejemplo, la hipergrafía generalizada cuyo conjunto de vértices es $V= {a,b}$ y cuyas aristas son $e_1={a,b}$ y $e_2 = {a, e_1 }$ . Entonces, aunque $ben e_1$ y $e_1 en e_2$ , no es cierto que $ben e_2$ . Sin embargo, el cierre transitivo de la pertenencia al conjunto para tales hipergrafías induce un orden parcial y "aplana" la hipergrafía en un conjunto parcialmente ordenado.

Alternativamente, se puede permitir que los bordes apunten a otros bordes, independientemente del requisito de que los bordes se ordenen como gráficos acíclicos dirigidos. Esto permite gráficos con bucles de borde, que no necesitan contener vértices en absoluto. Por ejemplo, considere la hipergrafía generalizada que consta de dos aristas $e_{1}$ y $e_{2}$ , y cero vértices, de modo que $e_1 = {e_2 }$ y $e_2 = {e_1 }$ . Como este bucle es infinitamente recursivo, los conjuntos que son las aristas violan el axioma de fundamento. En particular, no hay un cierre transitivo de pertenencia a un conjunto para tales hipergrafías. Aunque tales estructuras pueden parecer extrañas al principio, se pueden entender fácilmente al notar que la generalización equivalente de su gráfico de Levi ya no es bipartita, sino que es solo un gráfico general dirigido.

La matriz de incidencia generalizada para tales hipergrafías 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 $left[ begin{matrix} 0 & 1 \ 1 & 0 end{matrix} right].$

Contenido relacionado

Más resultados...