Abrir menu principal


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

DefiniçãoEditar

Definimos um hipergrafo como um par ordenado  , no qual  , onde   é 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.


Coloração de hipergrafosEditar

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-cliqueEditar

Um hipergrafo-clique (denotado  ) é um hipergrafo gerado a partir de um grafo G da seguinte forma:

  •  
  •   é uma clique maximal de  

Referências

  1. David A. Papa and Igor L. Markov. Hypergraph Partitioning and Clustering. University of Michigan, EECS (http://www.podload.org/pubs/book/part_survey.pdf)

BibliografiaEditar

  • Jonatan Lindén (2007), Hypergraphs and Matroids, Lyon