Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Fractional matching
Summary
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:
A matching in the traditional sense is a special case of a fractional matching, in which the fraction of every edge is either 0 or 1: f(e) = 1 if e is in the matching, and f(e) = 0 if it is not. For this reason, in the context of fractional matchings, usual matchings are sometimes called integral matchings.
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 . 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:A graph in which is called a stable graph. Every bipartite graph is stable; this means that in every bipartite graph, the fractional matching number is an integer and it equals the integral matching number.
In a general graph, The fractional matching number is either an integer or a half-integer.
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.