本文主要是介绍二分图完全匹配 不完全匹配 / linear_sum_assignment 详解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

https://jack.valmadre.net/notes/2020/12/08/non-perfect-linear-assignment/

\(G = (U,V,E)\)

• \(|U| = r\)
• \(|V| = n\)
• without loss of generality, assume \(r \leq n\)

• \(E(i,j) = \infty\) means no connection
  • Missing edges
• \(E(i,j) = 0\) means cost is zero.
  • however, given that cost can be either positive or negative, zero can be chosen.

In a matching problem, there will be \(\nu\) chosen edges.

Balanced

Balanced means \(r = n\)

two subsets have equal cardinality

Perfect/Complete Matching

note that the problem is not actuallysolved using a general-purpose ILP(integer linear programming) solver, it is just a convenient framework in which to express the problem

Perfect/Complete matching = every vertex has a match

The constraint that the sum of each row and column is equal to one ensures that each element has exactly one match.

Unbalanced

assume \(r < n\)

an unbalanced probem cannot have a perfect matching, since there will be at least \(n-r\) unmatched elements in the larger set.

One-sided Perfect Matching

One-sided Perfect Matching = every vertex in the smaller set has a match.

In one-sided perfect matching, \(\nu = r < n\)

What if there is no perfect matching?

Imperfect Matching(with given edge number)

- when there does not exist a (one-sided)perfect matching.

when \(\nu < r\), i.e. one-sided perfect matching cannot be achieved due to the lack of edges, all possible matchings are imperfect/incomplete.

[Note

这篇关于二分图完全匹配 不完全匹配 / linear_sum_assignment 详解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！