J'ai un graphique sous la forme d'une grille rectangulaire, c'est-à-dire N nœuds et 2N arêtes, tous les nœuds adjacents sont connectés. Cela signifie qu'il est deux couleurs, et donc il est possible de faire un appariement bipartite sur celui-ci.Correspondance bipartite de poids maximum
Chaque (non orienté) bord a un poids qui lui est assignée - soit -2, -1, 0, 1 ou 2. Aucune autre valeur sont autorisées
Comment puis-je faire pour trouver le correspondant sur ce graphique que maximise la somme des pesées dans l'appariement? Pseudocode serait bien, ne vous embêtez pas avec des langues spécifiques.
Idéalement, je cherche un algorithme qui fonctionne en temps quadratique - peut-être O (n^2 log n) au pire.
Avant de proposer une solution, j'ai essayé de faire un match max en utilisant les bords de poids 2, puis de poids 1 (sans dépasser les bords du poids 2). J'ai marqué 98% avec cette implémentation (le problème vient d'une olympiade informatique), et je me demande quelle est la solution à 100%.
Ne voulez-vous pas dire 2N bords? Et vous voulez que l'appariement inclue tous les nœuds, n'est-ce pas? – Beta
Oui, 2N bords (édité pour refléter cela). Et je veux que la correspondance inclue n'importe quel nombre de nœuds, tant que la somme des bords dans la correspondance est maximisée. – evgeny
Je pense que vous cherchez des coupures de graphiques - http://en.wikipedia.org/wiki/Cut_(graph_theory). L'algorithme de coupe minimum exécute O (n^3), et je doute que quiconque ici puisse le battre. –