Teorema de Kőnig (teoría de grafos)

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, ya que cualquier cobertura de vértices debe incluir al menos un extremo de cada arista emparejada (así como de todas las demás aristas), por lo que esta es una cobertura de vértices mínima. De manera similar, no puede haber un emparejamiento mayor, ya que cualquier arista emparejada debe incluir al menos un extremo en la cobertura de vértices, por lo que esta es 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 forma más general a cualquier grafo bipartito.

La siguiente demostración proporciona una forma de construir una cobertura de vértices mínima a partir de un emparejamiento máximo. Sea${\displaystyle G=(V,E)}$Sea un grafo bipartito y sea${\displaystyle A,B}$sean las dos partes del conjunto de vértices${\displaystyle V}$. Supongamos que${\displaystyle M}$es una coincidencia máxima para${\displaystyle G}$.

Construir la red de flujo${\displaystyle G'_{\infty }}$derivado de${\displaystyle G}$de tal manera que existan límites de capacidad${\displaystyle 1}$de la fuente${\displaystyle s}$a cada vértice${\displaystyle a\in A}$y desde cada vértice${\displaystyle b\in B}$al fregadero${\displaystyle t}$y de capacidad${\displaystyle +\infty }$de${\displaystyle a}$a${\displaystyle b}$para cualquier${\displaystyle (a,b)\in E}$.

El tamaño${\displaystyle |M|}$del máximo emparejamiento en${\displaystyle G}$es el tamaño de un flujo máximo en${\displaystyle G'_{\infty }}$, que, a su vez, es el tamaño de un corte mínimo en la red${\displaystyle G'_{\infty }}$, como se deduce del teorema del flujo máximo y el corte mínimo .

Dejar${\displaystyle (S,T)}$ser un recorte mínimo.${\displaystyle A=A_{S}\cup A_{T}}$y${\displaystyle B=B_{S}\cup B_{T}}$, de tal manera que${\displaystyle A_{S},B_{S}\subset S}$y${\displaystyle A_{T},B_{T}\subset T}$Entonces, el corte mínimo se compone únicamente de aristas que van desde${\displaystyle s}$a${\displaystyle A_{T}}$o de${\displaystyle B_{S}}$a${\displaystyle t}$, como cualquier borde de${\displaystyle A_{S}}$a${\displaystyle B_{T}}$eso haría que el tamaño del corte fuera infinito.

Por lo tanto, el tamaño del corte mínimo es igual a${\displaystyle |A_{T}|+|B_{S}|}$. Por otro lado,${\displaystyle A_{T}\cup B_{S}}$es una cubierta de vértices, ya que cualquier arista que no sea incidente a vértices de${\displaystyle A_{T}}$y${\displaystyle B_{S}}$debe ser incidente a un par de vértices de${\displaystyle A_{S}}$y${\displaystyle B_{T}}$, lo cual contradiría el hecho de que no hay bordes entre${\displaystyle A_{S}}$y${\displaystyle B_{T}}$.

De este modo,${\displaystyle A_{T}\cup B_{S}}$es una cobertura de vértices mínima de${\displaystyle G}$. ^{[ 4 ]}

Ningún vértice en una cubierta de vértices puede cubrir más de una arista de${\displaystyle M}$(porque la superposición parcial del borde lo impediría)${\displaystyle M}$desde que se trata de una coincidencia en primer lugar), por lo que si una cubierta de vértices con${\displaystyle |M|}$Se pueden construir vértices, debe ser una cobertura mínima. ^{[ 5 ]}

Para construir dicha cubierta, deje que${\displaystyle U}$sea ​​el conjunto de vértices no coincidentes en${\displaystyle A}$(posiblemente vacío), y dejar${\displaystyle Z}$sea ​​el conjunto de vértices que están en${\displaystyle U}$o están conectados a${\displaystyle U}$mediante caminos alternados (caminos que alternan entre aristas que están en la coincidencia y aristas que no están en la coincidencia).

${\displaystyle K=(A\setminus Z)\cup (B\cap Z).}$

Cada borde${\displaystyle e}$en${\displaystyle E}$o pertenece a una ruta alterna (y tiene un punto final derecho en${\displaystyle K}$), o tiene un punto final izquierdo en${\displaystyle K}$. Porque, si${\displaystyle e}$está emparejado pero no en una ruta alterna, entonces su extremo izquierdo no puede estar en una ruta alterna (porque dos aristas emparejadas no pueden compartir un vértice) y por lo tanto pertenece a${\displaystyle A\setminus Z}$Alternativamente, si${\displaystyle e}$Si no coincide pero no está en una ruta alterna, entonces su extremo izquierdo no puede estar en una ruta alterna, ya que dicha ruta podría extenderse añadiendo${\displaystyle e}$a ello. Por lo tanto,${\displaystyle K}$forma una cubierta de vértices. ^{[ 6 ]}

