Em teoria dos grafos, um hipergrafo é uma generalização de um grafo, com suas arestas ligando quaisquer quantidades positivas de vértices.
Definimos um hipergrafo como um par ordenado ( V , A ) {\displaystyle (V,A)} conjunto das partes de V.
, onde A ⊆ ( ℘ ( X ) ∖ { ∅ } ) {\displaystyle A\subseteq (\wp (X)\setminus \{\emptyset \})} e ℘ ( X ) {\displaystyle \wp (X)} é oO conjunto V {\displaystyle V} 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.
é chamado de conjunto de vértices e o conjunto A {\displaystyle A} é o conjunto de hiperarestas. Ou seja, um hipergrafo é um conjunto de vértices associado com um conjunto de hiperarestas, sendo que cada hiperaresta é umUma curiosidade é que se o conjunto de hiperarestas pudesse possuir o conjunto vazio, todo espaço mensurável seria uma espécie de hipergrafo.
Definimos a coloração de hipergrafos da seguinte forma: seja H = ( V , E ) {\displaystyle {\mathcal {H}}=(V,{\mathcal {E}})} se e somente se, para toda aresta e ∈ E {\displaystyle e\in {\mathcal {E}}} , exista pelo menos um par de vértices v 1 , v 2 ∈ e {\displaystyle v_{1},v_{2}\in e} tal que c 1 ≠ c 2 {\displaystyle c_{1}\neq c_{2}} .
um hipergrafo, com ∣ V ∣= n {\displaystyle \mid V\mid =n} . Dizemos que C = { c 1 , c 2 , … , c n } {\displaystyle {\mathcal {C}}=\{c_{1},c_{2},\ldots ,c_{n}\}} é uma coloração própria de H {\displaystyle {\mathcal {H}}}Um hipergrafo-clique (denotado H ( G ) {\displaystyle {\mathcal {H}}(G)}
) é um hipergrafo gerado a partir de um grafo G da seguinte forma: