Hypergraph

Los hipergráficos son objetos matemáticos que generalizan el concepto gráfico . Fueron nombrados así por Claude Berge en la década de 1960.

Los hipergráficos generalizan la noción de grafo no dirigido en el sentido de que los bordes ya no conectan uno o dos vértices, sino cualquier número de vértices (incluidos entre uno y el número de vértices del hipergráfico).

Algunos teoremas de la teoría de grafos se generalizan naturalmente a hipergráficos, por ejemplo, el teorema de Ramsey .

Los hipergráficos se manejan en todas las áreas donde se utiliza la teoría de grafos: resolución de problemas de satisfacción de restricciones , procesamiento de imágenes, optimización de arquitecturas de red, modelado , etc.

Definiciones

Hypergraph

Un hipergrafo es un par que se establece como no vacío (generalmente finito) y es una familia de partes no vacías . $H$ $(V, E)$ ${\ Displaystyle V = \ {v_ {1}, v_ {2}, ..., v_ {n} \}}$ ${\ Displaystyle E = E_ {1}, E_ {2}, ..., E_ {m}}$ $V$

Como gráficos, decimos que:

Los elementos de son los vértices de . $V$ $H$
El número de vértices es el orden del hipergráfico. $no$
Los elementos de son los bordes de . $mi$ $H$

Los hipergráficos corresponden precisamente a matrices con coeficientes 0 o 1 (cada columna tiene al menos un 1). De hecho, cualquier hipergráfico corresponde inequívocamente a la matriz como: $H$ ${\ Displaystyle {\ mathcal {A}} _ {n, m} \,}$

{\ Displaystyle \ forall a_ {i, j} \ in {\ mathcal {A}}, \ quad a_ {i, j} = {\ begin {cases} 1 & {\ text {si}} ~ v_ {i} \ in E_ {j} \\ 0 & {\ text {de lo contrario}} \ end {cases}}}

Hipergrafo uniforme

Entre las "nuevas" propiedades de los hipergráficos con respecto a los gráficos se encuentran dos conceptos asociados.

Llamamos al rango de un hipergráfico al número máximo de vértices de una arista: ${\ Displaystyle \ operatorname {sonó} (H) = \ max _ {i \ in \ {1, \ ldots, m \}} | E_ {i} |}$ El rango de un hipergráfico aumenta según su orden. Si , entonces es un gráfico . ${\ Displaystyle \ mathrm {rango} (H) = 2}$ $H$
Llamamos anti-rango de un hipergráfico al número mínimo de vértices de una arista: ${\ Displaystyle \ operatorname {anti-sonó} (H) = \ min _ {i \ in \ {1, \ ldots, m \}} | E_ {i} |}$

Por definición de un hipergráfico, los bordes son partes no vacías del conjunto de vértices del hipergráfico. Por tanto, el anti-rango de un hipergráfico es distinto de cero.

Se dice que un hipergrafo es uniforme cuando su rango y su anti-rango son iguales.

También hablamos de hipergrafo r-uniforme para denotar un hipergrafo uniforme de rango . $r$

Ejemplo: el hipergrafo del plano de Fano

El hipergrama del plano de Fano tiene siete vértices llamados puntos {0,1,2,3,4,5,6} y siete aristas llamadas líneas rectas (013, 045, 026, 124, 346, 325, 516). El orden (número de vértices) es 7.

La fila y la anti-fila son iguales a 3 (número de vértices de una arista). Por lo tanto, el hipergrafo del plano de Fano es un hipergrafo de 3 uniformes.

Hipergrafo y sub-hipergrafo parcial

Como gráficos, decimos que:

Un hipergrafo parcial de un hipergrafo es tal que: ${\ Displaystyle H_ {p} = (V, E_ {p})}$ ${\ Displaystyle H = (V, E)}$ ${\ Displaystyle E_ {p} \ subconjunto E}$ .
Un subhipergrafo de un hipergrafo es tal que: H′=(V′,mi′){\ Displaystyle H '= (V', E ')} $H '= (V', E ')$ H=(V,mi){\ Displaystyle H = (V, E)} ${\ Displaystyle H = (V, E)}$
- ${\ Displaystyle V '\ subseteq V}$ y
- ${\ Displaystyle \ forall E_ {i} \ in E ', \ quad E_ {i} \ subseteq V' \ land E_ {i} \ in E}$ .

Estas nociones generalizan las nociones de gráfico parcial y subgráfico a la teoría de hipergráficos.

Hipergrafo simple

Al igual que los gráficos (no orientados), decimos que un hipergráfico es simple si no tiene múltiples aristas (ver artículo gráfico simple ).

Llamamos a la familia de Sperner (o desorden en inglés) un hipergráfico simple cuyo borde no está contenido en otro.

Hipergrafo dual

Ya sea tal que . ${\ Displaystyle V ^ {*} = \ {V_ {j} \ mid j = 1,2, \ ldots, | V | \}}$ ${\ Displaystyle V_ {j} = \ {E_ {i} \ mid (E_ {i} \ in E) \ wedge (v_ {j} \ in E_ {i}) \}}$

Entonces, el hipergráfico definido por se denomina hipergráfico dual de . Corresponde a la transposición de la matriz. La noción no coincide con la de gráfico dual , incluso en el caso de que el hipergráfico resulte ser un gráfico. ${\ Displaystyle H ^ {*} = (E, V ^ {*})}$ $H$

Ejemplos:

${\ Displaystyle (\ {1,2 \}, \ {1,3 \}, \ {2,3 \})}$ es autodual y autotransversal .
${\ Displaystyle (\ {1,2,3 \}, \ {1,4,5 \}, \ {1,6,7 \}, \ {2,4,6 \}, \ {2,5, 7 \}, \ {3,4,7 \}, \ {3,5,6 \})}$ es un plano proyectivo , autotransversal, uniforme, regular y autodual.

Hypergraph, recuperación, partición

El conjunto de aristas de un hipergrafo no es necesariamente una superposición , porque un vértice puede ser de grado cero, es decir, no estar conectado por ninguna arista; en este caso, la unión de las aristas no cubre todos los vértices. Por ejemplo, en el hipergrafo tal que y , el vértice es de grado cero; no aparece en ninguno de los subconjuntos de , evita que sea una superposición. El conjunto de aristas de un hipergrafo es solo una superposición si cada vértice es al menos de grado 1. ${\ Displaystyle V = \ {v_ {1}, v_ {2}, v_ {3}, v_ {4}, v_ {5}, v_ {6}, v_ {7} \}}$ ${\ Displaystyle E = \ {e_ {1}, e_ {2}, e_ {3}, e_ {4} \} = \ {\ {v_ {1}, v_ {2}, v_ {3} \}, \ {v_ {2}, v_ {3} \}, \ {v_ {3}, v_ {5}, v_ {6} \}, \ {v_ {4} \} \}}$ $v_7$ $e_i$ $mi$ $mi$

En consecuencia, hay una partición si el conjunto de aristas se superpone y ningún vértice está conectado por dos aristas, es decir, si algún vértice es exactamente de grado 1.

Ver también

Notas y referencias

Claude Berge , Graphs et Hypergraphes , Dunod, Colección Monografía Universitaires de Mathématiques n ° 37, enero de 1970.

Claude Berge , Hypergraphs. Combinatoria de conjuntos finitos , Gauthier-Villars, 1987 ( ISBN 2-04-016906-7 ) .