patternMinor
What is a fractional matching?
Viewed 0 times
fractionalwhatmatching
Problem
For the maximum matching problem, we can find the fractional matching which I understand involves some sort of weighting for the edges. However, I cannot seem to find an exact and simple explanation of what a fractional matching is. How does it compare to an integral matching?
If this question seems too basic, could I please have a link to somewhere that explains it?
If this question seems too basic, could I please have a link to somewhere that explains it?
Solution
Given a graph $G=(V,E)$, we can represent a matching as a function $f$ from the edges $E$ to $\{0,1\}$ such that for each vertex $v\in V$, we have $\sum_{w\in N(v)} f(v,w) \leq1$, where $N(v)$ is the neighbourhood of $v$, i.e. the set of its adjacent vertices. (We have equality for a perfect matching) In this representation, $f(e)=1$ means the edge $e$ is part of the matching.
A fractional matching can then be represented by a function $f'$ from the edges $E$ to the continuous interval $[0,1]$, with the same constraint, i.e. $\sum_{w\in N(v)} f'(v,w) \leq1$. So, intuitively, each vertex is 'divided' over its incident edges such that it is participating in at most one edge 'in total'.
A fractional matching can then be represented by a function $f'$ from the edges $E$ to the continuous interval $[0,1]$, with the same constraint, i.e. $\sum_{w\in N(v)} f'(v,w) \leq1$. So, intuitively, each vertex is 'divided' over its incident edges such that it is participating in at most one edge 'in total'.
Context
StackExchange Computer Science Q#107149, answer score: 8
Revisions (0)
No revisions yet.