0
$\begingroup$

Consider the optimal perfect matching problem on a bipartite graph G= (X $\cup$ Y, E) with $\vert X \vert = \vert Y \vert$ and a weight function $w: E \to \mathbb{R}$. We want to find a perfect matching with maximal sum of edge weights. Where all edges in E are between X and Y only. Is there a canonical example of a bipartite graph that does NOT have a perfect matching? (so called inadmissible bipartite graphs).

Certainly we can isolate a vertex from X or Y and get inadmissibility. Can a fully connected bipartite graph be inadmissible? (these are the graphs I am working with)

Recall a perfect matching M is defined as a subset of E such that each node in X is incident to precisely one edge in M and each node in Y is incident to precisely one edge in M.

$\endgroup$
  • $\begingroup$ okay, maybe this is obvious: fully connected bipartite graphs always have an optimal perfect matching since there is always atleast one perfect matching? $\endgroup$ – user352102 Oct 24 '18 at 1:49
  • $\begingroup$ see Hall's marriage theorem: en.wikipedia.org/wiki/Hall%27s_marriage_theorem $\endgroup$ – user352102 Oct 24 '18 at 1:57
0
$\begingroup$

Hall's marriage theorem has a necessary and sufficient condition for a bipartite graph to have a perfect matching. The existence of at least one perfect matching means there is an optimal perfect matching (one with the sum of weights is maximal) assuming X and Y are finite vertex sets.

see: https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.