Matching

Matching --- паросочетание.

For a graph [math]\displaystyle{ G = (V,E) }[/math], a subset [math]\displaystyle{ E' \subseteq E }[/math] such that for all edges [math]\displaystyle{ e, e' \in E' }[/math] with [math]\displaystyle{ e \neq e' }[/math] [math]\displaystyle{ e \cap e' = \emptyset }[/math] holds. A maximum-cardinality matching is a matching which contains a maximum number of edges. A perfect matching is a matching in which every vertex of the graph is an end-point of some element of the matching. Not every graph contains a perfect matching.