二分的图表含有最小重量的图表

Question

我有一个完整的二分图，带有节点集 $ a={a_1，a_2，\ ldots，a_n \} $ 和 $ b={b_1，b_2，\ ldots，b_n \} $ 。每个节点都有一个权重， $ v_i $ for $ a_i $ 和 $ w_i $ for $ b_i $ 。每个节点 $ a_i $ 连接到恰好一个节点 $ b $ ，说 $ b_j $ ，通过边缘 $ e_i $ ，其权重 $ \ min （v_i，w_j）$ 。现在我想从 $ a $ 到 $ b $ ，找到一对一的映射边缘重量的总和尽可能小。

我的想法是排序 $ v_i $ s越来越多地和 $ w_i $ s逐渐减小，然后找到所有 $ \ min（v_i，w_i）$ 排序后的总和。这是正确的吗？你可以给出校验/脱离吗？

我已经运行了 $ n= 5,6，\ ldots，10 $ 的计算机模拟，随机顶点权重，找不到反例。

Answer 1

很高兴您在某些随机样本上检查了您的想法。

---

要了解为什么你的想法工作，让我们找到最简单但非平凡的案例，然后看看它。为简单和WLOG，节点的权重将用于表示该节点。例如，如果 $ a $ 包含具有权重 $ 42 $ 的节点，则该节点将被称为节点42.

$ n= 1 $ 是微不足道的。

let $ n= 2 $ 。如果我们恰好查看 $ a={1,2 \} $ 和 $ b={3， 4 \} $ ，但是我们选择映射，总和是 $ 1 + 2= 3 $ 。该样本显然不是为启发性的。

如何约 $ a={1,3 \} $ 和 $ b={2,4 \ $ ？

• 如果我们用4和3连接1，总和是 $ \ min（1,2）+ \ min（3,4）= 1 + 3= 4 $ 。
• 如果使用4和3使用2连接1，总和是 $ \ min（1,4）+ \ min（3,2）= 1 + 2= 3 $ 。

所以这是一个非琐碎的例子。现在我们应该问基本问题，为什么第二选择产生较小的总和？

要回答这个问题，我们应该观察这两个总和的结果。请注意，两个总和中出现1。这是巧合吗？想一想，你会知道它不是。 1是所有数字的最小数量。所以无论它连接到什么，它将被选为连接的重量。

这意味着，无论第1号连接到哪个数字，在这种情况下是3，从以后的计算中丢失该数字，即，它将“浪费”。 “废物”是越大，剩余数字越少，因此剩余连接的重量越小，因为函数 $ \ min（\ cdot，\ cdot）$ < / span>对两个变量的逐渐减小。所以1应该与尽可能大的数字连接。这是为什么 1连接到4而不是3，以产生最小总和。

在 $ n= 2 $ 时，映射只有两种选择。 $ a $ 中的较小数字映射到 $ b $ ，dubbed“forward”中的较小数字映射“，或者到 $ b $ ，称为”反向映射“。为了使映射产生较小的总重量，我们应该始终选择“反向映射”，从而浪费大量的数量（或者，或者，什么是相同的，将使用较小的数字。）

---

要证明您的想法是正确的，我们首先显示出于从 $ a $ 到 $ b $ < / span>，有一个映射，映射 $ \ min（a）$ 到 $ \ max（b）$ < /跨度>没有更大的总重量。假设映射 $ f $ maps $ \ min（a）$ 到一些 $ b_j $ 和一些数字 $ a_i $ to $ \ max（b）$ 。然后我们可以制作另一个地图 $ f'$ ，与 $ f $ 相同，除了这些4号码， $ f'$ maps $ \ min（a）$ to $ \ max（b）$ 和 $ a_i $ to $ b_j $ 。由于我们如上所述，对于四个数字 $ \ min（a），a_i $ 和 $ b_j $ ， $ \ max（b）$ ，我们有 $$ \ min（\ min（a），\ max（b））+ \ min（a_i，b_j）\ le \ min（\ min（a），b_j）+ \ min（a_i，\ max（b）），$$ $ f'$ 的总重量不大于 $ f $ 。

所以我们知道，

• 最小总重量来自映射 $ \ min（a）$ to $ \ max（b ）$ 。
• 对于所有映射，即地图 $ \ min（a）$ 到 $ \ max（b）$ ，最小总重量来自相同的参数，映射映射，映射 $ a $ （即< Span Class=“Math-Container”> $ a $ ）到 $ b $ 中剩余数字的最大值（即，即第二个最小数字） $ b $ ）。
• 为映射

ontainer“> $ \ min（a）$ 到 $ \ max（b）$ 和 $ b $ 中的第二个最大数量，最小总重量来自映射 $ a $ 在 $ b $ 中的第三个最大数字。

等，直到 $ a $ 映射到 $ b中的最后一个最大数字$ ，即 $ a $ 中的最大数量映射到 $ b $ < / span>。 $ \ checkmark $

可以给出更正式的证据。但是，上述推理可能更容易理解。我相信，应该说服普通人。

---

这里是证明你的想法的另一种直接的方式。

首先假设所有数字都不同。让我们证明还原AD荒谬。假设最小总重量可以通过映射 $ g $ 除了您的想法中描述的映射之外。然后 $ g $ 必须包含一个子映射，即“正向映射”，即，必须有两个数字 $ \ alpha_1 \ lt \ alpha_2 $ 在 $ a $ 和两个数字 $ \ beta_1 \ lt \ beta_2 $ 在 $ b $ 这样 $ g（\ alpha_1）=beta_1 $ 和< SPAN Class=“math-container”> $ g（\ alpha_2）=beta_2 $ 。

现在我们可以制作另一个映射 $ g'$ ，它与 $ g $ 无处不在除此之外，除了 $ g'$ 上的子映射， $ \ alpha_1 $ 和 $ \ alpha_2 $ 是一个“反向映射”，即 $ g'（\ alpha_1）=beta_2 $ 和< SPAN Class=“Math-Container”> $ G'（\ Alpha_2）=beta_1 $ 。现在我们可以如前所述，验证 $ g'$ 的总重量小于 $ g $ < / span>，它与我们的假设相矛盾。

如果所有数字都不明显，我们将使用限制接近的技术。略微扰乱所有数字，以便它们变得截然不同。现在所有重量都会略微脱离原来的重量。这意味着从您的想法中获得的总重量不应远离最佳解决方案。让扰动转到零，我们认为它实际上是最佳解决方案。

---

您可能对类似的问题感兴趣，如何证明贪婪算法最小化配对的最大总和

Answer 2

我认为这里的最佳解决方案是在此图中使用最小成本的最大流量算法。如果您不了解它，请访问并阅读它。该算法是这种问题最经典的解决方案。