En el área matemática de la teoría de grafos , el teorema de Kőnig , demostrado por Dénes Kőnig (1931), describe una equivalencia entre el problema de emparejamiento máximo y el problema de recubrimiento mínimo de vértices en grafos bipartitos . Fue descubierto de forma independiente, también en 1931, por Jenő Egerváry en el caso más general de grafos ponderados .
Una cobertura de vértices en un gráfico es un conjunto de vértices que incluye al menos un punto final de cada arista, y una cobertura de vértices es mínima si ninguna otra cobertura de vértices tiene menos vértices. [1] Una coincidencia en un gráfico es un conjunto de aristas de las cuales ninguna de dos comparte un punto final, y una coincidencia es máxima si ninguna otra coincidencia tiene más aristas. [2]
De la definición se desprende claramente que cualquier conjunto de cobertura de vértices debe ser al menos tan grande como cualquier conjunto coincidente (ya que para cada arista en la coincidencia, se necesita al menos un vértice en la cobertura). En particular, el conjunto de cobertura de vértices mínimo es al menos tan grande como el conjunto coincidente máximo . El teorema de König establece que, en cualquier grafo bipartito , el conjunto de cobertura de vértices mínimo y el conjunto coincidente máximo tienen, de hecho, el mismo tamaño. [3]
En cualquier gráfico bipartito , el número de aristas en una coincidencia máxima es igual al número de vértices en una cobertura de vértices mínima . [3]
El grafo bipartito que se muestra en la ilustración anterior tiene 14 vértices; un emparejamiento con seis aristas se muestra en azul y una cobertura de vértices con seis vértices se muestra en rojo. No puede haber una cobertura de vértices menor, porque cualquier cobertura de vértices debe incluir al menos un punto final de cada arista emparejada (así como de cada una de las otras aristas), por lo que se trata de una cobertura de vértices mínima. De manera similar, no puede haber un emparejamiento mayor, porque cualquier arista emparejada debe incluir al menos un punto final en la cobertura de vértices, por lo que se trata de un emparejamiento máximo. El teorema de König establece que la igualdad entre los tamaños del emparejamiento y la cobertura (en este ejemplo, ambos números son seis) se aplica de manera más general a cualquier grafo bipartito.
La siguiente prueba proporciona una forma de construir una cobertura mínima de vértices a partir de una correspondencia máxima. Sea un grafo bipartito y sean las dos partes del conjunto de vértices . Supongamos que es una correspondencia máxima para .
Construya la red de flujo derivada de de tal manera que haya aristas de capacidad desde la fuente hasta cada vértice y desde cada vértice hasta el sumidero , y de capacidad desde hasta para cualquier .
El tamaño de la coincidencia máxima en es el tamaño de un flujo máximo en , que, a su vez, es el tamaño de un corte mínimo en la red , como se desprende del teorema de flujo máximo-corte mínimo .
Sea un corte mínimo. Sea y , tal que y . Entonces el corte mínimo está compuesto únicamente de aristas que van desde hasta o desde hasta , ya que cualquier arista desde hasta haría que el tamaño del corte fuera infinito.
Por lo tanto, el tamaño del corte mínimo es igual a . Por otra parte, es una cobertura de vértices, ya que cualquier arista que no sea incidente a los vértices de y debe ser incidente a un par de vértices de y , lo que contradeciría el hecho de que no hay aristas entre y .
Por lo tanto, la cobertura mínima de vértices es de . [4]
Ningún vértice en una cubierta de vértices puede cubrir más de un borde (porque la superposición de la mitad del borde evitaría que haya una coincidencia en primer lugar), por lo que si se puede construir una cubierta de vértices con vértices, debe ser una cubierta mínima. [5]
Para construir dicha cubierta, sea el conjunto de vértices no coincidentes en (posiblemente vacío), y sea el conjunto de vértices que están en o están conectados a través de caminos alternos (caminos que alternan entre aristas que están en la coincidencia y aristas que no están en la coincidencia). Sea
Cada arista en pertenece a un camino alterno (y tiene un punto final derecho en ), o tiene un punto final izquierdo en . Porque, si coincide pero no está en un camino alterno, entonces su punto final izquierdo no puede estar en un camino alterno (porque dos aristas coincidentes no pueden compartir un vértice) y por lo tanto pertenece a . Alternativamente, si no coincide pero no está en un camino alterno, entonces su punto final izquierdo no puede estar en un camino alterno, porque tal camino podría extenderse añadiéndole algo . Por lo tanto, forma una cubierta de vértices. [6]
Además, cada vértice en es un punto final de una arista coincidente. Porque, cada vértice en es coincidente porque es un superconjunto de , el conjunto de vértices izquierdos no coincidentes. Y cada vértice en también debe ser coincidente, porque si existiera un camino alternativo hacia un vértice no coincidente, entonces cambiar la coincidencia eliminando las aristas coincidentes de este camino y agregando las aristas no coincidentes en su lugar aumentaría el tamaño de la coincidencia. Sin embargo, ninguna arista coincidente puede tener ambos puntos finales en . Por lo tanto, es una cobertura de vértices de cardinalidad igual a , y debe ser una cobertura de vértices mínima. [6]
Para explicar esta prueba, primero tenemos que extender la noción de un emparejamiento a la de un emparejamiento fraccionario - una asignación de un peso en [0,1] a cada arista, de modo que la suma de pesos cerca de cada vértice sea como máximo 1 (un emparejamiento integral es un caso especial de un emparejamiento fraccionario en el que los pesos están en {0,1}). De manera similar, definimos una cobertura de vértices fraccionaria - una asignación de un peso no negativo a cada vértice, de modo que la suma de pesos en cada arista sea al menos 1 (una cobertura de vértices integral es un caso especial de una cobertura de vértices fraccionaria en el que los pesos están en {0,1}).
El tamaño máximo de coincidencia fraccional en un gráfico es la solución del siguiente programa lineal :
Maximizar 1 E · x
Sujeto a: x ≥ 0 E
__________ Un G · x ≤ 1 V .
donde x es un vector de tamaño | E | en el que cada elemento representa el peso de una arista en la correspondencia fraccionaria. 1 E es un vector de | E | unos, por lo que la primera línea indica el tamaño de la correspondencia. 0 E es un vector de | E | ceros, por lo que la segunda línea indica la restricción de que los pesos no son negativos. 1 V es un vector de | V | unos y A G es la matriz de incidencia de G, por lo que la tercera línea indica la restricción de que la suma de los pesos cerca de cada vértice es como máximo 1. De manera similar, el tamaño mínimo de cobertura de vértices fraccionarios en es la solución del siguiente PL:
Minimizar 1 V · y
Sujeto a: y ≥ 0 V
__________ A G T · y ≥ 1 E .
donde y es un vector de tamaño |V| en el que cada elemento representa el peso de un vértice en la cobertura fraccionaria. Aquí, la primera línea es el tamaño de la cobertura, la segunda línea representa la no negatividad de los pesos y la tercera línea representa el requisito de que la suma de los pesos cerca de cada arista debe ser al menos 1. Ahora, la cobertura fraccionaria mínima LP es exactamente el programa lineal dual del LP de coincidencia fraccionaria máxima. Por lo tanto, por el teorema de dualidad LP, ambos programas tienen la misma solución. Este hecho es cierto no solo en grafos bipartitos sino en grafos arbitrarios:
En cualquier gráfico, el tamaño más grande de una coincidencia fraccional es igual al tamaño más pequeño de una cobertura de vértice fraccional.
Lo que hace que los grafos bipartitos sean especiales es que, en ellos, ambos programas lineales tienen soluciones óptimas en las que todos los valores de las variables son enteros. Esto se deduce del hecho de que en el politopo de correspondencia fraccionaria de un grafo bipartito, todos los puntos extremos tienen solo coordenadas enteras, y lo mismo es cierto para el politopo de cobertura de vértices fraccionario. Por lo tanto, el teorema anterior implica: [7]
En cualquier gráfico bipartito, el tamaño más grande de una coincidencia es igual al tamaño más pequeño de una cubierta de vértice.
La prueba constructiva descrita anteriormente proporciona un algoritmo para producir una cobertura mínima de vértices dada una correspondencia máxima. Por lo tanto, el algoritmo de Hopcroft-Karp para encontrar correspondencias máximas en grafos bipartitos también puede usarse para resolver el problema de cobertura de vértices de manera eficiente en estos grafos. [8]
A pesar de la equivalencia de los dos problemas desde el punto de vista de las soluciones exactas, no son equivalentes para los algoritmos de aproximación . Los emparejamientos máximos bipartitos se pueden aproximar con una precisión arbitraria en tiempo constante mediante algoritmos distribuidos ; por el contrario, la aproximación de la cobertura mínima de vértices de un grafo bipartito requiere al menos un tiempo logarítmico. [9]
En el gráfico que se muestra en la introducción, tome como el conjunto de vértices en la capa inferior del diagrama y como el conjunto de vértices en la capa superior del diagrama. De izquierda a derecha, etiquete los vértices en la capa inferior con los números 1, …, 7 y etiquete los vértices en la capa superior con los números 8, …, 14. El conjunto de vértices no coincidentes de es {1}. Los caminos alternativos que comienzan desde son 1–10–3–13–7, 1–10–3–11–5–13–7, 1–11–5–13–7, 1–11–5–10–3–13–7 y todos los subcaminos de estos que comienzan desde 1. Por lo tanto, el conjunto es {1,3,5,7,10,11,13}, lo que da como resultado , y la cobertura mínima de vértices .
En el caso de los grafos que no son bipartitos, la cobertura mínima de vértices puede ser mayor que la correspondencia máxima. Además, los dos problemas son muy diferentes en complejidad: las correspondencias máximas se pueden encontrar en tiempo polinomial para cualquier grafo, mientras que la cobertura mínima de vértices es NP-completa .
El complemento de una cobertura de vértices en cualquier grafo es un conjunto independiente , por lo que una cobertura de vértices mínima es complementaria a un conjunto independiente máximo; encontrar conjuntos independientes máximos es otro problema NP-completo. La equivalencia entre emparejamiento y cobertura articulada en el teorema de König permite calcular coberturas de vértices mínimas y conjuntos independientes máximos en tiempo polinomial para grafos bipartitos, a pesar de la NP-completitud de estos problemas para familias de grafos más generales. [10]
El teorema de Kőnig debe su nombre al matemático húngaro Dénes Kőnig . Kőnig había anunciado en 1914 y publicado en 1916 los resultados de que todo grafo bipartito regular tiene un emparejamiento perfecto [ 11] y, de manera más general, que el índice cromático de cualquier grafo bipartito (es decir, el número mínimo de emparejamientos en los que se puede dividir) es igual a su grado máximo [12] ; esta última afirmación se conoce como el teorema de coloración de líneas de Kőnig . [13] Sin embargo, Bondy y Murty (1976) atribuyen el propio teorema de Kőnig a un artículo posterior de Kőnig (1931).
Según Biggs, Lloyd y Wilson (1976), Kőnig atribuyó la idea de estudiar los emparejamientos en grafos bipartitos a su padre, el matemático Gyula Kőnig . En húngaro, el nombre de Kőnig tiene doble acento agudo , pero su teorema a veces se escribe (incorrectamente) en caracteres alemanes, con diéresis .
El teorema de König es equivalente a muchos otros teoremas de min-max en teoría de grafos y combinatoria, como el teorema del matrimonio de Hall y el teorema de Dilworth . Dado que el emparejamiento bipartito es un caso especial de flujo máximo , el teorema también resulta del teorema de corte mínimo de flujo máximo . [14]
Se dice que un grafo es perfecto si, en cada subgrafo inducido , el número cromático es igual al tamaño del grupo más grande . Cualquier grafo bipartito es perfecto, [15] porque cada uno de sus subgrafos es bipartito o independiente; en un grafo bipartito que no es independiente, el número cromático y el tamaño del grupo más grande son ambos dos, mientras que en un conjunto independiente, el número cromático y el número del grupo son ambos uno.
Un grafo es perfecto si y solo si su complemento es perfecto, [16] y el teorema de König puede verse como equivalente a la afirmación de que el complemento de un grafo bipartito es perfecto. Porque, cada clase de color en una coloración del complemento de un grafo bipartito es de tamaño como máximo 2 y las clases de tamaño 2 forman una correspondencia, una camarilla en el complemento de un grafo G es un conjunto independiente en G , y como ya hemos descrito un conjunto independiente en un grafo bipartito G es un complemento de una cobertura de vértices en G . Por lo tanto, cualquier correspondencia M en un grafo bipartito G con n vértices corresponde a una coloración del complemento de G con n -| M | colores, que por la perfección de los complementos de grafos bipartitos corresponde a un conjunto independiente en G con n -| M | vértices, que corresponde a una cobertura de vértices de G con M vértices. Por el contrario, el teorema de Kőnig demuestra la perfección de los complementos de los grafos bipartitos, un resultado demostrado de forma más explícita por Gallai (1958).
También se puede conectar el teorema de coloración de líneas de Kőnig a una clase diferente de grafos perfectos, los grafos de líneas de grafos bipartitos. Si G es un grafo, el grafo de línea L ( G ) tiene un vértice para cada arista de G , y una arista para cada par de aristas adyacentes en G . Por lo tanto, el número cromático de L ( G ) es igual al índice cromático de G . Si G es bipartito, las camarillas en L ( G ) son exactamente los conjuntos de aristas en G que comparten un punto final común. Ahora bien, el teorema de coloración de líneas de Kőnig, que establece que el índice cromático es igual al grado máximo del vértice en cualquier grafo bipartito, se puede interpretar como que establece que el grafo de línea de un grafo bipartito es perfecto. [17]
Como los gráficos lineales de los grafos bipartitos son perfectos, los complementos de los gráficos lineales de los grafos bipartitos también son perfectos. Una camarilla en el complemento del gráfico lineal de G es simplemente una coincidencia en G . Y una coloración en el complemento del gráfico lineal de G , cuando G es bipartito, es una partición de las aristas de G en subconjuntos de aristas que comparten un punto final común; los puntos finales compartidos por cada uno de estos subconjuntos forman una cubierta de vértices para G . Por lo tanto, el propio teorema de Kőnig también puede interpretarse como que afirma que los complementos de los gráficos lineales de los grafos bipartitos son perfectos. [17]
El teorema de Konig puede extenderse a gráficos ponderados .
Jenő Egerváry (1931) consideró grafos en los que cada arista e tiene un peso entero no negativo w e . El vector de pesos se denota por w . El peso w de un emparejamiento es la suma de los pesos de las aristas que participan en el emparejamiento. Un w- vertex-cover es un multiconjunto de vértices ("multiconjunto" significa que cada vértice puede aparecer varias veces), en el que cada arista e es adyacente a al menos w e vértices. El teorema de Egerváry dice:
En cualquier gráfico bipartito ponderado por aristas, el peso w máximo de una coincidencia es igual al número más pequeño de vértices en una cobertura de vértices w .
El peso w máximo de una correspondencia fraccionaria viene dado por el LP: [18]
Maximizar w · x
Sujeto a: x ≥ 0 E
__________ Un G · x ≤ 1 V .
Y el número mínimo de vértices en una cubierta de vértices w fraccional está dado por el LP dual:
Minimizar 1 V · y
Sujeto a: y ≥ 0 V
__________ A G T · y ≥ w .
Al igual que en la prueba del teorema de Konig, el teorema de dualidad LP implica que los valores óptimos son iguales (para cualquier gráfico), y el hecho de que el gráfico sea bipartito implica que estos programas tienen soluciones óptimas en las que todos los valores son números enteros.
Se puede considerar un grafo en el que cada vértice v tiene un peso entero no negativo b v . El vector de pesos se denota por b . El peso b de una cubierta de vértices es la suma de b v para todos los v en la cubierta. Una b -coincidencia es una asignación de un peso entero no negativo a cada arista, de modo que la suma de los pesos de las aristas adyacentes a cualquier vértice v sea como máximo b v . El teorema de Egerváry se puede extender, utilizando un argumento similar, a grafos que tienen pesos de arista w y pesos de vértice b : [18]
En cualquier gráfico bipartito ponderado por aristas y ponderado por vértices, el peso w máximo de una coincidencia b es igual al peso b mínimo de los vértices en una cobertura de vértices w .
