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 los gráficos ponderados .
Una cobertura de vértices en un gráfico es un conjunto de vértices que incluye al menos un extremo de cada borde, 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 dos no comparten un punto final, y una coincidencia es máxima si ninguna otra coincidencia tiene más aristas. [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 mínimo de cobertura de vértices es al menos tan grande como el conjunto máximo coincidente . El teorema de Kőnig establece que, en cualquier gráfico bipartito , el conjunto mínimo de cobertura de vértices y el conjunto máximo coincidente 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 mínima de vértices . [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 cualquier otro borde), por lo que esta es una cobertura de vértice mínima. De manera similar, no puede haber una coincidencia más grande, 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 coincidencia 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 mínima de vértices a partir de una coincidencia máxima. Sea un grafo bipartito y sean las dos partes del conjunto de vértices . Supongamos que es una coincidencia máxima para . Ningún vértice en una cubierta de vértices puede cubrir más de un borde (porque la mitad de la superposición de los bordes evitaría que coincidieran en primer lugar), por lo que si se puede construir una cubierta de vértices con vértices, debe ser una cubierta mínima. [4]
