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

Definição

editar

Definimos 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

editar

Definimos 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

editar

Um 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