= Maximum-weight matching
Assign each <edge> $e$ a real benefit $w_e$. A <maximum-weight matching> maximizes $\sum_{e\in M}w_e$ over all <matchings in a graph> $M$; the empty <matching in a graph> is allowed. Setting every $w_e=1$ recovers a <maximum cardinality matching>, but otherwise the objectives can disagree.
On the same <path graph> $P_4$, give the middle <edge> benefit $3$ and each outer <edge> benefit $1$. The <matching in a graph> $\{(2,3)\}$ has total benefit $3$, while the two-<edge> <matching in a graph> $\{(1,2),(3,4)\}$ has total benefit $2$. Thus the smaller choice is the unique <maximum-weight matching>. If instead the requirement is to find a <maximum cardinality matching> and then maximize benefit among those, the outer <edges> must be chosen. Requiring a <perfect matching> before optimizing cost is another distinct problem, covered by <minimum-weight perfect matching>. With negative benefits a <maximum-weight matching> can even be empty, so it need not be a <maximal matching>.
Back to article page
