# What is minimum cost perfect matching problem for general graph?

It does make sense when we talk about perfect matching in bipartite graphs because there are two sets of points, for example, one set may be jobs and other set may contain different machines. But when we talk about minimum cost perfect matching in general graphs, it is not making any sense for me, what are the nodes and edge cost representing, If you can give some real-life example depicting minimum cost perfect matching in general graphs. It will be very helpful to me.

Also, I need a precise definition of the minimum cost perfect matching problem. Thank You.

• en.wikipedia.org/wiki/Matching_(graph_theory)#Applications
– D.W.
Commented Oct 7, 2019 at 7:28
• I went through it but did not get anything. It would be better if you give a more elaborative answer which can build the intuition. Commented Oct 7, 2019 at 10:14

• The set of instances is the set of all edge-weighted undirected graphs $$G=(V, E, w)$$, where $$w : E \to \mathbb{R}$$.
• Given an instance $$G=(V, E, w)$$, the set of feasible solutions are the perfect matchings $$M$$ of $$G$$, i.e., all the sets $$M \subseteq E$$ such that, $$\forall u \in V \; |M \cap \{ (u, v) \in E : v \in V \}| = 1$$.
• Given an instance $$G=(V, E, w)$$ and a feasible solution $$M$$ for $$G$$, the is a function called measure defined as $$m(G, M) = \sum_{e \in M} w(e)$$.
You are organizing a trip for a (large) group of $$n=4k$$, $$k \in \mathbb{N}^+$$, participants that will travel together on a bus with $$n$$ seats. Bus seats are arranged in rows of $$4$$, with $$2$$ adjacent seats on each side and a corridor in the middle. Not all of the participants enjoy their company equally (indeed, some of them categorically refuse to be close by) and you know, for each pair of people that can sit together, how much they'd happy (or unhappy) to be sat next to each other (say, in a scale from $$-1$$ to $$1$$). Being a thoughtful organizer, you want to arrange seats in order to maximize the social welfare of the participants, i.e., the sum of the happiness of all pairs of neighbors in the arrangement you choose.