Hipergrafo

Os hipergrafos são objetos matemáticos que generalizam o gráfico conceitual . Eles foram nomeados assim por Claude Berge na década de 1960.

Os hipergrafos generalizam a noção de um grafo não direcionado no sentido de que as arestas não conectam mais um ou dois vértices, mas qualquer número de vértices (entre um e o número de vértices do hipergrafo).

Alguns teoremas da teoria dos grafos são naturalmente generalizados para hipergrafos, por exemplo o teorema de Ramsey .

Os hipergrafos são tratados em todas as áreas onde a teoria dos grafos é usada: resolução de problemas de satisfação de restrições , processamento de imagem, otimização de arquiteturas de rede, modelagem , etc.

Definições

Hipergrafo

Um hipergrafo é um par que é definido como não vazio (geralmente finito) e é uma família de partes não vazias . $H$ $(V, E)$ ${\ displaystyle V = \ {v_ {1}, v_ {2}, ..., v_ {n} \}}$ ${\ displaystyle E = E_ {1}, E_ {2}, ..., E_ {m}}$ $V$

Como gráficos, dizemos que:

Os elementos de são os vértices de . $V$ $H$
O número de vértices é a ordem do hipergrafo. $não$
Os elementos de são as arestas de . $E$ $H$

Os hipergrafos correspondem precisamente a matrizes com coeficientes 0 ou 1 (cada coluna tem pelo menos um 1). Na verdade, qualquer hipergrafo corresponde inequivocamente à 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 {caso contrário}} \ end {cases}}}

Hipergrafo uniforme

Entre as "novas" propriedades dos hipergrafos com respeito aos gráficos estão dois conceitos associados.

Chamamos a classificação de um hipergrafo o número máximo de vértices de uma aresta: ${\ displaystyle \ operatorname {rang} (H) = \ max _ {i \ in \ {1, \ ldots, m \}} | E_ {i} |}$ A classificação de um hipergrafo é aumentada por sua ordem. Se , então é um gráfico . ${\ displaystyle \ mathrm {rank} (H) = 2}$ $H$
Chamamos de anti-classificação de um hipergrafo o número mínimo de vértices de uma aresta: ${\ displaystyle \ operatorname {anti-rank} (H) = \ min _ {i \ in \ {1, \ ldots, m \}} | E_ {i} |}$

Por definição de um hipergrafo, as arestas são partes não vazias do conjunto de vértices do hipergrafo. O anti-rank de um hipergrafo é, portanto, diferente de zero.

Diz-se que um hipergrafo é uniforme quando sua posição e sua antiparas são iguais.

Também falamos de hipergrafo uniforme r para denotar um hipergrafo uniforme de classificação . $r$

Exemplo: o hipergrafo do avião de Fano

O hipergrafo do plano de Fano possui sete vértices denominados pontos {0,1,2,3,4,5,6} e sete arestas denominadas retas (013, 045, 026, 124, 346, 325, 516). A ordem (número de vértices) é 7.

A linha e a antirinha são iguais a 3 (número de vértices de uma aresta). Portanto, o hipergrafo do plano de Fano é um hipergrafo de 3 uniformes.

Hipergrafo parcial e subhipergrafo

Como gráficos, dizemos que:

Um hipergrafo parcial de um hipergrafo é tal que: ${\ displaystyle H_ {p} = (V, E_ {p})}$ ${\ displaystyle H = (V, E)}$ ${\ displaystyle E_ {p} \ subconjunto E}$ .
Um subhipergrafo de um hipergrafo é tal que: H′=(V′,E′){\ displaystyle H '= (V', E ')} $H '= (V', E ')$ H=(V,E){\ displaystyle H = (V, E)} ${\ displaystyle H = (V, E)}$
- ${\ displaystyle V '\ subseteq V}$ e
- ${\ displaystyle \ forall E_ {i} \ in E ', \ quad E_ {i} \ subseteq V' \ land E_ {i} \ in E}$ .

Essas noções generalizam as noções de gráfico parcial e subgrafo para a teoria dos hipergrafos.

Hipergrafo simples

Como os gráficos (não orientados), dizemos que um hipergrafo é simples se não tiver arestas múltiplas (ver artigo gráfico simples ).

Chamamos de família de Sperner (ou desordem em inglês) um hipergrafo simples cuja nenhuma borda está contida em outra.

Hipergrafo duplo

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

Então, o hipergrafo definido por é chamado de hipergrafo dual de . Corresponde à transposição da matriz. A noção não coincide com a de um gráfico dual , mesmo no caso em que o hipergrafo acaba por ser um gráfico. ${\ displaystyle H ^ {*} = (E, V ^ {*})}$ $H$

Exemplos:

${\ displaystyle (\ {1,2 \}, \ {1,3 \}, \ {2,3 \})}$ é autodual e autotransversal .
${\ displaystyle (\ {1,2,3 \}, \ {1,4,5 \}, \ {1,6,7 \}, \ {2,4,6 \}, \ {2,5, 7 \}, \ {3,4,7 \}, \ {3,5,6 \})}$ é um plano projetivo , autotransversal, uniforme, regular e autodual.

Hipergrafo, recuperação, partição

O conjunto de arestas de um hipergrafo não é necessariamente uma sobreposição , pois um vértice pode ser de grau zero, ou seja, não estar conectado por nenhuma aresta; neste caso, a união das arestas não cobre todos os vértices. Por exemplo, no hipergrafo tal que e , o vértice é de grau zero; não aparecendo em nenhum dos subconjuntos de , impede de ser uma sobreposição. O conjunto de arestas de um hipergrafo é apenas uma sobreposição se cada vértice tiver pelo menos grau 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$ $E$ $E$

Consequentemente, há uma partição se o conjunto de arestas for uma sobreposição e nenhum vértice estiver conectado por duas arestas, ou seja, se qualquer vértice for exatamente de grau 1.

Veja também

Notas e referências

Claude Berge , Graphs et Hypergraphes , Dunod, Collection Monograph Universitaires de Mathématiques n ° 37, janeiro de 1970.

Claude Berge , Hypergraphs. Combinatorics of finite sets , Gauthier-Villars, 1987 ( ISBN 2-04-016906-7 ) .