Metraipolis › archive › dc_db5075c64ce7

Kőnig's theorem (graph theory) — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-06T12:51:55.697Z
SHA-256 of the archived text
c1304e3aee601c2e4cde7269e05740b623a20dc7c9e7fab05e9beb5ef40bba5a
Stable URL of this page
https://metraipolis.com/documento/dc_db5075c64ce7

How to cite

Kőnig's theorem (graph theory) — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_db5075c64ce7 (Metraipolis archive dc_db5075c64ce7, sha256 c1304e3aee601c2e4cde7269e05740b623a20dc7c9e7fab05e9beb5ef40bba5a)
BibTeX
@misc{dcdb5075c64ce7,
  title = {Kőnig's theorem (graph theory) — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_db5075c64ce7; sha256 c1304e3aee601c2e4cde7269e05740b623a20dc7c9e7fab05e9beb5ef40bba5a},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory). Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Kőnig's theorem (graph theory)» — https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)
Wikidata Q897769: «theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q897769
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1352721742, consultata il 2026-10-06T11:07:58.665Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 29df68b0ee3b63ca3eea9563ff92b7d825b3f7c812e6a46e93510c63a01d3fd1