augmenting path for a matching

增广路

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

Translation evidence: Literature usage

Meaning in context

For a matching M in a finite bipartite graph, an augmenting path is a path of positive length whose edges alternate outside and inside M and whose two endpoints are unmatched; switching membership along it increases matching size by one.

有限二部图中，相对于匹配 M，增广路是长度为正、边交替属于 M 外和 M 内、且两个端点均未匹配的路；沿路切换所选边可使匹配边数增加一。

Example

In $a-b-c-d$ with $M=\{bc\}$, the path $(a,b,c,d)$ augments M to $\{ab,cd\}$.

Usage and distinctions

An alternating path with a matched endpoint need not augment. A single edge between unmatched vertices is an augmenting path.

Recommended reading in this subject · Preparation & skip guidance

Definition sources

1. Reinhard Diestel — Graph Theory, fourth electronic edition (2010), corrected reprint 2012Section 2.1, alternating and augmenting path definitions, Figure 2.1.1 and switching argument · Checked 2026-10-14

Translation sources

1. Reinhard Diestel — 图论，第五版，于青林译§2.1，印刷pp.33–34，「增广路 (augmenting path)」定义及图2.1.1 · Checked 2026-10-14

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