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 , onde e é o conjunto das partes de V.
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 seria uma espécie de hipergrafo. Coloração de hipergrafos 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 Um hipergrafo-clique (denotado ) é um hipergrafo gerado a partir de um grafo G da seguinte forma:
é uma clique maximal de
Bibliografia
Categoria:Teoria dos grafos Categoria:Estruturas matemáticas
de:Graph (Graphentheorie)#Hypergraph