如何找到边权和最大的图的最大匹配？

Question

我有一个应用程序，人们可以给对方打分，满分10分。每天午夜，我都想为每个成员计算一个“匹配”。一般来说，我希望让每个人都尽可能地快乐。

So at the midnight, I have an oriented graph like so : 
1 -> 2 : 7.5 // P1 give a 7.5/10 to P2
1 -> 3 : 5
1 -> 4 : 9
2 -> 3 : 6 
2 -> 1 : 4 
etc.  

为了简单起见，让我们假设如果P1给P2一个5，P2给P1一个7，那么匹配的P1 - P2将具有5+7- (7-5)/2 = 11的权重(我减去差异是因为，对于相同的成绩总和，它们彼此接近会更好，也就是说，a (7/10 - 7/10)比a (10/10 -4/10)更好)。

因此，完成此操作后，我们就得到了一个无向图。从数学上讲，为了我的目的，我认为我需要找到一种算法，在所有具有此图的最大尺寸匹配中，找到具有最大权重和的算法。这样的算法存在吗？

我已经研究了“婚姻稳定问题”和“分配问题”，但这些问题是针对可分为两类(男性/女性，男性/任务)的图的。

Answer 1

要做到这一点，一种方法是修改您的图形，然后在其中找到一个maximum weight matching。

我需要找到一个算法，在所有有这个图的最大尺寸的匹配中，找到具有最大权重和的那个。

。这样的算法存在吗？

让我们考虑一下您的图G = (V, E, w)，其中w是您的权重函数。让我们用n表示V的大小，即图中的顶点数量，并用M表示边中的最大权重。

然后，您所要做的就是以这种方式定义w'：对于E的任何边缘e，w'(e) = w(e) + n*M。

在这种情况下，G' = (V, E, w')上的最大权重匹配对应于G = (V, E, w)中也具有最大权重的最大大小的匹配。