Además, cada vértice en${\displaystyle K}$es un punto final de una arista coincidente. Porque, cada vértice en${\displaystyle A\setminus Z}$coincide porque${\displaystyle Z}$es un superconjunto de${\displaystyle U}$, el conjunto de vértices izquierdos no coincidentes. Y cada vértice en${\displaystyle B\cap Z}$También debe coincidir, ya que si existiera un camino alternativo hacia un vértice no coincidente, cambiar la coincidencia eliminando los bordes coincidentes de este camino 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${\displaystyle K}$. De este modo,${\displaystyle K}$es una cubierta de vértices de cardinalidad igual a${\displaystyle M}$y debe ser una cobertura de vértices mínima. ^{[ 6 ]}

Para explicar esta demostración, primero debemos extender la noción de emparejamiento a la de emparejamiento fraccional : una asignación de un peso en [0,1] a cada arista, de modo que la suma de los 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értices fraccional: una asignación de un peso no negativo a cada vértice, de modo que la suma de los pesos en cada arista sea al menos 1 (una cobertura de vértices integral es un caso especial de una cobertura de vértices fraccional en la que los pesos están en {0,1}).

El tamaño máximo de coincidencia fraccionaria en un gráfico${\displaystyle G=(V,E)}$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 una arista en el emparejamiento fraccional. 1 _E es un vector de | E | unos, por lo que la primera línea indica el tamaño del emparejamiento. 0 _E es un vector de | E | ceros, por lo que la segunda línea indica la restricción de que los pesos sean no 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 sea como máximo 1. De manera similar, el tamaño mínimo de cobertura de vértice fraccional en${\displaystyle G=(V,E)}$es la solución del siguiente problema de programación lineal:

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 representa el tamaño de la cobertura, la segunda la no negatividad de los pesos y la tercera el requisito de que la suma de los pesos cerca de cada arista sea al menos 1. Ahora bien, el programa lineal de cobertura fraccionaria mínima es exactamente el programa lineal dual del programa lineal de emparejamiento fraccionario máximo. Por lo tanto, según el teorema de dualidad de los programas lineales, ambos tienen la misma solución. Este hecho es cierto no solo en grafos bipartitos, sino también en grafos arbitrarios.

En cualquier grafo, el tamaño máximo de un emparejamiento fraccional es igual al tamaño mínimo de una cobertura de vértice fraccional.

Lo que hace especiales a los grafos bipartitos 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 emparejamiento fraccional de un grafo bipartito, todos los puntos extremos tienen coordenadas enteras , y lo mismo ocurre con el politopo de cobertura de vértices fraccional. Por lo tanto, el teorema anterior implica: ^{[ 7 ]}

En cualquier grafo bipartito, el tamaño máximo de un emparejamiento es igual al tamaño mínimo de una cobertura de vértices.

En el gráfico que se muestra en la introducción, tome${\displaystyle L}$ser el conjunto de vértices en la capa inferior del diagrama y${\displaystyle R}$ser el conjunto de vértices en la capa superior del diagrama. De izquierda a derecha, etiqueta los vértices en la capa inferior con los números 1, ..., 7 y etiqueta los vértices en la capa superior con los números 8, ..., 14. El conjunto${\displaystyle U}$de vértices no coincidentes de${\displaystyle L}$es {1}. Los caminos alternos que comienzan desde${\displaystyle U}$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. El conjunto${\displaystyle Z}$es por lo tanto {1,3,5,7,10,11,13}, lo que resulta en${\displaystyle L\setminus Z=\{2,4,6\}}$,${\displaystyle R\cap Z=\{10,11,13\}}$y la cobertura mínima de vértices${\displaystyle K=\{2,4,6,10,11,13\}}$.

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. Una cobertura de vértices w 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 grafo bipartito ponderado por aristas, el peso w máximo de un emparejamiento 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 un emparejamiento fraccional viene dado por el LP: ^{[ 18 ]}

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értices w fraccionaria viene dado por el LP dual:

Minimizar 1 _V · y

Sujeto a: y ≥ 0 _V

__________ A _G ^T · y ≥ w .

Al igual que en la demostración del teorema de Konig, el teorema de dualidad de la programación lineal implica que los valores óptimos son iguales (para cualquier grafo), y el hecho de que el grafo sea bipartito implica que estos programas tienen soluciones óptimas en las que todos los valores son 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 cobertura de vértices es la suma de b _v para todos los v en la cobertura. Un emparejamiento b es una asignación de un peso entero no negativo a cada arista, de tal manera que la suma de los pesos de las aristas adyacentes a cualquier vértice v es como máximo b _v . El teorema de Egerváry se puede extender, utilizando un argumento similar, a grafos que tienen pesos de aristas w y pesos de vértices b : ^{[ 18 ]}

En cualquier grafo bipartito ponderado por aristas y vértices, el peso w máximo de un emparejamiento b es igual al peso b mínimo de los vértices en una cobertura de vértices w .