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 (V,A), no qual A \subseteq (2^V \backslash \emptyset), onde 2^V é o conjunto das partes de V. [1]

O conjunto V é chamado de conjunto de vértices e o conjunto A é 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 \mathcal{H}=(V,\mathcal{E}) um hipergrafo, com \mid V\mid = n. Dizemos que \mathcal{C} = \{c_1, c_2, \ldots, c_n\} é uma coloração própria de \mathcal{H} se e somente se, para toda aresta e \in \mathcal{E}, exista pelo menos um par de vértices v_1,v_2 \in e tal que c_1 \neq c_2.

Hipergrafos-clique[editar | editar código-fonte]

Um hipergrafo-clique (denotado \mathcal{H}(G)) é um hipergrafo gerado a partir de um grafo G da seguinte forma:

  • V(\mathcal{H}) := V(G)
  • \mathcal{E}(\mathcal{H}) := \{e \in S(V(\mathcal{H})) \mid e é uma clique maximal de G\}

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