En teoría de grafos , un hipergrafo equilibrado es un hipergrafo que tiene varias propiedades análogas a las de un grafo bipartito .
Berge [1] introdujo los hipergrafos balanceados como una generalización natural de los grafos bipartitos. Proporcionó dos definiciones equivalentes.
Un hipergrafo H = ( V , E ) se llama 2-coloreable si sus vértices pueden ser 2-coloreados de modo que ninguna hiperarista sea monocromática. Todo grafo bipartito G = ( X + Y , E ) es 2-coloreable: cada arista contiene exactamente un vértice de X y un vértice de Y , de modo que, por ejemplo, X puede ser coloreado de azul e Y puede ser coloreado de amarillo y ninguna arista es monocromática.
Un hipergrafo en el que algunas hiperaristas son singletons (contienen solo un vértice) obviamente no es 2-coloreable; para evitar estos obstáculos triviales a la 2-coloreabilidad, es común considerar hipergrafos que son esencialmente 2-coloreables , es decir, se vuelven 2-coloreables al eliminar todas sus hiperaristas singleton. [2] : 468
Un hipergrafo se denomina equilibrado si es esencialmente 2-coloreable y permanece esencialmente 2-coloreable al eliminar cualquier número de vértices. Formalmente, para cada subconjunto U de V , defina la restricción de H a U como el hipergrafo H U = ( U , E U ) donde . Entonces H se denomina equilibrado si y solo si H U es esencialmente 2-coloreable para cada subconjunto U de V . Nótese que un grafo simple es bipartito si y solo si es 2-coloreable si y solo si está equilibrado.
Un ciclo (o circuito ) en un hipergrafo es una secuencia cíclica alternada de vértices e hiperaristas distintos: ( v 1 , e 1 , v 2 , e 2 , ..., v k , e k , v k +1 = v 1 ), donde cada vértice v i está contenido tanto en e i −1 como en e i . El número k se denomina longitud del ciclo.
Un hipergrafo está equilibrado si y solo si cada ciclo de longitud impar C en H tiene una arista que contiene al menos tres vértices de C. [3]
Nótese que en un grafo simple todas las aristas contienen solo dos vértices. Por lo tanto, un grafo simple está equilibrado si no contiene ciclos de longitud impar, lo que se cumple si es bipartito.
Berge [1] demostró que las dos definiciones son equivalentes; una prueba también está disponible aquí. [2] : 468–469
Algunos teoremas sobre grafos bipartitos se han generalizado a hipergrafos balanceados. [4] [2] : 468–470
Una transversal k -fold de un hipergrafo balanceado se puede expresar como una unión de k transversales disjuntas por pares, y dicha partición se puede obtener en tiempo polinomial. [6]
Además del equilibrio, existen generalizaciones alternativas de los grafos bipartitos. Un hipergrafo se denomina 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 (véase hipergrafo bipartito ). Obviamente, todo grafo bipartito es 2-coloreable.
Las propiedades de bipartidismo y equilibrio no se implican entre sí.
El equilibrio no implica bipartidismo . Sea H el hipergrafo: [7]
{ {1,2} , {3,4} , {1,2,3,4} }
Es bicolorable y sigue siendo bicolor al eliminar cualquier número de vértices de él. 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. La bipartición 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.
La tripartididad no implica equilibrio . Por ejemplo, sea H el hipergrafo tripartito con vértices {1,2},{3,4},{5,6} y aristas:
{ {1,3,5}, {2,4,5}, {1,4,6} }
No está equilibrado ya que si eliminamos los vértices 2,3,6, el resto es:
{ {1,5}, {4,5}, {1,4} }
que no es coloreable ya que es de 3 ciclos.
Otra forma de ver que no está equilibrado es que contiene el ciclo de longitud impar C = (1 - {1,3,5} - 5 - {2,4,5} - 4 - {1,4,6} - 1), y ninguna arista de C contiene los tres vértices 1,4,5 de C.
Un hipergrafo se denomina totalmente equilibrado si cada ciclo C en H de longitud al menos 3 ( no necesariamente de longitud impar) tiene una arista que contiene al menos tres vértices de C. [8]
Un hipergrafo H está totalmente equilibrado si y solo si cada subhipergrafo de H es un hipergrafo-árbol. [8]
La propiedad de Konig de un hipergrafo H es la propiedad de que su cobertura mínima de vértices tiene el mismo tamaño que su correspondencia máxima . El teorema de König-Egervary dice que todos los grafos bipartitos tienen la propiedad de Konig.
Los hipergrafos equilibrados son exactamente los hipergrafos H tales que cada subhipergrafo parcial de H tiene la propiedad Konig (es decir, H tiene la propiedad Konig incluso al eliminar cualquier número de hiperaristas y vértices).
Si cada hipergrafo parcial de H tiene la propiedad Konig (es decir, H tiene la propiedad Konig incluso al eliminar cualquier número de hiperaristas, pero no vértices), entonces H se denomina hipergrafo normal . [9]
Así pues, totalmente equilibrado implica equilibrado, lo cual implica normal.
