J'ai un graphe non orienté avec des poids sur chaque arête. Je veux enlever un ensemble d'arêtes tel que chaque sommet a un degré au plus K, mais je veux garder la somme pondérée maximum possible des arêtes. Je suis venu avec un programme entier qui devrait atteindre la bonne solution.Trouver un ensemble d'arêtes à enlever de façon à ce que le degré de chaque sommet ne dépasse pas K et que la somme des poids de bord soit maximisée
Mes questions sont les suivantes:
- ce que ce problème a un nom? Si oui, qu'est-ce que c'est?
- Existe-t-il un algorithme de temps polynomial connu pour résoudre ce problème? Jusqu'à présent, je n'ai pas réussi à en trouver. Peut-être qu'il me manque quelque chose d'évident.
Pour les funzies voici mon programme entier. Permettez-moi de savoir si je fait des erreurs:
# given (graph, K):
# Let x[e] be 1 if we keep an edge e and 0 if we cut it
# Keep the best set of edges for each node
maximize
sum(d['weight'] * x[(u, v)]
for u in graph.nodes()
for v, d in graph.node[u].items())
# The degree of each node must be less than K
subject to
all(
sum(x[(u, v)] for v in graph.node[u]) <= K
for u in graph.nodes()
)
EDIT:
Merci à l'aide de David Eisenstat j'ai pu trouver une bonne description d'un algorithme polynomial à la section 2 de
Implementing Weighted b-Matching Algorithms: Towards a Flexible Software Design par Matthias Muller Hannemann et Alexander Schwartz publié dans WAE'98
Cette description généralise le cas 1-adaptation de la Bloss om algorithme par Pulleyblank dans le problème de b-matching (que j'ai également trouvé être appelé flux bidirectionnel).
Le cas particulier k = 1 est l'appariement général de poids maximum, qui peut être résolu en temps polynomial. Mon intuition est que, s'il y a un algorithme de temps polynomial en général, alors vous pouvez l'obtenir en résolvant le problème non pondéré en généralisant le lemme de chemin augmentant et en appliquant ensuite le cadre dual primal. –