Perfect fractional matching

Perfect fractional matching --- совершенное дробное паросочетание.

Let us associate a variable [math]\displaystyle{ x_{ij} }[/math] with each edge [math]\displaystyle{ (i,j) }[/math] of a graph [math]\displaystyle{ G = (V,E) }[/math]. A perfect fractional matching of [math]\displaystyle{ G }[/math] is a vector [math]\displaystyle{ \vec{x} \in \Re^{|E|} }[/math], where [math]\displaystyle{ \Re }[/math] is the set of real numbers, such that:

[math]\displaystyle{ \sum_{j \in N(i)} x_{ij} = 1,\mbox{ for all }i = 1, \ldots, |V|, }[/math]

[math]\displaystyle{ x_{ij} \geq 0,\mbox{ for all }(i,j) \in E. }[/math]

It is not difficult to see that [math]\displaystyle{ G }[/math] admits a perfect fractional matching if and only if [math]\displaystyle{ G }[/math] can be covered by pairwise disjoint edges and odd cycles.