Bipartite-Diagramme mit MIN-Gewichten

Question

Ich habe ein volles zweifaches Diagramm mit Knoten-Sets $ A={A_1, A_2, \ LDOTs, A_N \} $ und $ B={B_1, B_2, \ ldots, b_n \} $ . Jeder Knoten hat ein Gewicht, $ v_i $ für $ A_I $ und $ w_i $ für $ b_i $ . Jeder Knoten $ A_I $ ist mit genau einem Knoten $ B $ angeschlossen, sagen Sie $ b_j $ , über eine Kante $ E_I $ , deren Gewicht $ \ min ist (v_i, w_j) $ . Jetzt möchte ich ein eins-zu-eins-Mapping von $ A $ bis $ B $ , dessen Die Summe der Kantengewichte ist so klein wie möglich.

meine idee ist es, $ v_i $ s zunehmend und $ w_i $ s unermüdlich und dann finden Die Summe aller $ \ min (v_i, w_i) $ nach dem Sortieren. Ist es richtig? Können Sie einen Beweis geben / entwändig?

Ich habe Computersimulationen für $ n= 5,6, \ LDOs, 10 $ mit zufälligen Scheitelpunktgewichten ausgeführt und fand kein Gegenbeispiel.

Answer 1

Es ist schön, dass Sie Ihre Idee auf einige zufällige Proben überprüft haben.

---

Um zu sehen, warum Ihre Idee funktioniert, lassen Sie uns den einfachsten, aber nicht-trivialen Fall finden und schauen Sie sich dann an. Für Einfachheit und WLOG wird das Gewicht eines Knotens verwendet, um diesen Knoten zu bezeichnen. Wenn beispielsweise $ A $ einen Knoten mit Gewicht $ 42 $ enthält, wird dieser Knoten als Knoten 42.

der Fall der $ n= 1 $ ist trivial.

lass $ n= 2 $ . Wenn wir uns auf $ A={1, 2 \} $ und $ B={3, 4 \} $ , dann wählen wir jedoch das Mapping aus, die Summe ist $ 1 + 2= 3 $ . Diese Probe ist anscheinend nicht aufschlussreich.

Wie wäre es mit $ a={1, 3 \} $ und $ B={2,4 \ } $ ?

.
• Wenn wir 1 mit 2 und 3 mit 4 verbinden, ist die Summe $ \ min (1,2) + \ min (3,4)= 1 + 3= 4 $ .
• Wenn wir 1 mit 4 und 3 mit 2 verbinden, ist die Summe $ \ min (1,4) + \ min (3,2)= 1 + 2= 3 $ .

Dies ist also ein nicht triviales Beispiel. Jetzt sollten wir die grundlegende Frage stellen, Warum ist die zweite Wahl eine kleinere Summe?

Um die Frage zu beantworten, sollten wir beobachten, wie diese beiden Summen auftreten. Beachten Sie, dass in beiden Summen 1 erscheint. Ist das Zufall? Denken Sie für einen Moment nach und Sie werden wissen, dass es nicht ist. 1 ist die Mindestanzahl aller Zahlen. Also, mit der es verbunden ist, wird es als Gewicht der Verbindung ausgewählt.

das heißt, welche Zahl 1 miteinander verbunden ist, mit der in diesem Fall 3 3 ist, dass die Zahl von späteren Berechnungen fehlen, d. H. Es wird "verschwendet". Je größer der "Abfall" ist, desto weniger die verbleibenden Nummern werden sein und somit das weniger Gewicht die verbleibende Verbindung erzeugt, da Funktion $ \ min (\ cdot, \ cdot) $ < / span> nimmt in Bezug auf beide Variablen ab. So sollte 1 so groß wie möglich an eine Zahl angeschlossen werden. Das ist , warum 1 anstelle von 3 mit 4 verbunden ist, um die minimale Gesamtsumme zu erzeugen.

Im Falle von $ n= 2 $ gibt es nur zwei Auswahlmöglichkeiten der Zuordnung. Entweder die kleinere Anzahl in $ A $ wird der kleineren Zahl in $ B $ , dubbbt "vorwärts Mapping ", oder in der größeren Anzahl in $ B $ , dubbett" umgekehrtes Mapping ". Um das Mapping kleineres Gesamtgewicht zu erzeugen, sollten wir immer das "Reverse-Mapping" auswählen, sodass eine große Anzahl verschwendet wird (oder was dasselbe ist, dass eine kleinere Zahl verwendet wird.)

---

