Teorema de Kőnig (teoría de grafos)
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 .
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értice 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]
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]
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.
La siguiente prueba proporciona una forma de construir una cobertura de vértice mínima a partir de una coincidencia máxima. Sea un gráfico bipartito y sean las dos partes del conjunto de vértices . Suponga 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 que coincida en primer lugar), por lo que si se puede construir una cobertura de vértice con vértices, debe ser una cobertura mínima. [4]
