En teoría de grafos , el término hipergrafo bipartito describe varias clases relacionadas de hipergrafos , todas las cuales son generalizaciones naturales de un grafo bipartito .
La definición más débil de bipartidismo también se llama 2-colorabilidad . Un hipergrafo H = ( V , E ) se llama 2-coloreable si su conjunto de vértices V se puede dividir en dos conjuntos, X e Y , de modo que cada hiperarista se encuentra con X e Y . Equivalentemente, los vértices de H pueden ser 2-coloreados de modo que ninguna hiperarista sea monocromática. Cada grafo bipartito G = ( X + Y , E ) es 2-coloreable: cada arista contiene exactamente un vértice de X y un vértice de Y , por lo que, por ejemplo, X puede colorearse de azul e Y puede colorearse de amarillo y ninguna arista es monocromática.
La propiedad de 2-colorabilidad fue introducida por primera vez por Felix Bernstein en el contexto de familias de conjuntos; [1] por lo tanto, también se llama Propiedad B.
Una definición más fuerte de bipartidismo es: un hipergrafo se llama bipartito si su conjunto de vértices V se puede dividir en dos conjuntos, X e Y , de modo que cada hiperarista contiene exactamente un elemento de X. [2] [3] Todo grafo bipartito es también un hipergrafo bipartito.
Todo hipergrafo bipartito es bicoloreable, pero la bipartididad es más fuerte que la bicoloreabilidad. Sea H un hipergrafo en los vértices {1, 2, 3, 4} con las siguientes hiperaristas:
{ {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} }
Este H es 2-coloreable, por ejemplo por la partición X = {1,2} e Y = {3,4}. Sin embargo, no es bipartito, ya que todo conjunto X con un elemento tiene una intersección vacía con una hiperarista, y todo conjunto X con dos o más elementos tiene una intersección de tamaño 2 o más con al menos dos hiperaristas.
El teorema del matrimonio de Hall se ha generalizado desde grafos bipartitos a hipergrafos bipartitos; véase Teoremas de tipo Hall para hipergrafos .
Una definición más fuerte es: dado un entero n , un hipergrafo se llama n -uniforme si todas sus hiperaristas contienen exactamente n vértices. Un hipergrafo n -uniforme se llama n -partito si su conjunto de vértices V se puede dividir en n subconjuntos de manera que cada hiperarista contenga exactamente un elemento de cada subconjunto. [4] Un término alternativo es arcoíris-coloreable . [5]
Todo hipergrafo de n- partididad es bipartito, pero la n-partididad es más fuerte que la bipartididad. Sea H un hipergrafo en los vértices {1, 2, 3, 4} con las siguientes hiperaristas:
{ {1,2,3} , {1,2,4} , {1,3,4} }
Esta H es 3-uniforme. Es bipartita por la partición X = {1} e Y = {2,3,4}. Sin embargo, no es 3-partita: en cada partición de V en 3 subconjuntos, al menos un subconjunto contiene dos vértices y, por lo tanto, al menos una hiperarista contiene dos vértices de este subconjunto.
Un hipergrafo de 3 partes se suele denominar "hipergrafo tripartito". Sin embargo, un hipergrafo de 2 partes no es lo mismo que un hipergrafo bipartito; es equivalente a un grafo bipartito .
Existen otras generalizaciones naturales de los grafos bipartitos. Un hipergrafo se denomina equilibrado si es esencialmente bicolorable y permanece esencialmente bicolorable al eliminar cualquier número de vértices (ver Hipergrafo equilibrado ).
Las propiedades de bipartidismo y equilibrio no se implican entre sí.
La bipartididad no implica equilibrio. Por ejemplo, sea H el hipergrafo con vértices {1,2,3,4} y aristas:
{ {1,2,3} , {1,2,4} , {1,3,4} }
Es bipartita por la partición X = {1}, Y = {2,3,4}. Pero no está balanceada. Por ejemplo, si se elimina el vértice 1, obtenemos la restricción de H a {2,3,4}, que tiene las siguientes hiperaristas:
{ {2,3}, {2,4}, {3,4}}
No es 2-coloreable, ya que en cualquier 2-coloración hay al menos dos vértices con el mismo color, y por lo tanto al menos una de las hiperaristas es monocromática.
Otra forma de ver que H no está equilibrado es que contiene el ciclo de longitud impar C = (2 - {1,2,3} - 3 - {1,3,4} - 4 - {1,2,4} - 2), y ninguna arista de C contiene los tres vértices 2,3,4 de C.
El equilibrio no implica bipartidismo. Sea H el hipergrafo: [ cita requerida ]
{ {1,2} , {3,4} , {1,2,3,4} }
Es bicolor y permanece bicolor si se le quita cualquier número de vértices. Sin embargo, no es bipartito, ya que para tener exactamente un vértice verde en cada una de las dos primeras hiperaristas, debemos tener dos vértices verdes en la última hiperarista.