Fractional matching
In graph theory, a fractional matching is a generalization of a matching in which, intuitively, each vertex may be broken into fractions that are matched to different neighbor vertices. == Definition == Given a graph G = ( V , E ) {\displaystyle G=(V,E)} , a fractional matching in G {\displaystyle G} is a function that assigns, to each edge e ∈ E {\displaystyle e\in E} , a fraction f ( e ) ∈ [ 0 , 1 ] {\displaystyle f(e)\in [0,1]} , such that for every vertex v ∈ V {\displaystyle v\in V} , the sum of fractions of edges adjacent to v {\displaystyle v} is at most one: ∀ v ∈ V : ∑ e ∋ v f ( e ) ≤ 1 {\displaystyle \forall v\in V:\sum _{e\ni v}f(e)\leq 1} A matching in the traditional sense is a special case of a fractional matching, in which the fraction of every edge is either zero or one: f ( e ) = 1 {\displaystyle f(e)=1} if e {\displaystyle e} is in the matching, and f ( e ) = 0 {\displaystyle f(e)=0} if it is not.