Hipergrafo

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

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

O conjunto ${\displaystyle V}$ é chamado de conjunto de vértices e o conjunto ${\displaystyle 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^[2] seria uma espécie de hipergrafo.

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

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

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

Referências