K-Matching

[math]\displaystyle{ k }[/math]-Matching --- [math]\displaystyle{ k }[/math]-паросочетание.

A [math]\displaystyle{ k }[/math]-matching in a hypergraph [math]\displaystyle{ G }[/math] is a collection of edges of [math]\displaystyle{ G }[/math] such that each point belongs to at most [math]\displaystyle{ k }[/math] of them (note that repetition of edges is allowed). A [math]\displaystyle{ 1 }[/math]-matching is also called matching. A [math]\displaystyle{ k }[/math]-matching can be considered as a mapping [math]\displaystyle{ w: E(G) \rightarrow \{0, 1, \ldots\} }[/math] such that

[math]\displaystyle{ \sum_{E \ni x} w(E) \leq k }[/math]

for every point [math]\displaystyle{ x }[/math] ([math]\displaystyle{ w(E) }[/math] is the multiplicity with which [math]\displaystyle{ E }[/math] occurs in the matching). A perfect [math]\displaystyle{ k }[/math]-matching is a [math]\displaystyle{ k }[/math]-matching such that each edge belongs to exactly [math]\displaystyle{ k }[/math] members of it (note the difference between this and a [math]\displaystyle{ k }[/math]-factor!). A fractional matching is an assignment of a non-negative real weight [math]\displaystyle{ w(E) }[/math] to each edge [math]\displaystyle{ E }[/math] such that

[math]\displaystyle{ \sum_{E \ni x} w(E) \leq 1 }[/math]

for every point [math]\displaystyle{ x }[/math].

The fractional matching number of [math]\displaystyle{ G }[/math] is the supremum of

[math]\displaystyle{ \sum_{e \in E(G)} w(e) }[/math]

over all fractional matchings [math]\displaystyle{ w }[/math].