perfect matching

完美匹配

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

Other names / variants: 1-factor edge set

Translation evidence: Literature usage

Meaning in context

A perfect matching in a finite simple graph is a matching incident with every vertex.

有限简单图中的完美匹配是饱和全部顶点的匹配，即每个顶点恰好属于一条所选边。

Example

In the cycle a−b−c−d−aa-b-c-d-a, {ab,cd}\{ab,cd\} is a perfect matching.

Usage and distinctions

A matching saturating only one bipartite part is not necessarily perfect. The empty graph has a perfect empty matching by the vacuous convention.

Recommended reading in this subject · Preparation & skip guidance

Definition sources

  1. Reinhard Diestel — Graph Theory, fourth electronic edition (2010), corrected reprint 2012Chapter 2 opening, a matching of the entire vertex set and its correspondence with a 1-factor · Checked 2026-10-14

Translation sources

  1. 南京大学计算机科学与技术系 — 二部图中的匹配，离散数学课程组slides 6–7 / PDF pp.6–7「完美匹配」，完备匹配说明 · 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.