maximal matching

极大匹配

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

Other names / variants: inclusion-maximal matching

Translation evidence: Literature usage

Meaning in context

A maximal matching is a matching not properly contained in another matching of the same graph.

极大匹配是不真包含于该图任何其他匹配的匹配，即不能直接添加一条边而仍保持匹配。

Example

In $a-b-c-d$, $\{bc\}$ is maximal, but its one edge is fewer than the two edges in $\{ab,cd\}$.

Usage and distinctions

Maximality permits a better matching obtained by deleting and replacing edges; it does not certify maximum size.

Recommended reading in this subject · Preparation & skip guidance

Definition sources

1. Reinhard Diestel — Graph Theory, fourth electronic edition (2010), corrected reprint 2012Section 2.1, proof of Theorem 2.1.1, passage using maximality to ensure an edge touches the matching · Checked 2026-10-14

Translation sources

1. 南京大学计算机科学与技术系 — 二部图中的匹配，离散数学课程组slide 6 / PDF p.6，图中的匹配，标签「极大匹配」 · Checked 2026-10-14

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