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.
Given a graph G = (V, E), a fractional matching in G is a function that assigns, to each edge e in E, a fraction f(e) in [0, 1], such that for every vertex v in V, the sum of fractions of edges adjacent to v is at most 1:[1]
The size of an integral matching is the number of edges in the matching, and the matching number of a graph G is the largest size of a matching in G. Analogously, the size of a fractional matching is the sum of fractions of all edges. The fractional matching number of a graph G is the largest size of a fractional matching in G. It is often denoted by .[2] Since a matching is a special case of a fractional matching, for every graph G one has that the integral matching number of G is less than or equal to the fractional matching number of G; in symbols:
In a general graph, The fractional matching number is either an integer or a half-integer.[4]
For a bipartite graph G = (X+Y, E), a fractional matching can be presented as a matrix with |X| rows and |Y| columns. The value of the entry in row x and column y is the fraction of the edge (x,y).
A fractional matching is called perfect if the sum of weights adjacent to each vertex is exactly 1. The size of a perfect matching is exactly |V|/2.
In a bipartite graph G = (X+Y, E), a fractional matching is called X-perfect if the sum of weights adjacent to each vertex of X is exactly 1. The size of an X-perfect fractional matching is exactly |X|.
For a bipartite graph G = (X+Y, E), the following are equivalent:
The first condition implies the second because an integral matching is a fractional matching. The second implies the third because, for each subset W of X, the sum of weights near vertices of W is |W|, so the edges adjacent to them are necessarily adjacent to at least |W| vertices of Y. By Hall's marriage theorem, the last condition implies the first one.[5][better source needed]
In a general graph, the above conditions are not equivalent - the largest fractional matching can be larger than the largest integral matching. For example, a 3-cycle admits a perfect fractional matching of size 3/2 (the fraction of every edge is 1/2), but does not admit perfect integral matching - the largest integral matching is of size 1.
A largest fractional matching in a graph can be easily found by linear programming, or alternatively by a maximum flow algorithm. In a bipartite graph, it is possible to convert a maximum fractional matching to a maximum integral matching of the same size. This leads to a simple polynomial-time algorithm for finding a maximum matching in a bipartite graph.[6]
If G is a bipartite graph with |X| = |Y| = n, and M is a perfect fractional matching, then the matrix representation of M is a doubly stochastic matrix - the sum of elements in each row and each column is 1. Birkhoff's algorithm can be used to decompose the matrix into a convex sum of at most n2-2n+2 permutation matrices. This corresponds to decomposing M into a convex sum of at most n2-2n+2 perfect matchings.
A fractional matching of maximum cardinality (i.e., maximum sum of fractions) can be found by linear programming. There is also a strongly-polynomial time algorithm,[7] using augmenting paths, that runs in time .
Suppose each edge on the graph has a weight. A fractional matching of maximum weight in a graph can be found by linear programming. In a bipartite graph, it is possible to convert a maximum-weight fractional matching to a maximum-weight integral matching of the same size, in the following way:[8]
Given a graph G = (V,E), the fractional matching polytope of G is a convex polytope that represents all possible fractional matchings of G. It is a polytope in R|E| - the |E|-dimensional Euclidean space. Each point (x1,...,x|E|) in the polytope represents a matching in which the fraction of each edge e is xe. The polytope is defined by |E| non-negativity constraints (xe ≥ 0 for all e in E) and |V| vertex constraints (the sum of xe, for all edges e that are adjacent to a vertex v, is at most 1). In a bipartite graph, the vertices of the fractional matching polytope are all integral.