HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What is a fractional matching?

Submitted by: @import:stackexchange-cs··
0
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?

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'.

Context

StackExchange Computer Science Q#107149, answer score: 8

Revisions (0)

No revisions yet.