Teorema de König
König's theorem
- Fecha
- 1931 · fiabilidad alta
- Lugar
- Budapest, Hungría
- Autoría
- Dénes Kőnig
- Ámbito
- Saber y símbolos
Qué se descubrió
Teorema de teoría de grafos que establece la equivalencia entre el emparejamiento máximo y la cobertura mínima de vértices en grafos bipartitos; demostrado por Dénes Kőnig en 1931 y, de forma independiente y más general, por Jenő Egerváry el mismo año.
A qué dio paso
- algoritmos eficientes de emparejamiento en grafos bipartitos
- base combinatoria del método húngaro de asignación
- aplicaciones en problemas de asignación de recursos y logística
- conexión con la dualidad en programación lineal