Augmenting path in a matching (source code)

= Augmenting path in a matching

= Augmenting paths in a matching
{synonym}

An <augmenting path in a matching> $M$ is a nonempty <alternating path in a matching> with distinct endpoints that are both <unmatched vertices in a matching>. Its first and last <edges> lie outside $M$. Thus it has $k+1$ unselected <edges> and $k$ selected <edges>, for some $k\geq0$. Taking the <symmetric difference>
$$
M'=M\mathbin\triangle E(P)
=(M\setminus E(P))\cup(E(P)\setminus M)
$$
removes the selected <edges> on $P$ and inserts its unselected <edges>. Each internal <vertex> exchanges one selected <edge> for another; each endpoint gains its first selected <edge>. All choices away from $P$ stay in place, so $M'$ is a <matching in a graph> with $|M'|=|M|+1$.<Graph Theory by Reinhard Diestel>[Matching, Covering and Packing, §2.1, printed p. 2: alternating paths, augmenting paths and symmetric difference]{ref}

For an explicit repair, let the <path graph> $P_6$ have <vertices> $1,2,3,4,5,6$ in that order and start with
$$
M=\{(2,3),(4,5)\},\qquad P=(1,2,3,4,5,6).
$$
The endpoints $1$ and $6$ are initially <unmatched vertices in a matching>. Along $P$ the <edges> are outside, inside, outside, inside, outside $M$. Remove $(2,3)$ and $(4,5)$, then add $(1,2),(3,4),(5,6)$ together:
$$
M'=M\mathbin\triangle E(P)=\{(1,2),(3,4),(5,6)\}.
$$
This raises the <cardinality> from two to three and gives a <perfect matching>. Six <vertices> allow at most three disjoint pairs, so it is also a <maximum cardinality matching>. The initial $M$ is already a <maximal matching>: every unused <edge> touches a matched <vertex>. Augmentation succeeds because it can replace earlier choices instead of only adding to them.

\Image[/matching-augmenting-path-symmetric-difference.png]
{title=The <augmenting path in a matching> on P₆ replaces two selected <edges> by three using <symmetric difference>}

One unused <edge> joining two <unmatched vertices in a matching> is the shortest possible <augmenting path in a matching>. Longer <augmenting paths in a matching> reassign several partners, explaining why a stalled <greedy matching> need not be optimal. For edge benefits $w_e$, the change in total benefit is
$$
\sum_{e\in E(P)\setminus M}w_e-\sum_{e\in E(P)\cap M}w_e,
$$
which need not be positive even though the <cardinality> increases. A <maximum-weight matching> therefore needs a different optimality test. In an assignment equality graph an <augmenting path in a matching> moves toward a <perfect matching> while preserving zero <reduced costs> on matched <edges>; this is the setting used by the <Hungarian algorithm>.