König's theorem
Teorema de König
- Date
- 1931 · confidence high
- Place
- Budapest, Hungary
- Credited to
- Dénes Kőnig
- Field
- Knowledge & symbols
What was discovered
A graph theory theorem establishing an equivalence between maximum matching and minimum vertex cover in bipartite graphs, proved by Dénes Kőnig in 1931 and, independently and more generally, by Jenő Egerváry the same year.
What it led to
- efficient matching algorithms for bipartite graphs
- combinatorial basis of the Hungarian assignment method
- applications in resource allocation and logistics problems
- connection to duality in linear programming