Um zu beweisen, dass Ihre Idee richtig ist, zeigen wir zuerst das für jedes Mapping von $ A $ bis $ B $ < / span>, gibt es eine Kartierung dieser Karten $ \ min (a) $ auf $ \ MAX (B) $ < / span> ohne größeres Gesamtgewicht. Angenommen, die Karte $ F $ Karten $ \ min (a) $ an einigen $ b_j $ und einige nummer $ a_i $ bis $ \ max (b) $ . Dann können wir eine andere Karte $ F '$ erstellen, die das gleiche wie $ F $ mit Ausnahme der 4 Nummer, $ F '$ Karten $ \ min (a) $ bis $ \ max (b) $ und $ A_I $ bis $ b_j $ . Da wir, wie wir oben gezeigt haben, für vier Zahlen $ \ min (a), a_i $ und $ b_j $ , $ \ max (b) $ , wir haben $$ \ min (\ min (a), \ max (b)) + \ min (a_i, b_j) \ le \ min (\ min (a), b_j) + \ min (a_i, \ max (b)), $$ Das Gesamtgewicht von $ F '$ ist nicht größer als der von $ f $ .

wir wissen also,

.
• Das minimale Gesamtgewicht stammt aus einem Mappings, das $ \ min (a) $ bis $ \ max (B ) $ .
• Für alle Zuordnungen, die $ \ min (a) $ in $ \ max (b) $ , das minimale Gesamtgewicht kommt von demselben Argument ein Mapping, das das Minimum der verbleibenden Nummern in $ A $ (dh die zweite Mindestanzahl in < Span-Klasse="Math-Container"> $ A $ ) Zum Maximum der verbleibenden Zahlen in $ B $ (dh die zweite Mindestanzahl in $ B $ ).
• für alle Zuordnungen, die

Ontainer "> $ \ min (A) $ bis $ \ MAX (B) $ und die zweite Mindestanzahl in $ A $ Zur zweiten Maximalnummer in $ B $ , stammt das minimale Gesamtgewicht von einem Mapping, das die dritte Mindestanzahl in $ A $ an die dritte Maximalnummer in $ B $ .

usw., bis die letzte Mindestanzahl in $ A $ der letzten Höchstzahl in $ B zugeordnet ist $ , dh die maximale Anzahl in $ A $ wird der Mindestanzahl in $ B $ . $ \ Checkmark $

Es könnte ein noch formellerer Beweis gegeben werden. Die obige Argumentation ist jedoch möglicherweise einfacher zu verstehen. Ich glaube, glaube ich, überzeugen Sie einen gewöhnlichen Menschen.

---

Hier ist ein weiterer unkomplizierter Weg, um Ihre Idee zu beweisen.

Angenommen, alle Zahlen sind unterschiedlich. Lasst uns von Reductio Ad Absurdum beweisen. Angenommen, das minimale Gesamtgewicht kann durch einen Mapping- $ G $ angesehen werden, außer der in Ihrer Idee beschriebenen Mapping. Dann muss $ g $ ein Unter-Mapping enthalten, das ein "Vorwärtszuordnungen" ist, dh es muss zwei Zahlen $ vorhanden sein \ alpha_1 \ lt \ alpha_2 $ in $ A $ und zwei Zahlen $ \ beta_1 \ lt \ beta_2 $ in $ B $ so, dass $ g (\ alpha_1)=beta_1 $ und < Span-Klasse="Math-Container"> $ g (\ alpha_2)=beta_2 $ .

Jetzt können wir ein anderes Mapping $ g '$ erstellen, was dasselbe ist wie der $ g $ überall sonst außer dass das Unterkapping von $ g '$ auf $ \ alpha_1 $ und $ \ alpha_2 $ ist ein "umgekehrter Mapping", dh $ g '(\ alpha_1)=beta_2 $ und < Span-Klasse="Math-Container"> $ g '(\ alpha_2)=beta_1 $ . Jetzt können wir, wie zuvor, dass das Gesamtgewicht von $ g '$ kleiner ist als der von $ g $ < / span>, was unserer Annahme widerspricht.

Wenn alle Zahlen nicht unterscheidet werden, verwenden wir die Technik der Annäherung an die Annäherung. Notieren Sie alle Zahlen leicht, damit sie sich unterscheiden. Jetzt werden alle Gewichte leicht von ihren ursprünglichen Gewichten sein. Das heißt, das Gesamtgewicht, das von Ihrer Idee gewonnen wird, sollte nicht weit von der optimalen Lösung sein. Lassen Sie die Störung auf Null gehen, wir sehen, dass es tatsächlich die optimale Lösung ist.

---

Sie könnten an einem ähnlichen Problem interessiert sein, Wie erweist man den gierigen Algorithmus, der die maximale Summe eines Paares minimiert.

Answer 2

Ich denke, die beste Lösung hier verwendet den Min-Cost-Max-Flow-Algorithmus in diesem Graphen.Wenn Sie nichts davon wissen, lesen Sie und lesen Sie darüber.Dieser Algorithmus ist die klassische Lösung für diese Art von Problem.