En el área matemática de la teoría de grafos , el teorema de Kőnig , probado por Dénes Kőnig ( 1931 ), describe una equivalencia entre el problema de coincidencia máxima y el problema de cobertura mínima 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 gráficos ponderados .
Configuración
Una cobertura de vértice en un gráfico es un conjunto de vértices que incluye al menos un punto final de cada borde, y una cobertura de vértice es mínima si ninguna otra cobertura de vértice tiene menos vértices. [1] Una coincidencia en un gráfico es un conjunto de bordes de los cuales no hay dos que compartan un punto final, y una coincidencia es máxima si ninguna otra coincidencia tiene más bordes. [2]
Es obvio a partir de la definición que cualquier conjunto de cobertura de vértices debe ser al menos tan grande como cualquier conjunto coincidente (ya que para cada borde en la coincidencia, se necesita al menos un vértice en la cobertura). En particular, el conjunto de cobertura de vértice mínimo es al menos tan grande como el conjunto de coincidencia máximo . El teorema de Kőnig establece que, en cualquier gráfico bipartito , el conjunto de cobertura de vértice mínimo y el conjunto de coincidencia máximo tienen de hecho el mismo tamaño. [3]
Declaración del teorema
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értice mínima . [3]
Ejemplo
El gráfico bipartito que se muestra en la ilustración anterior tiene 14 vértices; una coincidencia con seis aristas se muestra en azul y una cubierta de vértice con seis vértices se muestra en rojo. No puede haber una cobertura de vértice más pequeña, porque cualquier cobertura de vértice debe incluir al menos un punto final de cada borde coincidente (así como de todos los demás bordes), por lo que esta es una cobertura de vértice mínima. De manera similar, no puede haber una coincidencia mayor, porque cualquier borde coincidente debe incluir al menos un punto final en la cobertura del vértice, por lo que esta es una coincidencia máxima. El teorema de Kőnig establece que la igualdad entre los tamaños de la correspondencia y la cubierta (en este ejemplo, ambos números son seis) se aplica de manera más general a cualquier gráfico bipartito.
Pruebas
Prueba constructiva
La siguiente demostración proporciona una forma de construir una cobertura de vértice mínima a partir de una coincidencia máxima. Dejar ser un gráfico bipartito y dejar ser las dos partes del conjunto de vértices . Suponer que es una coincidencia máxima para . Ningún vértice en una cobertura de vértice puede cubrir más de un borde de (porque la mitad de la superposición del borde evitaría de ser una coincidencia en primer lugar), por lo que si un vértice cubre con se pueden construir vértices, debe ser una cobertura mínima. [4]
Para construir tal cubierta, dejemos ser el conjunto de vértices incomparables en (posiblemente vacío), y deje ser el conjunto de vértices que están en o están conectados a alternando caminos (caminos que alternan entre los bordes que están en la coincidencia y los bordes que no están en la coincidencia). Dejar
Cada borde en pertenece a una ruta alterna (y tiene un extremo derecho en ), o tiene un extremo izquierdo en . Por si está emparejado pero no en una ruta alterna, entonces su punto final izquierdo no puede estar en una ruta alterna (porque dos bordes emparejados no pueden compartir un vértice) y por lo tanto pertenece a . Alternativamente, si es incomparable pero no en una ruta alterna, entonces su punto final izquierdo no puede estar en una ruta alterna, ya que dicha ruta podría extenderse agregando lo. Por lo tanto,forma una cubierta de vértice. [5]
Además, cada vértice en es un punto final de un borde coincidente. Porque, cada vértice en se empareja porque es un superconjunto de , el conjunto de vértices izquierdos no coincidentes. Y cada vértice entambién deben coincidir, ya que si existiera una ruta alterna a un vértice no coincidente, cambiar la coincidencia eliminando los bordes coincidentes de esta ruta y agregando los bordes no coincidentes en su lugar aumentaría el tamaño de la coincidencia. Sin embargo, ningún borde coincidente puede tener ambos extremos en. Por lo tanto, es una cubierta de vértice de cardinalidad igual a , y debe tener una cobertura mínima de vértices. [5]
Prueba usando dualidad de programación lineal
Para explicar esta demostración, primero tenemos que extender la noción de coincidencia a la de coincidencia fraccional : una asignación de un peso en [0,1] a cada borde, 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 emparejamiento fraccional en el que los pesos están en {0,1}). De manera similar, definimos una cobertura de vértice fraccional: una asignación de un peso no negativo a cada vértice, de modo que la suma de pesos en cada borde sea al menos 1 (una cobertura de vértice integral es un caso especial de una cobertura de vértice fraccional 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
__________ A G · x ≤ 1 V .
donde x es un vector de tamaño | E | en el que cada elemento representa el peso de un borde en la coincidencia fraccional. 1 E es un vector de | E | unos, por lo que la primera línea indica el tamaño de la coincidencia. 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 pesos cerca de cada vértice es como máximo 1. De manera similar, el tamaño mínimo de cobertura de vértice fraccional en es la solución del siguiente LP:
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 cubierta, la segunda línea representa la no negatividad de los pesos y la tercera línea representa el requisito de que la suma de pesos cerca de cada borde debe ser al menos 1. Ahora, la fracción mínima cover LP es exactamente el programa lineal dual del LP de coincidencia fraccional máximo. Por lo tanto, según el teorema de la dualidad LP, ambos programas tienen la misma solución. Este hecho es cierto no solo en gráficos bipartitos sino en gráficos 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 gráficos bipartitos sean especiales es que, en los gráficos bipartitos, ambos programas lineales tienen soluciones óptimas en las que todos los valores de las variables son números enteros. Esto se deriva del hecho de que en el politopo de coincidencia fraccional de un gráfico bipartito, todos los puntos extremos tienen solo coordenadas enteras, y lo mismo es cierto para el politopo de cobertura de vértice fraccional. Por lo tanto, el teorema anterior implica: [6] : 270
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.
Algoritmo
La prueba constructiva descrita anteriormente proporciona un algoritmo para producir una cobertura de vértice mínima dada una coincidencia máxima. Por lo tanto, el algoritmo de Hopcroft-Karp para encontrar coincidencias máximas en gráficos bipartitos también puede usarse para resolver el problema de cobertura de vértices de manera eficiente en estos gráficos. [7]
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 de forma arbitraria y precisa en tiempo constante mediante algoritmos distribuidos ; por el contrario, la aproximación de la cobertura mínima de vértices de un gráfico bipartito requiere al menos un tiempo logarítmico. [8]
Ejemplo
En el gráfico que se muestra en la introducción, tome para ser el conjunto de vértices en la capa inferior del diagrama y para ser el conjunto de vértices en la capa superior del diagrama. De izquierda a derecha, etiquete los vértices de la capa inferior con los números 1,…, 7 y etiquete los vértices de la capa superior con los números 8,…, 14. El conjunto de vértices incomparables de es {1}. Los caminos alternos partiendo de 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 subtrazados de estos a partir de 1. El conjunto es por lo tanto {1,3,5,7,10,11,13}, lo que resulta en , y la cobertura mínima de vértices .
Gráficos no bipartitos
Para gráficos que no son bipartitos, la cobertura mínima del vértice puede ser mayor que la coincidencia máxima. Además, los dos problemas son muy diferentes en complejidad: las coincidencias máximas se pueden encontrar en el tiempo polinomial para cualquier gráfico, mientras que la cobertura mínima de vértices es NP-completa .
El complemento de una cobertura de vértice en cualquier gráfico es un conjunto independiente , por lo que una cobertura de vértice mínima es complementaria a un conjunto máximo independiente; encontrar conjuntos máximos independientes es otro problema NP-completo. La equivalencia entre emparejamiento y cobertura articulada en el teorema de Kőnig permite que las cubiertas de vértices mínimas y los conjuntos independientes máximos se calculen en tiempo polinómico para gráficos bipartitos, a pesar de la completitud NP de estos problemas para familias de gráficos más generales. [9]
Historia
El teorema de Kőnig lleva el nombre del matemático húngaro Dénes Kőnig . Kőnig había anunciado en 1914 y publicado en 1916 los resultados de que todo gráfico bipartito regular tiene una coincidencia perfecta , [10] y, de manera más general, que el índice cromático de cualquier gráfico bipartito (es decir, el número mínimo de coincidencias en las que se puede dividir ) es igual a su grado máximo [11] - este último enunciado se conoce como teorema de coloración de líneas de Kőnig . [6] : Teorema 1.4.17, págs. 37 y siguientes. Sin embargo, Bondy y Murty (1976) atribuyen el teorema de Kőnig en sí mismo a un artículo posterior de Kőnig (1931).
Según Biggs, Lloyd & Wilson (1976) , Kőnig atribuyó la idea de estudiar emparejamientos en gráficos bipartitos a su padre, el matemático Gyula Kőnig . En húngaro, el nombre de Kőnig tiene un doble acento agudo , pero su teorema generalmente se escribe en caracteres alemanes, con diéresis .
Teoremas relacionados
El teorema de Kőnig es equivalente a muchos otros teoremas mínimo-máximo 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 . [12]
Conexiones con gráficos perfectos
Se dice que una gráfica es perfecta si, en cada subgrafía inducida , el número cromático es igual al tamaño de la camarilla más grande . Cualquier gráfico bipartito es perfecto, [13] porque cada uno de sus subgrafos es bipartito o independiente; en un gráfico bipartito que no es independiente, el número cromático y el tamaño de la camarilla más grande son dos mientras que en un conjunto independiente el número cromático y el número de camarilla son uno.
Una gráfica es perfecta si y solo si su complemento es perfecto, [14] y el teorema de Kőnig puede considerarse equivalente al enunciado de que el complemento de una gráfica bipartita es perfecto. Porque, cada clase de color en una coloración del complemento de un gráfico bipartito tiene un tamaño máximo de 2 y las clases de tamaño 2 forman una coincidencia, una camarilla en el complemento de un gráfico G es un conjunto independiente en G , y como nosotros ya han descrito un conjunto independiente en un gráfico bipartito G es un complemento de una cubierta de vértice en G . Por lo tanto, cualquier M coincidente en un gráfico 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 complementos de grafos bipartitos corresponde a un conjunto independiente en G con n - | M | vértices, que corresponde a una cubierta de vértice 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, resultado que Gallai (1958) demostró de forma más explícita .
También se puede conectar el Teorema de coloración lineal de Kőnig con una clase diferente de gráficos perfectos, los gráficos lineales de gráficos bipartitos. Si G es un gráfico, el gráfico de la línea L ( G ) tiene un vértice para cada borde de G , y un borde para cada par de bordes adyacentes en G . Así, el número cromática 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, el Teorema de coloración lineal de Kőnig, que establece que el índice cromático es igual al grado máximo de vértice en cualquier gráfico bipartito, se puede interpretar como una afirmación de que el gráfico lineal de un gráfico bipartito es perfecto. [15]
Dado que los gráficos lineales de los gráficos bipartitos son perfectos, los complementos de los gráficos lineales de los gráficos bipartitos también son perfectos. A clique en el complemento de la línea gráfico de G es sólo un juego en G . Y una coloración en el complemento del gráfico lineal de G , cuando G es bipartito, es una partición de los bordes de G en subconjuntos de bordes que comparten un punto final común; los puntos finales compartidos por cada uno de estos subconjuntos forman una cubierta de vértice para G . Por lo tanto, el teorema de Kőnig en sí mismo también se puede interpretar en el sentido de que los complementos de las gráficas lineales de las gráficas bipartitas son perfectos. [15]
Variantes ponderadas
El teorema de Konig se puede extender a gráficos ponderados .
Teorema de Egerváry para gráficas ponderadas por aristas
Jenő Egerváry (1931) consideró gráficos en los que cada borde e tiene un peso entero no negativo w e . El vector de peso se denota por w . El peso w de un emparejamiento es la suma de los pesos de los bordes que participan en el emparejamiento. Una cubierta de vértice w es un conjunto múltiple de vértices ("conjunto múltiple" significa que cada vértice puede aparecer varias veces), en el que cada borde e es adyacente a al menos w e vértices. El teorema de Egerváry dice:
En cualquier grafo 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értice w .
El peso w máximo de una coincidencia fraccional viene dado por el LP: [6] : 271
Maximizar w · x
Sujeto a: x ≥ 0 E
__________ A G · x ≤ 1 V .
Y el número mínimo de vértices en una cobertura de vértice w fraccional viene dado por el LP dual:
Minimizar 1 V · y
Sujeto a: y ≥ 0 V
__________ A G T · y ≥ w .
Como en la demostración 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.
Teorema para gráficas ponderadas por vértices
Se puede considerar una gráfica en la que cada vértice v tiene un peso entero no negativo b v . El vector de peso se denota por b . El peso b de una cubierta de vértice es la suma de b v para todo v en la cubierta. Un emparejamiento b es una asignación de un peso integral no negativo a cada borde, de modo que la suma de los pesos de los bordes adyacentes a cualquier vértice v es como máximo b v . El teorema de Egervary se puede extender, usando un argumento similar, a gráficos que tienen pesos de arista w y pesos de vértice b : [6] : 271
En cualquier gráfico bipartito vértice-ponderado borde-ponderado, el máximo w- peso de un b De equiparación es igual al mínimo b -peso de vértices en un w- vértice de la cubierta.
Ver también
- Propiedad de Kőnig en hipergrafos
Notas
- ↑ Llamado recubrimiento y recubrimiento mínimo respectivamente por Bondy y Murty (1976) , p. 73.
- ^ Bondy y Murty (1976) , p. 70.
- ↑ a b Bondy y Murty (1976) , Teorema 5.3, p. 74; Cook y col. (2011) .
- ^ Bondy y Murty (1976) , Lema 5.3, p. 74.
- ↑ a b Bondy y Murty (1976) , págs. 74–75.
- ^ a b c d Lovász, László ; Plummer, MD (1986), Teoría de emparejamiento , Annals of Discrete Mathematics, 29 , Holanda Septentrional, ISBN 0-444-87916-1, MR 0859549
- ^ Para este algoritmo, consulte Storer (2001) , p 319, y para la conexión con la cobertura de vértices, consulte la p. 342.
- ^ Göös y Suomela (2012) .
- ^ Storer (2001) , ejercicio 261, p. 342 .
- ↑ En un cartel exhibido en el Congreso Internacional de Matemáticos de 1998en Berlín y nuevamente en la Conferencia Internacional Bled'07 sobre Teoría de Gráficos, Harald Gropp ha señalado que el mismo resultado ya aparece en el lenguaje de las configuraciones en la tesis de Ernst Steinitz de 1894..
- ^ Biggs, Lloyd y Wilson (1976) .
- ^ Cook y col. (2011) .
- ^ "Trivialmente", según Lovász (1974) .
- ^ Este es el teorema del gráfico perfecto de Lovász (1972)
- ↑ a b Lovász (1974) .
Referencias
- Biggs, EK; Lloyd; Wilson, RJ (1976), Graph Theory 1736-1936 , Oxford University Press, págs. 203-207, ISBN 0-19-853916-9.
- Cook, William J .; Cunningham, William H .; Pulleyblank, William R .; Schrijver, Alexander (2011), Optimización combinatoria , Serie Wiley en Matemáticas discretas y optimización, 33 , John Wiley & Sons, págs. 48–49, ISBN 9781118031391.
- Bondy, JA ; Murty, USR (1976), Teoría de grafos con aplicaciones , Holanda Septentrional, ISBN 0-444-19451-7.
- Gallai, Tibor (1958), "Máximo-mínimo Sätze über Graphen", Acta Math. Acad. Sci. Colgado. , 9 (3–4): 395–434, doi : 10.1007 / BF02020271 , MR 0124238.
- Göös, Mika; Suomela, Jukka (2012), "No hay esquema de aproximación de tiempo sublogarítmico para la cobertura de vértices bipartitos", 26 ° Simposio Internacional de Computación Distribuida (DISC), Salvador, Brasil, octubre de 2012 , arXiv : 1205.4605 , Bibcode : 2012arXiv1205.4605G.
- Kőnig, Dénes (1916), "Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére", Matematikai és Természettudományi Értesítő , 34 : 104-119.
- Kőnig, Dénes (1931), "Gráfok és mátrixok", Matematikai és Fizikai Lapok , 38 : 116-119.
- Lovász, László (1972), "Hipergrafías normales y la conjetura de la gráfica perfecta", Matemáticas discretas , 2 (3): 253-267, doi : 10.1016 / 0012-365X (72) 90006-4 , MR 0302480.
- Lovász, László (1974), "Teoremas Minimax para hipergráficos", Seminario Hypergraph (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; dedicado a Arnold Ross) , Berlín: Springer, págs. 111-126 . Lecture Notes in Math., Vol. 411, doi : 10.1007 / BFb0066186 , MR 0406862.
- Storer, JA (2001), Introducción a las estructuras de datos y algoritmos , Progresos en informática y serie de lógica aplicada, Springer, ISBN 9780817642532.