Graphiques bipartites avec poids min

cs.stackexchange https://cs.stackexchange.com/questions/128045

Question

J'ai un graphe bipartite complet avec des jeux de nœud $ a={a_1, a_2, \ ldots, a_n \} $ et $ b={b_1, b_2, \ ldots, b_n \} $ . Chaque nœud a un poids, $ v_i $ pour $ a_i $ et $ w_i $ pour $ b_i $ . Chaque nœud $ a_i $ est connecté à exactement un nœud de $ B $ , dites $ b_j $ , via un bord $ e_i $ , dont le poids est $ \ min (v_i, w_j) $ . Maintenant, je veux trouver un mappage unique de $ A $ à $ B $ , dont la somme des poids de bord est aussi petite que possible.

mon idée est de trier $ v_i $ s de plus en plus et $ w_i $ s La somme de tout $ \ min (v_i, w_i) $ après le tri. Est-ce correct? Pouvez-vous donner une preuve / ignifuge?

J'ai exécuté des simulations d'ordinateur pour $ n= 5,6, \ ldots, 10 $ avec des poids de sommet aléatoire et trouvé aucun contre-exemple.

Était-ce utile?

La solution

C'est bien que vous ayez vérifié votre idée sur des échantillons aléatoires.

Pour voir pourquoi votre idée fonctionne, trouvons le cas le plus simple mais non trivial, puis jetez-y un coup d'œil. Pour la simplicité et le WLog, le poids d'un nœud sera utilisé pour indiquer ce nœud. Par exemple, si $ a $ contient un nœud avec poids $ 42 $ , ce nœud sera appelé noeud Node 42.

le cas de $ n= 1 $ est trivial.

