Erel Segal: /* Perfect fractional matching */
In [[graph theory]], a '''fractional matching''' is a generalization of a [[Matching (graph theory)|matching]] in which, intuitively, each vertex may be broken into fractions that are matched to different neighbor vertices.
Formally, 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:<ref name=":1">Liquid error: wrong number of arguments (given 1, expected 2)</ref> <blockquote><math>\forall v\in V: \sum_{e\ni v}f(e)\leq 1</math> </blockquote>A matching (often called: '''integral matching''') is a special case of a fractional matching, in which the fraction of every edge is either 1 or 0: ''f(e)'' = 1 if ''e'' is in the matching, and ''f(e)'' = 0 if it is not.
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 <math>\nu^*(G)</math>.<ref name=":0">Liquid error: wrong number of arguments (given 1, expected 2)</ref>
The '''integral matching number''' of a graph ''G'' is the largest size of an integral matching in ''G''. It is often denoted by <math>\nu(G)</math>.<ref name=":0" />
Since a matching is a special case of a fractional matching, for every graph ''G'':<blockquote>integral-matching-number (''G'') ≤ fractional-matching-number (''G'');</blockquote>In symbols:<blockquote><math>\nu(G) \leq \nu^*(G).</math></blockquote>In a bipartite graph equality holds: <math>\nu(G) = \nu^*(G).</math> In a general graph, <math>\nu(G) > \frac{2}{3} \nu^*(G).</math> <ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref>
== Perfect fractional matching ==
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''|.
The following are equivalent for a bipartite graph ''G'' = (''X+Y, E''):<ref></ref>
*''G'' admits an ''X''-perfect integral matching.
*''G'' admits an ''X''-perfect fractional matching. The implication is obvious since an integral matching is a fractional matching.
*''G'' satisfies the condition to [[Hall's marriage theorem]]. The implication holds 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.
== Algorithmic aspects ==
A largest fractional matching in a graph can be easily found by [[linear programming]], or alternatively by a [[Maximum flow problem|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.<ref></ref>
== References ==
[[Category:Matching (graph theory)]]
Formally, 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:<ref name=":1">Liquid error: wrong number of arguments (given 1, expected 2)</ref> <blockquote><math>\forall v\in V: \sum_{e\ni v}f(e)\leq 1</math> </blockquote>A matching (often called: '''integral matching''') is a special case of a fractional matching, in which the fraction of every edge is either 1 or 0: ''f(e)'' = 1 if ''e'' is in the matching, and ''f(e)'' = 0 if it is not.
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 <math>\nu^*(G)</math>.<ref name=":0">Liquid error: wrong number of arguments (given 1, expected 2)</ref>
The '''integral matching number''' of a graph ''G'' is the largest size of an integral matching in ''G''. It is often denoted by <math>\nu(G)</math>.<ref name=":0" />
Since a matching is a special case of a fractional matching, for every graph ''G'':<blockquote>integral-matching-number (''G'') ≤ fractional-matching-number (''G'');</blockquote>In symbols:<blockquote><math>\nu(G) \leq \nu^*(G).</math></blockquote>In a bipartite graph equality holds: <math>\nu(G) = \nu^*(G).</math> In a general graph, <math>\nu(G) > \frac{2}{3} \nu^*(G).</math> <ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref>
== Perfect fractional matching ==
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''|.
The following are equivalent for a bipartite graph ''G'' = (''X+Y, E''):<ref></ref>
*''G'' admits an ''X''-perfect integral matching.
*''G'' admits an ''X''-perfect fractional matching. The implication is obvious since an integral matching is a fractional matching.
*''G'' satisfies the condition to [[Hall's marriage theorem]]. The implication holds 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.
== Algorithmic aspects ==
A largest fractional matching in a graph can be easily found by [[linear programming]], or alternatively by a [[Maximum flow problem|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.<ref></ref>
== References ==
[[Category:Matching (graph theory)]]
from Wikipedia - New pages [en] https://ift.tt/2VmSfI3
via IFTTT
No comments:
Post a Comment