Metraipolis › archive › dc_7361862caab3

Maximum-cardinality matching — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Maximum-cardinality_matching
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T23:23:03.293Z
SHA-256 of the archived text
01c09699ceb4a22e38c682feb5c40b020aec47eab0f8e9a5624a0d8df02b537d
Stable URL of this page
https://metraipolis.com/documento/dc_7361862caab3

How to cite

Maximum-cardinality matching — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Maximum-cardinality_matching (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_7361862caab3 (Metraipolis archive dc_7361862caab3, sha256 01c09699ceb4a22e38c682feb5c40b020aec47eab0f8e9a5624a0d8df02b537d)
BibTeX
@misc{dc7361862caab3,
  title = {Maximum-cardinality matching — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Maximum-cardinality_matching},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_7361862caab3; sha256 01c09699ceb4a22e38c682feb5c40b020aec47eab0f8e9a5624a0d8df02b537d},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Maximum-cardinality_matching. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In graph theory, a maximum-cardinality matching is a special kind of subgraph useful in many computational contexts. Given a graph G, a matching is a subgraph where no two edges share a vertex. The cardinality of the matching is the number of edges in the subgraph, and the maximum cardinality is the largest number of edges a matching can contain. A matching for a given graph is a maximum-cardinality matching if its cardinality is this maximum cardinality. If we think of each edge as "covering" the vertices it connects exactly once, then a maximal matching is also the largest non-overlapping cover of the graph. If all the vertices are covered, we call it a perfect matching. For finite graphs, a maximum-cardinality matching always exists, but is not usually unique. The cardinality of the matching is never more than half the number of vertices and also never more than the number of edges. An important special case of the maximum-cardinality matching problem is when G is a bipartite graph representing a binary relation, whose vertices V are partitioned between left vertices in X and right vertices in Y, and edges in E always connect a left vertex to a right vertex. In this case, the problem can be efficiently solved with simpler algorithms than in the general case. The calculation of a maximum matching for a given graph is a fundamental task in computational graph theory. There are nonconstructive characterization theorems for the size of a maximum matching. This article is about computation of maximum matchings.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Maximum-cardinality matching» — https://en.wikipedia.org/wiki/Maximum-cardinality_matching
Wikidata Q65088751 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q65088751
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Maximum-cardinality_matching?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 1365861338, consultata il 2026-10-07T23:02:11.413Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: d09ae91dd8df6f6fafa7bfb4bd0a22a2ac729d53fb90106c6806564a660fbaa0