maximum matching

最大匹配

Combinatorics · Undergraduate · Mathematics Resources editorial compilation (AI-assisted)

Other names / variants: maximum-cardinality matching

Translation evidence: Literature usage

Meaning in context

A maximum matching of a finite graph is a matching with at least as many edges as every other matching of that graph.

有限图的最大匹配是边数达到所有匹配中最大值的匹配。

Example

In a−b−c−da-b-c-d, {ab,cd}\{ab,cd\} is maximum, with two edges.

Usage and distinctions

Maximum compares cardinalities globally; maximal forbids only strict containment by another matching.

Recommended reading in this subject · Preparation & skip guidance

Definition sources

  1. Keller and Trotter — Applied Combinatorics (2016)Section 14.2, maximum matching definition · Checked 2026-10-14

Translation sources

  1. Reinhard Diestel — 图论，第五版，于青林译§2.1，印刷p.34，增广路讨论末「寻找最大匹配」 · Checked 2026-10-14
Edit source / propose a PRReport a correction

Original encyclopedia and terminology content: CC BY-SA 4.0. Contribute or report a correction.