Hipergrafo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa


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 | editar código-fonte]

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 hipergrafos[editar | editar código-fonte]

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 | editar código-fonte]

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)

Bibliografia[editar | editar código-fonte]

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