let $ n= 2 $ . Si nous arrive à regarder à $ a={1, 2 \ \ {1, 2 \} $ et $ b={3, 4 \} $ , cependant, nous avons choisi le mappage, la somme sera 1 + 2= 3 $ . Cet échantillon n'est apparemment pas éclairant.

Que diriez-vous de $ a={1, 3 \ \ {1, 3 \} $ et $ b={2,4 \ \ {2,4 } $ ?

  • Si nous connectons 1 avec 2 et 3 avec 4, la somme est $ \ min (1,2) + \ min (3,4)= 1 + 3= 4 $ .
  • Si nous connectons 1 avec 4 et 3 avec 2, la somme est $ \ min (1,4) + \ min (3,2)= 1 + 2= 3 $ .

Donc, c'est un exemple non trivial. Maintenant, nous devrions poser la question de base, pourquoi Le deuxième choix produit-il une somme plus petite?

Pour répondre à la question, nous devrions observer comment ces deux sommes montées. Notez que 1 apparaît dans les deux sommes. Est cette coïncidence? Pensez un instant et vous saurez que ce n'est pas le cas. 1 est le nombre minimum de tous les nombres. Donc, quoi qu'il soit connecté, il sera choisi comme poids de la connexion.

Cela signifie, quel que soit le numéro 1 est connecté à, ce qui est 3 dans ce cas, ce nombre sera manquant des calculs ultérieurs, c'est-à-dire qu'il sera "gaspillé". Plus les "déchets" sont plus importants, moins les numéros restants seront et donc le moins de poids que la connexion restante produira, car la fonction $ \ min (\ CDOT, \ CDOT) $ < / span> diminue par rapport aux deux variables. Donc, 1 devrait être connecté à un nombre aussi grand que possible. C'est pourquoi 1 est connecté à 4 au lieu de 3 afin de produire la somme totale minimale.

dans le cas de $ n= 2 $ , il n'y a que deux choix de la cartographie. Soit le plus petit nombre dans $ a $ est mappé sur le plus petit nombre dans $ B $ , surnommé "vers l'avant Mappage ", ou au plus grand nombre de $ B $ , surnommé" cartographie inversée ". Pour que la cartographie produise un poids total réduit, nous devrions toujours choisir le "cartographie inverse", de sorte qu'un grand nombre soit gaspillé (ou, quel est le même nombre, un nombre plus petit sera utilisé pour être utilisé.)

Pour prouver que votre idée est correct, nous montrons d'abord que pour tout mappage de $ a $ to $ b $ < / Span>, il y a une cartographie qui mesure $ \ min (a) $ à $ \ max (b) $ < / Span> sans poids total plus important. Supposons que map $ f $ maps $ \ min (a) $ à une $ b_j $ et un nombre $ a_i $ to $ \ max (b) $ . Alors nous pouvons faire une autre carte $ f '$ , qui est identique à $ f $ sauf pour ces 4 nombre, $ f '$ maps $ \ min (a) $ to $ \ max (b) $ et $ a_i $ to $ b_j $ . Depuis, comme nous l'avons montré ci-dessus, pour quatre chiffres $ \ min (a), a_i $ et $ b_j $ , $ \ max (b) $ , nous avons $$ \ min (\ min (a), \ max (b)) + \ min (a_i, b_j) \ Le \ min (\ min (a), b_j) + \ min (a_i, \ max (b)), $$ Le poids total de $ f '$ n'est pas supérieur à celui de $ F $

.

.

Nous savons donc,

  • Le poids total minimum provient d'un mappages qui mappe $ \ min (a) $ à $ \ max (b ) $ .
  • pour tous les mappages que map $ \ min (a) $ to $ \ max (b) $ , le poids total minimum provient de, par le même argument, un mappage qui mappe le minimum des numéros restants dans $ a $ (c'est-à-dire le deuxième nombre minimal dans < span class="math-conteneur"> $ a $ ) au maximum des numéros restants dans $ B $ (c'est-à-dire le deuxième nombre minimal de $ B $ ).
  • pour tous les mappages que map
Ontainer "> $ \ min (a) $ à $ \ max (b) $ et le deuxième numéro minimum dans $ A $ au deuxième numéro maximum dans $ B $ , le poids total minimum provient d'un mappage qui mappe le troisième numéro minimum dans $ A $ au troisième numéro maximum dans $ B $ .
  • et ainsi de suite, jusqu'au dernier numéro minimum dans $ A $ est mappé sur le dernier nombre maximum de $ b> $ b $ , c'est-à-dire le nombre maximum de $ A $ est mappé sur le nombre minimal de $ B $ < / span>. $ \ checkmark $

    • Une preuve encore plus formelle pourrait être donnée. Cependant, le raisonnement ci-dessus pourrait être plus facile à comprendre. Je crois, je crois, convaincre un humain ordinaire.

    Voici un autre moyen simple de prouver votre idée.

    Supposons d'abord tous les chiffres sont distincts. Laissez-nous prouver par réductio ad absurdum. Supposons que le poids total minimum est atteint par une mappage $ g $ autre que la cartographie décrite dans votre idée. Alors $ g $ doit contenir un sous-mappage qui est un "mappage avant", c'est-à-dire qu'il doit y avoir deux numéros $ \ alpha_1 \ lt \ alpha_2 $ in $ A $ et deux numéros $ \ beta_1 \ lt \ beta_2 $ dans $ b $ tel que $ g (\ alpha_1)=beta_1 $ et < Span Classe="Math-Conteneur"> $ g (\ alpha_2)=beta_2 $ .

    Maintenant, nous pouvons faire une autre mappage $ g '$ qui est identique à $ g $ partout sinon sauf que la sous-mappage de $ g '$ sur $ \ alpha_1 $ et $ \ alpha_2 $ est un "mappage inverse", c'est-à-dire, c'est-à-dire $ g '(\ alpha_1)=beta_2 $ et < Span Classe="Conteneur mathématique"> $ g '(\ alpha_2)=beta_1 $ . Maintenant, nous pouvons, comme auparavant, vérifier que le poids total de $ g '$ est inférieur à celui de $ g $ < / span>, qui contredit notre hypothèse.

    Si tous les chiffres ne sont pas distincts, nous utiliserons la technique d'approche de la limite. Perturber tous les nombres légèrement pour qu'ils soient distincts. Maintenant, tous les poids seront légèrement éteints de leur poids d'origine. Cela signifie que le poids total obtenu de votre idée ne doit pas être loin de la solution optimale. Laissez la perturbation aller à zéro, nous voyons que c'est en fait la solution optimale.

    Vous pourriez être intéressé par un problème similaire, Comment prouver l'algorithme gourmand qui minimise la somme maximale d'un couple .

    Autres conseils

    Je pense que la meilleure solution ici consiste à utiliser l'algorithme MIN-Coût Max-Flow sur ce graphique.Si vous ne le savez pas, allez-y en lire.Cet algorithme est la solution la plus classique pour ce type de problème.

    Licencié sous: CC-BY-SA avec attribution
    Non affilié à cs.stackexchange
    scroll top