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 (\mathrm{\wp }(X)\setminus \{\mathrm{\varnothing }\})$ e $\mathrm{\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 $\mathscr{H}=(V,ℰ)$ um hipergrafo, com $\mid V\mid =n$. Dizemos que $𝒞=\{c_1,c_2,\dots ,c_n\}$ é uma coloração própria de $\mathscr{H}$ se e somente se, para toda aresta $e\in ℰ$, exista pelo menos um par de vértices $v_1,v_2\in e$ tal que $c_1\ne c_2$.

Hipergrafos-clique

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

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

Bibliografia

• Predefinição:Citation