Hipergrafo

Em teoria dos grafos, um hipergrafo é uma generalização de um grafo, com suas arestas ligando quaisquer quantidades positivas de vértices.

Definição

Definimos um hipergrafo como um par ordenado $(V,A)$, onde $A\subseteq (\wp (X)\setminus \{\emptyset \})$ e $\wp (X)$ é o conjunto das partes de V.

O conjunto $V$ é chamado de conjunto de vértices e o conjunto $A$ é o conjunto de hiperarestas. Ou seja, um hipergrafo é um conjunto de vértices associado com um conjunto de hiperarestas, sendo que cada hiperaresta é um subconjunto não vazio do conjunto de vértices. Note que isso não impede que o conjunto de hiperarestas seja vazio, apenas impede que se tenha uma hiperaresta vazia, visto que não faria sentido chamarmos algo de "aresta" sendo que não 'conectaria' vértice algum.

Uma curiosidade é que se o conjunto de hiperarestas pudesse possuir o conjunto vazio, todo espaço mensurável seria uma espécie de hipergrafo.

Coloração de hipergrafos

Definimos a coloração de hipergrafos da seguinte forma: seja ${\mathcal {H}}=(V,{\mathcal {E}})$ um hipergrafo, com $\mid V\mid =n$. Dizemos que ${\mathcal {C}}=\{c_{1},c_{2},\ldots ,c_{n}\}$ é uma coloração própria de ${\mathcal {H}}$ se e somente se, para toda aresta $e\in {\mathcal {E}}$, exista pelo menos um par de vértices $v_{1},v_{2}\in e$ tal que $c_{1}\neq c_{2}$.

Hipergrafos-clique

Um hipergrafo-clique (denotado ${\mathcal {H}}(G)$) é um hipergrafo gerado a partir de um grafo G da seguinte forma:

• $V({\mathcal {H}}):=V(G)$
• ${\mathcal {E}}({\mathcal {H}}):=\{e\in S(V({\mathcal {H}}))\mid e$ é uma clique maximal de $G\}$