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
editarDefinimos um hipergrafo como um par ordenado , onde e é o conjunto das partes de V. [1]
O conjunto é chamado de conjunto de vértices e o conjunto é 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.
Coloração de hipergrafos
editarDefinimos a coloração de hipergrafos da seguinte forma: seja um hipergrafo, com . Dizemos que é uma coloração própria de se e somente se, para toda aresta , exista pelo menos um par de vértices tal que .
Hipergrafos-clique
editarUm hipergrafo-clique (denotado ) é um hipergrafo gerado a partir de um grafo G da seguinte forma:
- é uma clique maximal de
Referências
Bibliografia
editar- Jonatan Lindén (2007), Hypergraphs and Matroids, Lyon